PostGIS  2.5.0dev-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 3411 of file lwgeodetic.c.

References dot_product(), dot_product_side(), FP_EQUALS, PIR_A_TOUCH_LEFT, PIR_A_TOUCH_RIGHT, PIR_B_TOUCH_LEFT, PIR_B_TOUCH_RIGHT, PIR_COLINEAR, PIR_INTERSECTS, PIR_NO_INTERACT, point_in_cone(), unit_normal(), and vector_scale().

Referenced by circ_tree_contains_point(), circ_tree_distance_tree_internal(), lwpoly_intersects_line(), ptarray_contains_point_sphere(), ptarray_distance_spheroid(), and test_edge_intersects().

3412 {
3413  POINT3D AN, BN, VN; /* Normals to plane A and plane B */
3414  double ab_dot;
3415  int a1_side, a2_side, b1_side, b2_side;
3416  int rv = PIR_NO_INTERACT;
3417 
3418  /* Normals to the A-plane and B-plane */
3419  unit_normal(A1, A2, &AN);
3420  unit_normal(B1, B2, &BN);
3421 
3422  /* Are A-plane and B-plane basically the same? */
3423  ab_dot = dot_product(&AN, &BN);
3424  if ( FP_EQUALS(fabs(ab_dot), 1.0) )
3425  {
3426  /* Co-linear case */
3427  if ( point_in_cone(A1, A2, B1) || point_in_cone(A1, A2, B2) ||
3428  point_in_cone(B1, B2, A1) || point_in_cone(B1, B2, A2) )
3429  {
3430  rv |= PIR_INTERSECTS;
3431  rv |= PIR_COLINEAR;
3432  }
3433  return rv;
3434  }
3435 
3436  /* What side of plane-A and plane-B do the end points */
3437  /* of A and B fall? */
3438  a1_side = dot_product_side(&BN, A1);
3439  a2_side = dot_product_side(&BN, A2);
3440  b1_side = dot_product_side(&AN, B1);
3441  b2_side = dot_product_side(&AN, B2);
3442 
3443  /* Both ends of A on the same side of plane B. */
3444  if ( a1_side == a2_side && a1_side != 0 )
3445  {
3446  /* No intersection. */
3447  return PIR_NO_INTERACT;
3448  }
3449 
3450  /* Both ends of B on the same side of plane A. */
3451  if ( b1_side == b2_side && b1_side != 0 )
3452  {
3453  /* No intersection. */
3454  return PIR_NO_INTERACT;
3455  }
3456 
3457  /* A straddles B and B straddles A, so... */
3458  if ( a1_side != a2_side && (a1_side + a2_side) == 0 &&
3459  b1_side != b2_side && (b1_side + b2_side) == 0 )
3460  {
3461  /* Have to check if intersection point is inside both arcs */
3462  unit_normal(&AN, &BN, &VN);
3463  if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
3464  {
3465  return PIR_INTERSECTS;
3466  }
3467 
3468  /* Have to check if intersection point is inside both arcs */
3469  vector_scale(&VN, -1);
3470  if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
3471  {
3472  return PIR_INTERSECTS;
3473  }
3474 
3475  return PIR_NO_INTERACT;
3476  }
3477 
3478  /* The rest are all intersects variants... */
3479  rv |= PIR_INTERSECTS;
3480 
3481  /* A touches B */
3482  if ( a1_side == 0 )
3483  {
3484  /* Touches at A1, A2 is on what side? */
3485  rv |= (a2_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
3486  }
3487  else if ( a2_side == 0 )
3488  {
3489  /* Touches at A2, A1 is on what side? */
3490  rv |= (a1_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
3491  }
3492 
3493  /* B touches A */
3494  if ( b1_side == 0 )
3495  {
3496  /* Touches at B1, B2 is on what side? */
3497  rv |= (b2_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
3498  }
3499  else if ( b2_side == 0 )
3500  {
3501  /* Touches at B2, B1 is on what side? */
3502  rv |= (b1_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
3503  }
3504 
3505  return rv;
3506 }
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:86
#define PIR_A_TOUCH_RIGHT
Definition: lwgeodetic.h:84
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:3396
static void vector_scale(POINT3D *n, double scale)
Scale a vector out by a factor.
Definition: lwgeodetic.c:452
#define PIR_A_TOUCH_LEFT
Definition: lwgeodetic.h:85
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:506
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:411
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:3358
#define FP_EQUALS(A, B)
#define PIR_NO_INTERACT
Bitmask elements for edge_intersects() return value.
Definition: lwgeodetic.h:81
#define PIR_B_TOUCH_LEFT
Definition: lwgeodetic.h:87
#define PIR_COLINEAR
Definition: lwgeodetic.h:83
#define PIR_INTERSECTS
Definition: lwgeodetic.h:82
Here is the call graph for this function:
Here is the caller graph for this function: