PostGIS  2.5.7dev-r@@SVN_REVISION@@

## ◆ edge_intersects()

 uint32_t edge_intersects ( const POINT3D * A1, const POINT3D * A2, const POINT3D * B1, const POINT3D * B2 )

Returns non-zero if edges A and B interact.

The type of interaction is given in the return value with the bitmask elements defined above.

Definition at line 3540 of file lwgeodetic.c.

3541 {
3542  POINT3D AN, BN, VN; /* Normals to plane A and plane B */
3543  double ab_dot;
3544  int a1_side, a2_side, b1_side, b2_side;
3545  int rv = PIR_NO_INTERACT;
3546
3547  /* Normals to the A-plane and B-plane */
3548  unit_normal(A1, A2, &AN);
3549  unit_normal(B1, B2, &BN);
3550
3551  /* Are A-plane and B-plane basically the same? */
3552  ab_dot = dot_product(&AN, &BN);
3553  if ( FP_EQUALS(fabs(ab_dot), 1.0) )
3554  {
3555  /* Co-linear case */
3556  if ( point_in_cone(A1, A2, B1) || point_in_cone(A1, A2, B2) ||
3557  point_in_cone(B1, B2, A1) || point_in_cone(B1, B2, A2) )
3558  {
3559  rv |= PIR_INTERSECTS;
3560  rv |= PIR_COLINEAR;
3561  }
3562  return rv;
3563  }
3564
3565  /* What side of plane-A and plane-B do the end points */
3566  /* of A and B fall? */
3567  a1_side = dot_product_side(&BN, A1);
3568  a2_side = dot_product_side(&BN, A2);
3569  b1_side = dot_product_side(&AN, B1);
3570  b2_side = dot_product_side(&AN, B2);
3571
3572  /* Both ends of A on the same side of plane B. */
3573  if ( a1_side == a2_side && a1_side != 0 )
3574  {
3575  /* No intersection. */
3576  return PIR_NO_INTERACT;
3577  }
3578
3579  /* Both ends of B on the same side of plane A. */
3580  if ( b1_side == b2_side && b1_side != 0 )
3581  {
3582  /* No intersection. */
3583  return PIR_NO_INTERACT;
3584  }
3585
3586  /* A straddles B and B straddles A, so... */
3587  if ( a1_side != a2_side && (a1_side + a2_side) == 0 &&
3588  b1_side != b2_side && (b1_side + b2_side) == 0 )
3589  {
3590  /* Have to check if intersection point is inside both arcs */
3591  unit_normal(&AN, &BN, &VN);
3592  if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
3593  {
3594  return PIR_INTERSECTS;
3595  }
3596
3597  /* Have to check if intersection point is inside both arcs */
3598  vector_scale(&VN, -1);
3599  if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
3600  {
3601  return PIR_INTERSECTS;
3602  }
3603
3604  return PIR_NO_INTERACT;
3605  }
3606
3607  /* The rest are all intersects variants... */
3608  rv |= PIR_INTERSECTS;
3609
3610  /* A touches B */
3611  if ( a1_side == 0 )
3612  {
3613  /* Touches at A1, A2 is on what side? */
3614  rv |= (a2_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
3615  }
3616  else if ( a2_side == 0 )
3617  {
3618  /* Touches at A2, A1 is on what side? */
3619  rv |= (a1_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
3620  }
3621
3622  /* B touches A */
3623  if ( b1_side == 0 )
3624  {
3625  /* Touches at B1, B2 is on what side? */
3626  rv |= (b2_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
3627  }
3628  else if ( b2_side == 0 )
3629  {
3630  /* Touches at B2, B1 is on what side? */
3631  rv |= (b1_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
3632  }
3633
3634  return rv;
3635 }
#define FP_EQUALS(A, B)
static int point_in_cone(const POINT3D *A1, const POINT3D *A2, const POINT3D *P)
Utility function for checking if P is within the cone defined by A1/A2.
Definition: lwgeodetic.c:3459
void vector_scale(POINT3D *n, double scale)
Scale a vector out by a factor.
Definition: lwgeodetic.c:487
static int dot_product_side(const POINT3D *p, const POINT3D *q)
Utility function for edge_intersects(), signum with a tolerance in determining if the value is zero.
Definition: lwgeodetic.c:3525
void unit_normal(const POINT3D *P1, const POINT3D *P2, POINT3D *normal)
Calculates the unit normal to two vectors, trying to avoid problems with over-narrow or over-wide cas...
Definition: lwgeodetic.c:541
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:446
#define PIR_A_TOUCH_LEFT
Definition: lwgeodetic.h:90
#define PIR_COLINEAR
Definition: lwgeodetic.h:88
#define PIR_INTERSECTS
Definition: lwgeodetic.h:87
#define PIR_A_TOUCH_RIGHT
Definition: lwgeodetic.h:89
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:91
#define PIR_B_TOUCH_LEFT
Definition: lwgeodetic.h:92
#define PIR_NO_INTERACT
Bitmask elements for edge_intersects() return value.
Definition: lwgeodetic.h:86
Here is the call graph for this function:
Here is the caller graph for this function: