PostGIS  2.1.10dev-r@@SVN_REVISION@@
int edge_point_in_cone ( const GEOGRAPHIC_EDGE e,
const GEOGRAPHIC_POINT p 
)

Returns true if the point p is inside the cone defined by the two ends of the edge e.

Definition at line 737 of file lwgeodetic.c.

References dot_product(), GEOGRAPHIC_EDGE::end, geog2cart(), LW_FALSE, LW_TRUE, LWDEBUG, LWDEBUGF, normalize(), GEOGRAPHIC_EDGE::start, vector_sum(), POINT3D::x, POINT3D::y, and POINT3D::z.

Referenced by edge_contains_point().

738 {
739  POINT3D vcp, vs, ve, vp;
740  double vs_dot_vcp, vp_dot_vcp;
741  geog2cart(&(e->start), &vs);
742  geog2cart(&(e->end), &ve);
743  /* Antipodal case, everything is inside. */
744  if ( vs.x == -1.0 * ve.x && vs.y == -1.0 * ve.y && vs.z == -1.0 * ve.z )
745  return LW_TRUE;
746  geog2cart(p, &vp);
747  /* The normalized sum bisects the angle between start and end. */
748  vector_sum(&vs, &ve, &vcp);
749  normalize(&vcp);
750  /* The projection of start onto the center defines the minimum similarity */
751  vs_dot_vcp = dot_product(&vs, &vcp);
752  LWDEBUGF(4,"vs_dot_vcp %.19g",vs_dot_vcp);
753  /* The projection of candidate p onto the center */
754  vp_dot_vcp = dot_product(&vp, &vcp);
755  LWDEBUGF(4,"vp_dot_vcp %.19g",vp_dot_vcp);
756  /* If p is more similar than start then p is inside the cone */
757  LWDEBUGF(4,"fabs(vp_dot_vcp - vs_dot_vcp) %.39g",fabs(vp_dot_vcp - vs_dot_vcp));
758 
759  /*
760  ** We want to test that vp_dot_vcp is >= vs_dot_vcp but there are
761  ** numerical stability issues for values that are very very nearly
762  ** equal. Unfortunately there are also values of vp_dot_vcp that are legitimately
763  ** very close to but still less than vs_dot_vcp which we also need to catch.
764  ** The tolerance of 10-17 seems to do the trick on 32-bit and 64-bit architectures,
765  ** for the test cases here.
766  ** However, tuning the tolerance value feels like a dangerous hack.
767  ** Fundamentally, the problem is that this test is so sensitive.
768  */
769 
770  /* 1.1102230246251565404236316680908203125e-16 */
771 
772  if ( vp_dot_vcp > vs_dot_vcp || fabs(vp_dot_vcp - vs_dot_vcp) < 2e-16 )
773  {
774  LWDEBUG(4, "point is in cone");
775  return LW_TRUE;
776  }
777  LWDEBUG(4, "point is not in cone");
778  return LW_FALSE;
779 }
void normalize(POINT3D *p)
Normalize to a unit vector.
Definition: lwgeodetic.c:564
double y
Definition: liblwgeom.h:296
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
double x
Definition: liblwgeom.h:296
double z
Definition: liblwgeom.h:296
static double dot_product(const POINT3D *p1, const POINT3D *p2)
Convert cartesion coordinates on unit sphere to lon/lat coordinates static void cart2ll(const POINT3D...
Definition: lwgeodetic.c:397
#define LW_FALSE
Definition: liblwgeom.h:52
GEOGRAPHIC_POINT start
Definition: lwgeodetic.h:44
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:51
GEOGRAPHIC_POINT end
Definition: lwgeodetic.h:45
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesion coordinates on unit sphere.
Definition: lwgeodetic.c:355
void vector_sum(const POINT3D *a, const POINT3D *b, POINT3D *n)
Calculate the sum of two vectors.
Definition: lwgeodetic.c:416
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55

Here is the call graph for this function:

Here is the caller graph for this function: