circ_tree_contains_point()

int circ_tree_contains_point	(	const CIRC_NODE *	node,
		const POINT2D *	pt,
		const POINT2D *	pt_outside,
		int	level,
		int *	on_boundary
	)

Walk the tree and count intersections between the stab line and the edges.

odd => containment, even => no containment. KNOWN PROBLEM: Grazings (think of a sharp point, just touching the stabline) will be counted for one, which will throw off the count.

Definition at line 495 of file lwgeodetic_tree.c.

{
        GEOGRAPHIC_POINT closest;
        GEOGRAPHIC_EDGE stab_edge, edge;
        POINT3D S1, S2, E1, E2;
        double d;
        uint32_t i, c;
 
        /* Construct a stabline edge from our "inside" to our known outside point */
        geographic_point_init(pt->x, pt->y, &(stab_edge.start));
        geographic_point_init(pt_outside->x, pt_outside->y, &(stab_edge.end));
        geog2cart(&(stab_edge.start), &S1);
        geog2cart(&(stab_edge.end), &S2);
 
        LWDEBUGF(3, "%*s entered", level, "");
 
        /*
        * If the stabline doesn't cross within the radius of a node, there's no
        * way it can cross.
        */
 
        LWDEBUGF(3, "%*s :working on node %p, edge_num %d, radius %g, center POINT(%.12g %.12g)", level, "", node, node->edge_num, node->radius, rad2deg(node->center.lon), rad2deg(node->center.lat));
        d = edge_distance_to_point(&stab_edge, &(node->center), &closest);
        LWDEBUGF(3, "%*s :edge_distance_to_point=%g, node_radius=%g", level, "", d, node->radius);
        if ( FP_LTEQ(d, node->radius) )
        {
                LWDEBUGF(3,"%*s :entering this branch (%p)", level, "", node);
 
                /* Return the crossing number of this leaf */
                if ( circ_node_is_leaf(node) )
                {
                        int inter;
                        LWDEBUGF(3, "%*s :leaf node calculation (edge %d)", level, "", node->edge_num);
                        geographic_point_init(node->p1->x, node->p1->y, &(edge.start));
                        geographic_point_init(node->p2->x, node->p2->y, &(edge.end));
                        geog2cart(&(edge.start), &E1);
                        geog2cart(&(edge.end), &E2);
 
                        inter = edge_intersects(&S1, &S2, &E1, &E2);
                        LWDEBUGF(3, "%*s :inter = %d", level, "", inter);
 
                        if ( inter & PIR_INTERSECTS )
                        {
                                LWDEBUGF(3,"%*s ::got stab line edge_intersection with this edge!", level, "");
                                /* To avoid double counting crossings-at-a-vertex, */
                                /* always ignore crossings at "lower" ends of edges*/
                                GEOGRAPHIC_POINT e1, e2;
                                cart2geog(&E1,&e1); cart2geog(&E2,&e2);
 
                                LWDEBUGF(3,"%*s LINESTRING(%.15g %.15g,%.15g %.15g)", level, "",
                                        pt->x, pt->y,
                                        pt_outside->x, pt_outside->y
                                        );
 
                                LWDEBUGF(3,"%*s LINESTRING(%.15g %.15g,%.15g %.15g)", level, "",
                                        rad2deg(e1.lon), rad2deg(e1.lat),
                                        rad2deg(e2.lon), rad2deg(e2.lat)
                                        );
 
                                if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
                                {
                                        LWDEBUGF(3,"%*s ::rejecting stab line grazing by left-side edge", level, "");
                                        return 0;
                                }
                                else
                                {
                                        LWDEBUGF(3,"%*s ::accepting stab line intersection", level, "");
                                        return 1;
                                }
                        }
                        else
                        {
                                LWDEBUGF(3,"%*s edge does not intersect", level, "");
                        }
                }
                /* Or, add up the crossing numbers of all children of this node. */
                else
                {
                        c = 0;
                        for ( i = 0; i < node->num_nodes; i++ )
                        {
                                LWDEBUGF(3,"%*s calling circ_tree_contains_point on child %d!", level, "", i);
                                c += circ_tree_contains_point(node->nodes[i], pt, pt_outside, level + 1, on_boundary);
                        }
                        return c % 2;
                }
        }
        else
        {
                LWDEBUGF(3,"%*s skipping this branch (%p)", level, "", node);
        }
        return 0;
}

References cart2geog(), circ_node::center, circ_node_is_leaf(), circ_tree_contains_point(), edge_distance_to_point(), edge_intersects(), circ_node::edge_num, GEOGRAPHIC_EDGE::end, FP_LTEQ, geog2cart(), geographic_point_init(), GEOGRAPHIC_POINT::lat, GEOGRAPHIC_POINT::lon, LWDEBUGF, circ_node::nodes, circ_node::num_nodes, circ_node::p1, circ_node::p2, PIR_B_TOUCH_RIGHT, PIR_COLINEAR, PIR_INTERSECTS, rad2deg, circ_node::radius, GEOGRAPHIC_EDGE::start, POINT2D::x, and POINT2D::y.

Referenced by circ_tree_contains_point(), circ_tree_distance_tree_internal(), CircTreePIP(), test_tree_circ_pip(), and test_tree_circ_pip2().

Here is the call graph for this function:

Here is the caller graph for this function: