[postgis-tickets] r16371 - Apply node sorting before descent to CIRC_NODE trees for

[Paul Ramsey]

Author: pramsey
Date: 2018-02-02 14:23:31 -0800 (Fri, 02 Feb 2018)
New Revision: 16371

Modified:
   trunk/liblwgeom/lwgeodetic_tree.c
   trunk/liblwgeom/lwgeodetic_tree.h
Log:
Apply node sorting before descent to CIRC_NODE trees for
faster calculation of geography distances.
Closes #4010


Modified: trunk/liblwgeom/lwgeodetic_tree.c
===================================================================
--- trunk/liblwgeom/lwgeodetic_tree.c	2018-02-02 21:42:12 UTC (rev 16370)
+++ trunk/liblwgeom/lwgeodetic_tree.c	2018-02-02 22:23:31 UTC (rev 16371)
@@ -601,6 +601,51 @@
 	}
 }
 
+
+/***********************************************************************
+* Internal node sorting routine to make distance calculations faster?
+*/
+
+struct sort_node {
+	CIRC_NODE *node;
+	double d;
+};
+
+static int
+circ_nodes_sort_cmp(const void *a, const void *b)
+{
+	struct sort_node *node_a = (struct sort_node *)(a);
+	struct sort_node *node_b = (struct sort_node *)(b);
+	if (node_a->d < node_b->d) return -1;
+	else if (node_a->d > node_b->d) return 1;
+	else return 0;
+}
+
+static void
+circ_internal_nodes_sort(CIRC_NODE **nodes, uint32_t num_nodes, const CIRC_NODE *target_node)
+{
+	int i;
+	struct sort_node sort_nodes[CIRC_NODE_SIZE];
+
+	/* Copy incoming nodes into sorting array and calculate */
+	/* distance to the target node */
+	for (i = 0; i < num_nodes; i++)
+	{
+		sort_nodes[i].node = nodes[i];
+		sort_nodes[i].d = sphere_distance(&(nodes[i]->center), &(target_node->center));
+	}
+
+	/* Sort the nodes and copy the result back into the input array */
+	qsort(sort_nodes, num_nodes, sizeof(struct sort_node), circ_nodes_sort_cmp);
+	for (i = 0; i < num_nodes; i++)
+	{
+		nodes[i] = sort_nodes[i].node;
+	}
+	return;
+}
+
+/***********************************************************************/
+
 static double
 circ_tree_distance_tree_internal(const CIRC_NODE* n1, const CIRC_NODE* n2, double threshold, double* min_dist, double* max_dist, GEOGRAPHIC_POINT* closest1, GEOGRAPHIC_POINT* closest2)
 {
@@ -746,6 +791,7 @@
 		/* tests above. */
 		if ( n1->geom_type && lwtype_is_collection(n1->geom_type) )
 		{
+			circ_internal_nodes_sort(n1->nodes, n1->num_nodes, n2);
 			for ( i = 0; i < n1->num_nodes; i++ )
 			{
 				d = circ_tree_distance_tree_internal(n1->nodes[i], n2, threshold, min_dist, max_dist, closest1, closest2);
@@ -754,6 +800,7 @@
 		}
 		else if ( n2->geom_type && lwtype_is_collection(n2->geom_type) )
 		{
+			circ_internal_nodes_sort(n2->nodes, n2->num_nodes, n1);
 			for ( i = 0; i < n2->num_nodes; i++ )
 			{
 				d = circ_tree_distance_tree_internal(n1, n2->nodes[i], threshold, min_dist, max_dist, closest1, closest2);
@@ -762,6 +809,7 @@
 		}
 		else if ( ! circ_node_is_leaf(n1) )
 		{
+			circ_internal_nodes_sort(n1->nodes, n1->num_nodes, n2);
 			for ( i = 0; i < n1->num_nodes; i++ )
 			{
 				d = circ_tree_distance_tree_internal(n1->nodes[i], n2, threshold, min_dist, max_dist, closest1, closest2);
@@ -770,6 +818,7 @@
 		}
 		else if ( ! circ_node_is_leaf(n2) )
 		{
+			circ_internal_nodes_sort(n2->nodes, n2->num_nodes, n1);
 			for ( i = 0; i < n2->num_nodes; i++ )
 			{
 				d = circ_tree_distance_tree_internal(n1, n2->nodes[i], threshold, min_dist, max_dist, closest1, closest2);

Modified: trunk/liblwgeom/lwgeodetic_tree.h
===================================================================
--- trunk/liblwgeom/lwgeodetic_tree.h	2018-02-02 21:42:12 UTC (rev 16370)
+++ trunk/liblwgeom/lwgeodetic_tree.h	2018-02-02 22:23:31 UTC (rev 16371)
@@ -41,6 +41,7 @@
 	struct circ_node** nodes;
 	int edge_num;
 	uint32_t geom_type;
+	double d;
 	POINT2D pt_outside;
 	POINT2D* p1;
 	POINT2D* p2;