PostGIS  2.5.0dev-r@@SVN_REVISION@@
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 3516 of file lwgeodetic.c.

References genraster::count, 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().

3517 {
3518  POINT3D S1, S2; /* Stab line end points */
3519  POINT3D E1, E2; /* Edge end points (3-space) */
3520  POINT2D p; /* Edge end points (lon/lat) */
3521  uint32_t count = 0, i, inter;
3522 
3523  /* Null input, not enough points for a ring? You ain't closed! */
3524  if ( ! pa || pa->npoints < 4 )
3525  return LW_FALSE;
3526 
3527  /* Set up our stab line */
3528  ll2cart(pt_to_test, &S1);
3529  ll2cart(pt_outside, &S2);
3530 
3531  /* Initialize first point */
3532  getPoint2d_p(pa, 0, &p);
3533  ll2cart(&p, &E1);
3534 
3535  /* Walk every edge and see if the stab line hits it */
3536  for ( i = 1; i < pa->npoints; i++ )
3537  {
3538  LWDEBUGF(4, "testing edge (%d)", i);
3539  LWDEBUGF(4, " start point == POINT(%.12g %.12g)", p.x, p.y);
3540 
3541  /* Read next point. */
3542  getPoint2d_p(pa, i, &p);
3543  ll2cart(&p, &E2);
3544 
3545  /* Skip over too-short edges. */
3546  if ( point3d_equals(&E1, &E2) )
3547  {
3548  continue;
3549  }
3550 
3551  /* Our test point is on an edge end! Point is "in ring" by our definition */
3552  if ( point3d_equals(&S1, &E1) )
3553  {
3554  return LW_TRUE;
3555  }
3556 
3557  /* Calculate relationship between stab line and edge */
3558  inter = edge_intersects(&S1, &S2, &E1, &E2);
3559 
3560  /* We have some kind of interaction... */
3561  if ( inter & PIR_INTERSECTS )
3562  {
3563  /* If the stabline is touching the edge, that implies the test point */
3564  /* is on the edge, so we're done, the point is in (on) the ring. */
3565  if ( (inter & PIR_A_TOUCH_RIGHT) || (inter & PIR_A_TOUCH_LEFT) )
3566  {
3567  return LW_TRUE;
3568  }
3569 
3570  /* It's a touching interaction, disregard all the left-side ones. */
3571  /* It's a co-linear intersection, ignore those. */
3572  if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
3573  {
3574  /* Do nothing, to avoid double counts. */
3575  LWDEBUGF(4," edge (%d) crossed, disregarding to avoid double count", i, count);
3576  }
3577  else
3578  {
3579  /* Increment crossingn count. */
3580  count++;
3581  LWDEBUGF(4," edge (%d) crossed, count == %d", i, count);
3582  }
3583  }
3584  else
3585  {
3586  LWDEBUGF(4," edge (%d) did not cross", i);
3587  }
3588 
3589  /* Increment to next edge */
3590  E1 = E2;
3591  }
3592 
3593  LWDEBUGF(4,"final count == %d", count);
3594 
3595  /* An odd number of crossings implies containment! */
3596  if ( count % 2 )
3597  {
3598  return LW_TRUE;
3599  }
3600 
3601  return LW_FALSE;
3602 }
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:86
static int point3d_equals(const POINT3D *p1, const POINT3D *p2)
Utility function for ptarray_contains_point_sphere()
Definition: lwgeodetic.c:3386
#define PIR_A_TOUCH_RIGHT
Definition: lwgeodetic.h:84
#define PIR_A_TOUCH_LEFT
Definition: lwgeodetic.h:85
unsigned int uint32_t
Definition: uthash.h:78
double x
Definition: liblwgeom.h:327
#define LW_FALSE
Definition: liblwgeom.h:76
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
void ll2cart(const POINT2D *g, POINT3D *p)
Convert lon/lat coordinates to cartesion coordinates on unit sphere.
Definition: lwgeodetic.c:388
int count
Definition: genraster.py:56
uint32_t edge_intersects(const POINT3D *A1, const POINT3D *A2, const POINT3D *B1, const POINT3D *B2)
Returns non-zero if edges A and B interact.
Definition: lwgeodetic.c:3411
double y
Definition: liblwgeom.h:327
int getPoint2d_p(const POINTARRAY *pa, uint32_t n, POINT2D *point)
Definition: lwgeom_api.c:338
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
#define PIR_COLINEAR
Definition: lwgeodetic.h:83
#define PIR_INTERSECTS
Definition: lwgeodetic.h:82
uint32_t npoints
Definition: liblwgeom.h:370

Here is the call graph for this function:

Here is the caller graph for this function: