circ_tree_contains_point()

int circ_tree_contains_point	(	const CIRC_NODE *	node,
		const POINT2D *	pt,
		const POINT2D *	pt_outside,
		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);
 
        LWDEBUG(3, "entered");
 
        /*
        * If the stabline doesn't cross within the radius of a node, there's no
        * way it can cross.
        */
 
        LWDEBUGF(3, "working on node %p, edge_num %d, radius %g, center POINT(%g %g)", 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, "edge_distance_to_point=%g, node_radius=%g", d, node->radius);
        if ( FP_LTEQ(d, node->radius) )
        {
                LWDEBUGF(3,"entering this branch (%p)", node);
 
                /* Return the crossing number of this leaf */
                if ( circ_node_is_leaf(node) )
                {
                        int inter;
                        LWDEBUGF(3, "leaf node calculation (edge %d)", 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);
 
                        if ( inter & PIR_INTERSECTS )
                        {
                                LWDEBUG(3," got stab line edge_intersection with this edge!");
                                /* To avoid double counting crossings-at-a-vertex, */
                                /* always ignore crossings at "lower" ends of edges*/
 
                                if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
                                {
                                        LWDEBUG(3,"  rejecting stab line grazing by left-side edge");
                                        return 0;
                                }
                                else
                                {
                                        LWDEBUG(3,"  accepting stab line intersection");
                                        return 1;
                                }
                        }
                }
                /* Or, add up the crossing numbers of all children of this node. */
                else
                {
                        c = 0;
                        for ( i = 0; i < node->num_nodes; i++ )
                        {
                                LWDEBUG(3,"internal node calculation");
                                LWDEBUGF(3," calling circ_tree_contains_point on child %d!", i);
                                c += circ_tree_contains_point(node->nodes[i], pt, pt_outside, on_boundary);
                        }
                        return c % 2;
                }
        }
        else
        {
                LWDEBUGF(3,"skipping this branch (%p)", node);
        }
 
        return 0;
}

References circ_node::center, circ_node_is_leaf(), 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, LWDEBUG, 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_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: