PostGIS  2.2.8dev-r@@SVN_REVISION@@

◆ edge_point_in_cone()

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 738 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().

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