PostGIS  2.1.10dev-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 3201 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().

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

Here is the call graph for this function:

Here is the caller graph for this function: