PostGIS  2.5.0dev-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 757 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().

758 {
759  POINT3D vcp, vs, ve, vp;
760  double vs_dot_vcp, vp_dot_vcp;
761  geog2cart(&(e->start), &vs);
762  geog2cart(&(e->end), &ve);
763  /* Antipodal case, everything is inside. */
764  if ( vs.x == -1.0 * ve.x && vs.y == -1.0 * ve.y && vs.z == -1.0 * ve.z )
765  return LW_TRUE;
766  geog2cart(p, &vp);
767  /* The normalized sum bisects the angle between start and end. */
768  vector_sum(&vs, &ve, &vcp);
769  normalize(&vcp);
770  /* The projection of start onto the center defines the minimum similarity */
771  vs_dot_vcp = dot_product(&vs, &vcp);
772  LWDEBUGF(4,"vs_dot_vcp %.19g",vs_dot_vcp);
773  /* The projection of candidate p onto the center */
774  vp_dot_vcp = dot_product(&vp, &vcp);
775  LWDEBUGF(4,"vp_dot_vcp %.19g",vp_dot_vcp);
776  /* If p is more similar than start then p is inside the cone */
777  LWDEBUGF(4,"fabs(vp_dot_vcp - vs_dot_vcp) %.39g",fabs(vp_dot_vcp - vs_dot_vcp));
778 
779  /*
780  ** We want to test that vp_dot_vcp is >= vs_dot_vcp but there are
781  ** numerical stability issues for values that are very very nearly
782  ** equal. Unfortunately there are also values of vp_dot_vcp that are legitimately
783  ** very close to but still less than vs_dot_vcp which we also need to catch.
784  ** The tolerance of 10-17 seems to do the trick on 32-bit and 64-bit architectures,
785  ** for the test cases here.
786  ** However, tuning the tolerance value feels like a dangerous hack.
787  ** Fundamentally, the problem is that this test is so sensitive.
788  */
789 
790  /* 1.1102230246251565404236316680908203125e-16 */
791 
792  if ( vp_dot_vcp > vs_dot_vcp || fabs(vp_dot_vcp - vs_dot_vcp) < 2e-16 )
793  {
794  LWDEBUG(4, "point is in cone");
795  return LW_TRUE;
796  }
797  LWDEBUG(4, "point is not in cone");
798  return LW_FALSE;
799 }
void normalize(POINT3D *p)
Normalize to a unit vector.
Definition: lwgeodetic.c:584
double y
Definition: liblwgeom.h:342
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
double x
Definition: liblwgeom.h:342
double z
Definition: liblwgeom.h:342
static double dot_product(const POINT3D *p1, const POINT3D *p2)
Convert cartesian coordinates on unit sphere to lon/lat coordinates static void cart2ll(const POINT3D...
Definition: lwgeodetic.c:415
#define LW_FALSE
Definition: liblwgeom.h:76
GEOGRAPHIC_POINT start
Definition: lwgeodetic.h:58
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
GEOGRAPHIC_POINT end
Definition: lwgeodetic.h:59
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesian coordinates on unit sphere.
Definition: lwgeodetic.c:373
void vector_sum(const POINT3D *a, const POINT3D *b, POINT3D *n)
Calculate the sum of two vectors.
Definition: lwgeodetic.c:434
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
Here is the call graph for this function:
Here is the caller graph for this function: