PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ 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 3215 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().

3216 {
3217  POINT3D S1, S2; /* Stab line end points */
3218  POINT3D E1, E2; /* Edge end points (3-space) */
3219  POINT2D p; /* Edge end points (lon/lat) */
3220  int count = 0, i, inter;
3221 
3222  /* Null input, not enough points for a ring? You ain't closed! */
3223  if ( ! pa || pa->npoints < 4 )
3224  return LW_FALSE;
3225 
3226  /* Set up our stab line */
3227  ll2cart(pt_to_test, &S1);
3228  ll2cart(pt_outside, &S2);
3229 
3230  /* Initialize first point */
3231  getPoint2d_p(pa, 0, &p);
3232  ll2cart(&p, &E1);
3233 
3234  /* Walk every edge and see if the stab line hits it */
3235  for ( i = 1; i < pa->npoints; i++ )
3236  {
3237  LWDEBUGF(4, "testing edge (%d)", i);
3238  LWDEBUGF(4, " start point == POINT(%.12g %.12g)", p.x, p.y);
3239 
3240  /* Read next point. */
3241  getPoint2d_p(pa, i, &p);
3242  ll2cart(&p, &E2);
3243 
3244  /* Skip over too-short edges. */
3245  if ( point3d_equals(&E1, &E2) )
3246  {
3247  continue;
3248  }
3249 
3250  /* Our test point is on an edge end! Point is "in ring" by our definition */
3251  if ( point3d_equals(&S1, &E1) )
3252  {
3253  return LW_TRUE;
3254  }
3255 
3256  /* Calculate relationship between stab line and edge */
3257  inter = edge_intersects(&S1, &S2, &E1, &E2);
3258 
3259  /* We have some kind of interaction... */
3260  if ( inter & PIR_INTERSECTS )
3261  {
3262  /* If the stabline is touching the edge, that implies the test point */
3263  /* is on the edge, so we're done, the point is in (on) the ring. */
3264  if ( (inter & PIR_A_TOUCH_RIGHT) || (inter & PIR_A_TOUCH_LEFT) )
3265  {
3266  return LW_TRUE;
3267  }
3268 
3269  /* It's a touching interaction, disregard all the left-side ones. */
3270  /* It's a co-linear intersection, ignore those. */
3271  if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
3272  {
3273  /* Do nothing, to avoid double counts. */
3274  LWDEBUGF(4," edge (%d) crossed, disregarding to avoid double count", i, count);
3275  }
3276  else
3277  {
3278  /* Increment crossingn count. */
3279  count++;
3280  LWDEBUGF(4," edge (%d) crossed, count == %d", i, count);
3281  }
3282  }
3283  else
3284  {
3285  LWDEBUGF(4," edge (%d) did not cross", i);
3286  }
3287 
3288  /* Increment to next edge */
3289  E1 = E2;
3290  }
3291 
3292  LWDEBUGF(4,"final count == %d", count);
3293 
3294  /* An odd number of crossings implies containment! */
3295  if ( count % 2 )
3296  {
3297  return LW_TRUE;
3298  }
3299 
3300  return LW_FALSE;
3301 }
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:86
int npoints
Definition: liblwgeom.h:370
static int point3d_equals(const POINT3D *p1, const POINT3D *p2)
Utility function for ptarray_contains_point_sphere()
Definition: lwgeodetic.c:3085
#define PIR_A_TOUCH_RIGHT
Definition: lwgeodetic.h:84
#define PIR_A_TOUCH_LEFT
Definition: lwgeodetic.h:85
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
double y
Definition: liblwgeom.h:327
int getPoint2d_p(const POINTARRAY *pa, int n, POINT2D *point)
Definition: lwgeom_api.c:461
int 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:3110
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
#define PIR_COLINEAR
Definition: lwgeodetic.h:83
#define PIR_INTERSECTS
Definition: lwgeodetic.h:82
Here is the call graph for this function:
Here is the caller graph for this function: