PostGIS  2.5.1dev-r@@SVN_REVISION@@

◆ edge_intersection()

int edge_intersection ( const GEOGRAPHIC_EDGE e1,
const GEOGRAPHIC_EDGE e2,
GEOGRAPHIC_POINT g 
)

Returns true if an intersection can be calculated, and places it in *g.

Returns false otherwise.

Definition at line 1096 of file lwgeodetic.c.

References dot_product(), edge_contains_point(), GEOGRAPHIC_EDGE::end, FP_EQUALS, geographic_point_equals(), GEOGRAPHIC_POINT::lat, GEOGRAPHIC_POINT::lon, LW_FALSE, LW_TRUE, LWDEBUG, LWDEBUGF, normalize(), rad2deg, robust_cross_product(), GEOGRAPHIC_EDGE::start, unit_normal(), POINT3D::x, POINT3D::y, and POINT3D::z.

Referenced by circ_tree_distance_tree_internal(), and test_edge_intersection().

1097 {
1098  POINT3D ea, eb, v;
1099  LWDEBUGF(4, "e1 start(%.20g %.20g) end(%.20g %.20g)", e1->start.lat, e1->start.lon, e1->end.lat, e1->end.lon);
1100  LWDEBUGF(4, "e2 start(%.20g %.20g) end(%.20g %.20g)", e2->start.lat, e2->start.lon, e2->end.lat, e2->end.lon);
1101 
1102  LWDEBUGF(4, "e1 start(%.20g %.20g) end(%.20g %.20g)", rad2deg(e1->start.lon), rad2deg(e1->start.lat), rad2deg(e1->end.lon), rad2deg(e1->end.lat));
1103  LWDEBUGF(4, "e2 start(%.20g %.20g) end(%.20g %.20g)", rad2deg(e2->start.lon), rad2deg(e2->start.lat), rad2deg(e2->end.lon), rad2deg(e2->end.lat));
1104 
1105  if ( geographic_point_equals(&(e1->start), &(e2->start)) )
1106  {
1107  *g = e1->start;
1108  return LW_TRUE;
1109  }
1110  if ( geographic_point_equals(&(e1->end), &(e2->end)) )
1111  {
1112  *g = e1->end;
1113  return LW_TRUE;
1114  }
1115  if ( geographic_point_equals(&(e1->end), &(e2->start)) )
1116  {
1117  *g = e1->end;
1118  return LW_TRUE;
1119  }
1120  if ( geographic_point_equals(&(e1->start), &(e2->end)) )
1121  {
1122  *g = e1->start;
1123  return LW_TRUE;
1124  }
1125 
1126  robust_cross_product(&(e1->start), &(e1->end), &ea);
1127  normalize(&ea);
1128  robust_cross_product(&(e2->start), &(e2->end), &eb);
1129  normalize(&eb);
1130  LWDEBUGF(4, "e1 cross product == POINT(%.12g %.12g %.12g)", ea.x, ea.y, ea.z);
1131  LWDEBUGF(4, "e2 cross product == POINT(%.12g %.12g %.12g)", eb.x, eb.y, eb.z);
1132  LWDEBUGF(4, "fabs(dot_product(ea, eb)) == %.14g", fabs(dot_product(&ea, &eb)));
1133  if ( FP_EQUALS(fabs(dot_product(&ea, &eb)), 1.0) )
1134  {
1135  LWDEBUGF(4, "parallel edges found! dot_product = %.12g", dot_product(&ea, &eb));
1136  /* Parallel (maybe equal) edges! */
1137  /* Hack alert, only returning ONE end of the edge right now, most do better later. */
1138  /* Hack alert #2, returning a value of 2 to indicate a co-linear crossing event. */
1139  if ( edge_contains_point(e1, &(e2->start)) )
1140  {
1141  *g = e2->start;
1142  return 2;
1143  }
1144  if ( edge_contains_point(e1, &(e2->end)) )
1145  {
1146  *g = e2->end;
1147  return 2;
1148  }
1149  if ( edge_contains_point(e2, &(e1->start)) )
1150  {
1151  *g = e1->start;
1152  return 2;
1153  }
1154  if ( edge_contains_point(e2, &(e1->end)) )
1155  {
1156  *g = e1->end;
1157  return 2;
1158  }
1159  }
1160  unit_normal(&ea, &eb, &v);
1161  LWDEBUGF(4, "v == POINT(%.12g %.12g %.12g)", v.x, v.y, v.z);
1162  g->lat = atan2(v.z, sqrt(v.x * v.x + v.y * v.y));
1163  g->lon = atan2(v.y, v.x);
1164  LWDEBUGF(4, "g == GPOINT(%.12g %.12g)", g->lat, g->lon);
1165  LWDEBUGF(4, "g == POINT(%.12g %.12g)", rad2deg(g->lon), rad2deg(g->lat));
1166  if ( edge_contains_point(e1, g) && edge_contains_point(e2, g) )
1167  {
1168  return LW_TRUE;
1169  }
1170  else
1171  {
1172  LWDEBUG(4, "flipping point to other side of sphere");
1173  g->lat = -1.0 * g->lat;
1174  g->lon = g->lon + M_PI;
1175  if ( g->lon > M_PI )
1176  {
1177  g->lon = -1.0 * (2.0 * M_PI - g->lon);
1178  }
1179  if ( edge_contains_point(e1, g) && edge_contains_point(e2, g) )
1180  {
1181  return LW_TRUE;
1182  }
1183  }
1184  return LW_FALSE;
1185 }
void robust_cross_product(const GEOGRAPHIC_POINT *p, const GEOGRAPHIC_POINT *q, POINT3D *a)
Computes the cross product of two vectors using their lat, lng representations.
Definition: lwgeodetic.c:603
void normalize(POINT3D *p)
Normalize to a unit vector.
Definition: lwgeodetic.c:584
int edge_contains_point(const GEOGRAPHIC_EDGE *e, const GEOGRAPHIC_POINT *p)
Returns true if the point p is on the minor edge defined by the end points of e.
Definition: lwgeodetic.c:1003
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
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:510
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
#define rad2deg(r)
Definition: lwgeodetic.h:75
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
int geographic_point_equals(const GEOGRAPHIC_POINT *g1, const GEOGRAPHIC_POINT *g2)
Definition: lwgeodetic.c:161
#define FP_EQUALS(A, B)
#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: