ptarray_contains_point_sphere()

int ptarray_contains_point_sphere	(	const POINTARRAY *	pa,
		const POINT2D *	pt_outside,
		const POINT2D *	pt_to_test
	)

This routine returns LW_TRUE if the stabline joining the pt_outside and pt_to_test crosses the ring an odd number of times, or if the pt_to_test is on the ring boundary itself, returning LW_FALSE otherwise.

The pt_outside must be guaranteed to be outside the ring (use the geography_pt_outside() function to derive one in postgis, or the gbox_pt_outside() function if you don't mind burning CPU cycles building a gbox first).

Definition at line 3502 of file lwgeodetic.c.

{
        POINT3D S1, S2; /* Stab line end points */
        POINT3D E1, E2; /* Edge end points (3-space) */
        POINT2D p; /* Edge end points (lon/lat) */
        uint32_t count = 0, i, inter;
 
        /* Null input, not enough points for a ring? You ain't closed! */
        if ( ! pa || pa->npoints < 4 )
                return LW_FALSE;
 
        /* Set up our stab line */
        ll2cart(pt_to_test, &S1);
        ll2cart(pt_outside, &S2);
 
        /* Initialize first point */
        getPoint2d_p(pa, 0, &p);
        ll2cart(&p, &E1);
 
        /* Walk every edge and see if the stab line hits it */
        for ( i = 1; i < pa->npoints; i++ )
        {
                LWDEBUGF(4, "testing edge (%d)", i);
                LWDEBUGF(4, "  start point == POINT(%.12g %.12g)", p.x, p.y);
 
                /* Read next point. */
                getPoint2d_p(pa, i, &p);
                ll2cart(&p, &E2);
 
                /* Skip over too-short edges. */
                if ( point3d_equals(&E1, &E2) )
                {
                        continue;
                }
 
                /* Our test point is on an edge end! Point is "in ring" by our definition */
                if ( point3d_equals(&S1, &E1) )
                {
                        return LW_TRUE;
                }
 
                /* Calculate relationship between stab line and edge */
                inter = edge_intersects(&S1, &S2, &E1, &E2);
 
                /* We have some kind of interaction... */
                if ( inter & PIR_INTERSECTS )
                {
                        /* If the stabline is touching the edge, that implies the test point */
                        /* is on the edge, so we're done, the point is in (on) the ring. */
                        if ( (inter & PIR_A_TOUCH_RIGHT) || (inter & PIR_A_TOUCH_LEFT) )
                        {
                                return LW_TRUE;
                        }
 
                        /* It's a touching interaction, disregard all the left-side ones. */
                        /* It's a co-linear intersection, ignore those. */
                        if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
                        {
                                /* Do nothing, to avoid double counts. */
                                LWDEBUGF(4,"    edge (%d) crossed, count == %d, disregarding to avoid double count", i, count);
                        }
                        else
                        {
                                /* Increment crossingn count. */
                                count++;
                                LWDEBUGF(4,"    edge (%d) crossed, count == %d", i, count);
                        }
                }
                else
                {
                        LWDEBUGF(4,"    edge (%d) did not cross", i);
                }
 
                /* Increment to next edge */
                E1 = E2;
        }
 
        LWDEBUGF(4,"final count == %d", count);
 
        /* An odd number of crossings implies containment! */
        if ( count % 2 )
        {
                return LW_TRUE;
        }
 
        return LW_FALSE;
}

References edge_intersects(), getPoint2d_p(), ll2cart(), LW_FALSE, LW_TRUE, LWDEBUGF, POINTARRAY::npoints, PIR_A_TOUCH_LEFT, PIR_A_TOUCH_RIGHT, PIR_B_TOUCH_RIGHT, PIR_COLINEAR, PIR_INTERSECTS, point3d_equals(), POINT2D::x, and POINT2D::y.

Referenced by lwpoly_covers_point2d(), test_ptarray_contains_point_sphere(), and test_ptarray_contains_point_sphere_iowa().

Here is the call graph for this function:

Here is the caller graph for this function: