ptarray_contains_point()

int ptarray_contains_point	(	const POINTARRAY *	pa,
		const POINT2D *	pt
	)

The following is based on the "Fast Winding Number Inclusion of a Point in a Polygon" algorithm by Dan Sunday.

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm#Winding%20Number

Return:

• LW_INSIDE (1) if the point is inside the POINTARRAY
• LW_BOUNDARY (0) if it is on the boundary.
• LW_OUTSIDE (-1) if it is outside

Definition at line 746 of file ptarray.c.

{
        const POINT2D *seg1, *seg2;
        int wn = 0;
 
        seg1 = getPoint2d_cp(pa, 0);
        seg2 = getPoint2d_cp(pa, pa->npoints-1);
        if (!p2d_same(seg1, seg2))
                lwerror("ptarray_contains_point called on unclosed ring");
 
        for (uint32_t i = 1; i < pa->npoints; i++)
        {
                double side, ymin, ymax;
 
                seg2 = getPoint2d_cp(pa, i);
 
                /* Zero length segments are ignored. */
                if (p2d_same(seg1, seg2))
                {
                        seg1 = seg2;
                        continue;
                }
 
                ymin = FP_MIN(seg1->y, seg2->y);
                ymax = FP_MAX(seg1->y, seg2->y);
 
                /* Only test segments in our vertical range */
                if (pt->y > ymax || pt->y < ymin)
                {
                        seg1 = seg2;
                        continue;
                }
 
                side = lw_segment_side(seg1, seg2, pt);
 
                /*
                * A point on the boundary of a ring is not contained.
                * WAS: if (fabs(side) < 1e-12), see #852
                */
                if ((side == 0) && lw_pt_in_seg(pt, seg1, seg2))
                {
                        return LW_BOUNDARY;
                }
 
                /*
                * If the point is to the left of the line, and it's rising,
                * then the line is to the right of the point and
                * circling counter-clockwise, so increment.
                */
                if ((side < 0) && (seg1->y <= pt->y) && (pt->y < seg2->y))
                {
                        wn++;
                }
 
                /*
                * If the point is to the right of the line, and it's falling,
                * then the line is to the right of the point and circling
                * clockwise, so decrement.
                */
                else if ( (side > 0) && (seg2->y <= pt->y) && (pt->y < seg1->y) )
                {
                        wn--;
                }
 
                seg1 = seg2;
        }
 
        /* wn == 0 => Outside, wn != 0 => Inside */
        return wn == 0 ? LW_OUTSIDE : LW_INSIDE;
}

References FP_MAX, FP_MIN, getPoint2d_cp(), LW_BOUNDARY, LW_INSIDE, LW_OUTSIDE, lw_pt_in_seg(), lw_segment_side(), lwerror(), POINTARRAY::npoints, p2d_same(), and POINT2D::y.

Referenced by _lwt_AddFaceSplit(), lw_dist2d_line_poly(), lw_dist2d_line_tri(), lw_dist2d_point_poly(), lw_dist2d_point_tri(), lw_dist2d_poly_poly(), lw_dist2d_tri_circstring(), lw_dist2d_tri_poly(), lw_dist2d_tri_tri(), lwgeom_contains_point(), lwgeom_solid_contains_lwgeom(), lwpoly_contains_point(), and test_ptarray_contains_point().

Here is the call graph for this function:

Here is the caller graph for this function: