PostGIS  2.2.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 3204 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().

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