[SCM] PostGIS branch master updated. 3.4.0rc1-1014-g2c4abb3f2
git at osgeo.org
git at osgeo.org
Wed Mar 13 15:51:01 PDT 2024
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via 2c4abb3f268b1e806e59337bf737fbcc04d9b31e (commit)
from 1284f168d7159c8585b46f9bdfd54c63927f8c9e (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 2c4abb3f268b1e806e59337bf737fbcc04d9b31e
Author: Paul Ramsey <pramsey at cleverelephant.ca>
Date: Wed Mar 13 15:50:50 2024 -0700
Clean up recttree a little bit
diff --git a/liblwgeom/lwtree.c b/liblwgeom/lwtree.c
index 481b329f6..19a6bd41c 100644
--- a/liblwgeom/lwtree.c
+++ b/liblwgeom/lwtree.c
@@ -82,7 +82,7 @@ rect_tree_free(RECT_NODE *node)
}
static int
-rect_leaf_node_intersects(RECT_NODE_LEAF *n1, RECT_NODE_LEAF *n2)
+rect_leaf_node_intersects(const RECT_NODE_LEAF *n1, const RECT_NODE_LEAF *n2)
{
const POINT2D *p1, *p2, *p3, *q1, *q2, *q3;
DISTPTS dl;
@@ -196,7 +196,7 @@ rect_leaf_node_intersects(RECT_NODE_LEAF *n1, RECT_NODE_LEAF *n2)
* Returns 1 if segment is to the right of point.
*/
static inline int
-rect_leaf_node_segment_side(RECT_NODE_LEAF *node, const POINT2D *q, int *on_boundary)
+rect_leaf_node_segment_side(const RECT_NODE_LEAF *node, const POINT2D *q, int *on_boundary)
{
const POINT2D *p1, *p2, *p3;
switch (node->seg_type)
@@ -311,7 +311,7 @@ rect_leaf_node_segment_side(RECT_NODE_LEAF *node, const POINT2D *q, int *on_boun
* be on both sides, and will have a zero return sum.
*/
static int
-rect_tree_ring_contains_point(RECT_NODE *node, const POINT2D *pt, int *on_boundary)
+rect_tree_ring_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_boundary)
{
/* Only test nodes that straddle our stabline vertically */
/* and might be to the right horizontally */
@@ -341,7 +341,7 @@ rect_tree_ring_contains_point(RECT_NODE *node, const POINT2D *pt, int *on_bounda
* (multiply contained by interior rings?)
*/
static int
-rect_tree_area_contains_point(RECT_NODE *node, const POINT2D *pt)
+rect_tree_area_contains_point(const RECT_NODE *node, const POINT2D *pt)
{
/* Can't do anything with a leaf node, makes no sense */
if (rect_node_is_leaf(node))
@@ -381,7 +381,7 @@ rect_tree_area_contains_point(RECT_NODE *node, const POINT2D *pt)
* Simple containment test for node/point inputs
*/
static int
-rect_node_bounds_point(RECT_NODE *node, const POINT2D *pt)
+rect_node_bounds_point(const RECT_NODE *node, const POINT2D *pt)
{
if (pt->y < node->ymin || pt->y > node->ymax ||
pt->x < node->xmin || pt->x > node->xmax)
@@ -395,7 +395,7 @@ rect_node_bounds_point(RECT_NODE *node, const POINT2D *pt)
* and false otherwise.
*/
int
-rect_tree_contains_point(RECT_NODE *node, const POINT2D *pt)
+rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt)
{
int i, c;
@@ -762,6 +762,10 @@ rect_tree_from_lwpoly(const LWGEOM *lwgeom)
nodes[j++] = node;
}
}
+ /* Put the top nodes in a z-order curve for a spatially coherent */
+ /* tree after node merge */
+ qsort(nodes, j, sizeof(RECT_NODE*), rect_node_cmp);
+
tree = rect_nodes_merge(nodes, j);
tree->geom_type = lwgeom->type;
lwfree(nodes);
@@ -848,7 +852,9 @@ rect_tree_from_lwcollection(const LWGEOM *lwgeom)
/* Note: CompoundCurve has edges already spatially organized, no */
/* sorting needed */
if (lwgeom->type != COMPOUNDTYPE)
+ {
qsort(nodes, j, sizeof(RECT_NODE*), rect_node_cmp);
+ }
tree = rect_nodes_merge(nodes, j);
@@ -933,7 +939,7 @@ rect_node_to_str(const RECT_NODE *n)
* that intersect. Prune branches that do not intersect.
*/
static int
-rect_tree_intersects_tree_recursive(RECT_NODE *n1, RECT_NODE *n2)
+rect_tree_intersects_tree_recursive(const RECT_NODE *n1, const RECT_NODE *n2)
{
int i, j;
#if POSTGIS_DEBUG_LEVEL >= 4
@@ -987,7 +993,7 @@ rect_tree_intersects_tree_recursive(RECT_NODE *n1, RECT_NODE *n2)
int
-rect_tree_intersects_tree(RECT_NODE *n1, RECT_NODE *n2)
+rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2)
{
/*
* It is possible for an area to intersect another object
@@ -1014,24 +1020,12 @@ rect_tree_intersects_tree(RECT_NODE *n1, RECT_NODE *n2)
return rect_tree_intersects_tree_recursive(n1, n2);
}
-/*
-* For slightly more speed when doing distance comparisons,
-* where we only care if d1 < d2 and not what the actual value
-* of d1 or d2 is, we use the squared distance and avoid the
-* sqrt()
-*/
-static inline double
-distance_sq(double x1, double y1, double x2, double y2)
-{
- double dx = x1-x2;
- double dy = y1-y2;
- return dx*dx + dy*dy;
-}
-
static inline double
distance(double x1, double y1, double x2, double y2)
{
- return sqrt(distance_sq(x1, y1, x2, y2));
+ double dx = x1-x2;
+ double dy = y1-y2;
+ return sqrt(dx*dx + dy*dy);
}
/*
@@ -1222,72 +1216,8 @@ rect_leaf_node_distance(const RECT_NODE_LEAF *n1, const RECT_NODE_LEAF *n2, RECT
}
-static int
-rect_tree_node_sort_cmp(const void *a, const void *b)
-{
- RECT_NODE *n1 = *(RECT_NODE**)a;
- RECT_NODE *n2 = *(RECT_NODE**)b;
- if (n1->d < n2->d) return -1;
- else if (n1->d > n2->d) return 1;
- else return 0;
-}
-
-/* Calculate the center of a node */
-static inline void
-rect_node_to_p2d(const RECT_NODE *n, POINT2D *pt)
-{
- pt->x = (n->xmin + n->xmax)/2;
- pt->y = (n->ymin + n->ymax)/2;
-}
-
-/*
-* (If necessary), sort the children of each node in
-* order of their distance from the enter of the other node.
-*/
-static void
-rect_tree_node_sort(RECT_NODE *n1, RECT_NODE *n2)
-{
- int i;
- RECT_NODE *n;
- POINT2D c1, c2, c;
- if (!rect_node_is_leaf(n1) && ! n1->i.sorted)
- {
- rect_node_to_p2d(n2, &c2);
- /* Distance of each child from center of other node */
- for (i = 0; i < n1->i.num_nodes; i++)
- {
- n = n1->i.nodes[i];
- rect_node_to_p2d(n, &c);
- n->d = distance2d_sqr_pt_pt(&c2, &c);
- }
- /* Sort the children by distance */
- n1->i.sorted = 1;
- qsort(n1->i.nodes,
- n1->i.num_nodes,
- sizeof(RECT_NODE*),
- rect_tree_node_sort_cmp);
- }
- if (!rect_node_is_leaf(n2) && ! n2->i.sorted)
- {
- rect_node_to_p2d(n1, &c1);
- /* Distance of each child from center of other node */
- for (i = 0; i < n2->i.num_nodes; i++)
- {
- n = n2->i.nodes[i];
- rect_node_to_p2d(n, &c);
- n->d = distance2d_sqr_pt_pt(&c1, &c);
- }
- /* Sort the children by distance */
- n2->i.sorted = 1;
- qsort(n2->i.nodes,
- n2->i.num_nodes,
- sizeof(RECT_NODE*),
- rect_tree_node_sort_cmp);
- }
-}
-
static double
-rect_tree_distance_tree_recursive(RECT_NODE *n1, RECT_NODE *n2, RECT_TREE_DISTANCE_STATE *state)
+rect_tree_distance_tree_recursive(const RECT_NODE *n1, const RECT_NODE *n2, RECT_TREE_DISTANCE_STATE *state)
{
double min, max;
@@ -1319,7 +1249,6 @@ rect_tree_distance_tree_recursive(RECT_NODE *n1, RECT_NODE *n2, RECT_TREE_DISTAN
{
int i, j;
double d_min = FLT_MAX;
- rect_tree_node_sort(n1, n2);
if (rect_node_is_leaf(n1) && !rect_node_is_leaf(n2))
{
for (i = 0; i < n2->i.num_nodes; i++)
@@ -1351,7 +1280,7 @@ rect_tree_distance_tree_recursive(RECT_NODE *n1, RECT_NODE *n2, RECT_TREE_DISTAN
}
}
-double rect_tree_distance_tree(RECT_NODE *n1, RECT_NODE *n2, double threshold)
+double rect_tree_distance_tree(const RECT_NODE *n1, const RECT_NODE *n2, double threshold)
{
double distance;
RECT_TREE_DISTANCE_STATE state;
diff --git a/liblwgeom/lwtree.h b/liblwgeom/lwtree.h
index 0aa4cf31d..1167e3c2c 100644
--- a/liblwgeom/lwtree.h
+++ b/liblwgeom/lwtree.h
@@ -95,19 +95,19 @@ RECT_NODE * rect_tree_from_lwgeom(const LWGEOM *geom);
/**
* Test if two RECT_NODE trees intersect one another.
*/
-int rect_tree_intersects_tree(RECT_NODE *tree1, RECT_NODE *tree2);
+int rect_tree_intersects_tree(const RECT_NODE *tree1, const RECT_NODE *tree2);
/**
* Return the distance between two RECT_NODE trees.
*/
-double rect_tree_distance_tree(RECT_NODE *n1, RECT_NODE *n2, double threshold);
+double rect_tree_distance_tree(const RECT_NODE *n1, const RECT_NODE *n2, double threshold);
/**
* Free the rect-tree memory
*/
void rect_tree_free(RECT_NODE *node);
-int rect_tree_contains_point(RECT_NODE *tree, const POINT2D *pt);
+int rect_tree_contains_point(const RECT_NODE *tree, const POINT2D *pt);
RECT_NODE * rect_tree_from_ptarray(const POINTARRAY *pa, int geom_type);
LWGEOM * rect_tree_to_lwgeom(const RECT_NODE *tree);
char * rect_tree_to_wkt(const RECT_NODE *node);
-----------------------------------------------------------------------
Summary of changes:
liblwgeom/lwtree.c | 107 +++++++++--------------------------------------------
liblwgeom/lwtree.h | 6 +--
2 files changed, 21 insertions(+), 92 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list