From cd73095c2154e761773c49dcce17730adcb47df4 Mon Sep 17 00:00:00 2001 From: Paul Ramsey Date: Mon, 30 Nov 2009 22:08:12 +0000 Subject: [PATCH] Fix up boundary condition in node interaction test. git-svn-id: http://svn.osgeo.org/postgis/trunk@4949 b70326c6-7e19-0410-871a-916f4a2858ee --- liblwgeom/cunit/cu_measures.c | 10 +++++++--- liblwgeom/lwtree.c | 7 ++++++- 2 files changed, 13 insertions(+), 4 deletions(-) diff --git a/liblwgeom/cunit/cu_measures.c b/liblwgeom/cunit/cu_measures.c index 543dec6ef..c12082809 100644 --- a/liblwgeom/cunit/cu_measures.c +++ b/liblwgeom/cunit/cu_measures.c @@ -159,7 +159,7 @@ void test_rect_tree_contains_point(void) RECT_NODE* tree; int result; int boundary = 0; - + /* square */ poly = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))", PARSER_CHECK_NONE); tree = rect_tree_new(poly->rings[0]); @@ -308,6 +308,7 @@ void test_rect_tree_intersects_tree(void) RECT_NODE *tree1, *tree2; int result; + /* total overlap, A == B */ poly1 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 3 1, 0 2, 3 3, 0 4, 3 5, 0 6, 5 6, 5 0, 0 0))", PARSER_CHECK_NONE); poly2 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 3 1, 0 2, 3 3, 0 4, 3 5, 0 6, 5 6, 5 0, 0 0))", PARSER_CHECK_NONE); tree1 = rect_tree_new(poly1->rings[0]); @@ -319,6 +320,7 @@ void test_rect_tree_intersects_tree(void) rect_tree_free(tree1); rect_tree_free(tree2); + /* hiding between the tines of the comb */ poly1 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 3 1, 0 2, 3 3, 0 4, 3 5, 0 6, 5 6, 5 0, 0 0))", PARSER_CHECK_NONE); poly2 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0.3 0.7, 0.3 0.8, 0.4 0.8, 0.4 0.7, 0.3 0.7))", PARSER_CHECK_NONE); tree1 = rect_tree_new(poly1->rings[0]); @@ -330,6 +332,7 @@ void test_rect_tree_intersects_tree(void) rect_tree_free(tree1); rect_tree_free(tree2); + /* between the tines, but with a corner overlapping */ poly1 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 3 1, 0 2, 3 3, 0 4, 3 5, 0 6, 5 6, 5 0, 0 0))", PARSER_CHECK_NONE); poly2 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0.3 0.7, 0.3 0.8, 0.4 0.8, 1.3 0.3, 0.3 0.7))", PARSER_CHECK_NONE); tree1 = rect_tree_new(poly1->rings[0]); @@ -340,7 +343,8 @@ void test_rect_tree_intersects_tree(void) lwpoly_free(poly2); rect_tree_free(tree1); rect_tree_free(tree2); -/* + + /* Just touching the top left corner of the comb */ poly1 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((0 0, 3 1, 0 2, 3 3, 0 4, 3 5, 0 6, 5 6, 5 0, 0 0))", PARSER_CHECK_NONE); poly2 = (LWPOLY*)lwgeom_from_ewkt("POLYGON((-1 5, 0 5, 0 7, -1 7, -1 5))", PARSER_CHECK_NONE); tree1 = rect_tree_new(poly1->rings[0]); @@ -351,7 +355,7 @@ void test_rect_tree_intersects_tree(void) lwpoly_free(poly2); rect_tree_free(tree1); rect_tree_free(tree2); -*/ + } diff --git a/liblwgeom/lwtree.c b/liblwgeom/lwtree.c index 266d77798..faff7335e 100644 --- a/liblwgeom/lwtree.c +++ b/liblwgeom/lwtree.c @@ -53,12 +53,15 @@ int rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_b int rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2) { + LWDEBUGF(4,"n1 (%.9g %.9g,%.9g %.9g) vs n2 (%.9g %.9g,%.9g %.9g)",n1->xmin,n1->ymin,n1->xmax,n1->ymax,n2->xmin,n2->ymin,n2->xmax,n2->ymax); /* There can only be an edge intersection if the rectangles overlap */ - if( ! ( FP_GTEQ(n1->xmin, n2->xmax) || FP_GTEQ(n2->xmin, n1->xmax) || FP_GTEQ(n1->ymin, n2->ymax) || FP_GTEQ(n2->ymin, n1->ymax) ) ) + if( ! ( FP_GT(n1->xmin, n2->xmax) || FP_GT(n2->xmin, n1->xmax) || FP_GT(n1->ymin, n2->ymax) || FP_GT(n2->ymin, n1->ymax) ) ) { + LWDEBUG(4," interaction found"); /* We can only test for a true intersection if the nodes are both leaf nodes */ if( rect_node_is_leaf(n1) && rect_node_is_leaf(n2) ) { + LWDEBUG(4," leaf node test"); /* Check for true intersection */ if( lw_segment_intersects(n1->p1, n1->p2, n2->p1, n2->p2) ) return LW_TRUE; @@ -67,6 +70,7 @@ int rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2) } else { + LWDEBUG(4," internal node found, recursing"); /* Recurse to children */ if( rect_node_is_leaf(n1) ) { @@ -86,6 +90,7 @@ int rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2) } else { + LWDEBUG(4," no interaction found"); return LW_FALSE; } } -- 2.40.0