PostGIS  3.1.6dev-r@@SVN_REVISION@@

◆ lw_dist2d_seg_arc()

int lw_dist2d_seg_arc ( const POINT2D A1,
const POINT2D A2,
const POINT2D B1,
const POINT2D B2,
const POINT2D B3,
DISTPTS dl 
)

Calculate the shortest distance between an arc and an edge.

Line/circle approach from http://stackoverflow.com/questions/1073336/circle-line-collision-detection

Definition at line 1340 of file measures.c.

1346 {
1347  POINT2D C; /* center of arc circle */
1348  double radius_C; /* radius of arc circle */
1349  POINT2D D; /* point on A closest to C */
1350  double dist_C_D; /* distance from C to D */
1351  int pt_in_arc, pt_in_seg;
1352  DISTPTS dltmp;
1353 
1354  /* Bail out on crazy modes */
1355  if (dl->mode < 0)
1356  lwerror("lw_dist2d_seg_arc does not support maxdistance mode");
1357 
1358  /* What if the "arc" is a point? */
1359  if (lw_arc_is_pt(B1, B2, B3))
1360  return lw_dist2d_pt_seg(B1, A1, A2, dl);
1361 
1362  /* Calculate center and radius of the circle. */
1363  radius_C = lw_arc_center(B1, B2, B3, &C);
1364 
1365  /* This "arc" is actually a line (B2 is collinear with B1,B3) */
1366  if (radius_C < 0.0)
1367  return lw_dist2d_seg_seg(A1, A2, B1, B3, dl);
1368 
1369  /* Calculate distance between the line and circle center */
1371  if (lw_dist2d_pt_seg(&C, A1, A2, &dltmp) == LW_FALSE)
1372  lwerror("lw_dist2d_pt_seg failed in lw_dist2d_seg_arc");
1373 
1374  D = dltmp.p1;
1375  dist_C_D = dltmp.distance;
1376 
1377  /* Line intersects circle, maybe arc intersects edge? */
1378  /* If so, that's the closest point. */
1379  /* If not, the closest point is one of the end points of A */
1380  if (dist_C_D < radius_C)
1381  {
1382  double length_A; /* length of the segment A */
1383  POINT2D E, F; /* points of intersection of edge A and circle(B) */
1384  double dist_D_EF; /* distance from D to E or F (same distance both ways) */
1385 
1386  dist_D_EF = sqrt(radius_C * radius_C - dist_C_D * dist_C_D);
1387  length_A = sqrt((A2->x - A1->x) * (A2->x - A1->x) + (A2->y - A1->y) * (A2->y - A1->y));
1388 
1389  /* Point of intersection E */
1390  E.x = D.x - (A2->x - A1->x) * dist_D_EF / length_A;
1391  E.y = D.y - (A2->y - A1->y) * dist_D_EF / length_A;
1392  /* Point of intersection F */
1393  F.x = D.x + (A2->x - A1->x) * dist_D_EF / length_A;
1394  F.y = D.y + (A2->y - A1->y) * dist_D_EF / length_A;
1395 
1396  /* If E is within A and within B then it's an intersection point */
1397  pt_in_arc = lw_pt_in_arc(&E, B1, B2, B3);
1398  pt_in_seg = lw_pt_in_seg(&E, A1, A2);
1399 
1400  if (pt_in_arc && pt_in_seg)
1401  {
1402  lw_dist2d_distpts_set(dl, 0.0, &E, &E);
1403  return LW_TRUE;
1404  }
1405 
1406  /* If F is within A and within B then it's an intersection point */
1407  pt_in_arc = lw_pt_in_arc(&F, B1, B2, B3);
1408  pt_in_seg = lw_pt_in_seg(&F, A1, A2);
1409 
1410  if (pt_in_arc && pt_in_seg)
1411  {
1412  lw_dist2d_distpts_set(dl, 0.0, &F, &F);
1413  return LW_TRUE;
1414  }
1415  }
1416 
1417  /* Line grazes circle, maybe arc intersects edge? */
1418  /* If so, grazing point is the closest point. */
1419  /* If not, the closest point is one of the end points of A */
1420  else if (dist_C_D == radius_C)
1421  {
1422  /* Closest point D is also the point of grazing */
1423  pt_in_arc = lw_pt_in_arc(&D, B1, B2, B3);
1424  pt_in_seg = lw_pt_in_seg(&D, A1, A2);
1425 
1426  /* Is D contained in both A and B? */
1427  if (pt_in_arc && pt_in_seg)
1428  {
1429  lw_dist2d_distpts_set(dl, 0.0, &D, &D);
1430  return LW_TRUE;
1431  }
1432  }
1433  /* Line misses circle. */
1434  /* If closest point to A on circle is within B, then that's the closest */
1435  /* Otherwise, the closest point will be an end point of A */
1436  else
1437  {
1438  POINT2D G; /* Point on circle closest to A */
1439  G.x = C.x + (D.x - C.x) * radius_C / dist_C_D;
1440  G.y = C.y + (D.y - C.y) * radius_C / dist_C_D;
1441 
1442  pt_in_arc = lw_pt_in_arc(&G, B1, B2, B3);
1443  pt_in_seg = lw_pt_in_seg(&D, A1, A2);
1444 
1445  /* Closest point is on the interior of A and B */
1446  if (pt_in_arc && pt_in_seg)
1447  return lw_dist2d_pt_pt(&D, &G, dl);
1448  }
1449 
1450  /* Now we test the many combinations of end points with either */
1451  /* arcs or edges. Each previous check determined if the closest */
1452  /* potential point was within the arc/segment inscribed on the */
1453  /* line/circle holding the arc/segment. */
1454 
1455  /* Closest point is in the arc, but not in the segment, so */
1456  /* one of the segment end points must be the closest. */
1457  if (pt_in_arc && !pt_in_seg)
1458  {
1459  lw_dist2d_pt_arc(A1, B1, B2, B3, dl);
1460  lw_dist2d_pt_arc(A2, B1, B2, B3, dl);
1461  return LW_TRUE;
1462  }
1463  /* or, one of the arc end points is the closest */
1464  else if (pt_in_seg && !pt_in_arc)
1465  {
1466  lw_dist2d_pt_seg(B1, A1, A2, dl);
1467  lw_dist2d_pt_seg(B3, A1, A2, dl);
1468  return LW_TRUE;
1469  }
1470  /* Finally, one of the end-point to end-point combos is the closest. */
1471  else
1472  {
1473  lw_dist2d_pt_pt(A1, B1, dl);
1474  lw_dist2d_pt_pt(A1, B3, dl);
1475  lw_dist2d_pt_pt(A2, B1, dl);
1476  lw_dist2d_pt_pt(A2, B3, dl);
1477  return LW_TRUE;
1478  }
1479 
1480  return LW_FALSE;
1481 }
#define LW_FALSE
Definition: liblwgeom.h:108
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:107
double lw_arc_center(const POINT2D *p1, const POINT2D *p2, const POINT2D *p3, POINT2D *result)
Determines the center of the circle defined by the three given points.
Definition: lwalgorithm.c:229
int lw_pt_in_seg(const POINT2D *P, const POINT2D *A1, const POINT2D *A2)
Returns true if P is between A1/A2.
Definition: lwalgorithm.c:96
int lw_arc_is_pt(const POINT2D *A1, const POINT2D *A2, const POINT2D *A3)
Returns true if arc A is actually a point (all vertices are the same) .
Definition: lwalgorithm.c:106
int lw_pt_in_arc(const POINT2D *P, const POINT2D *A1, const POINT2D *A2, const POINT2D *A3)
Returns true if P is on the same side of the plane partition defined by A1/A3 as A2 is.
Definition: lwalgorithm.c:86
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
int lw_dist2d_pt_arc(const POINT2D *P, const POINT2D *A1, const POINT2D *A2, const POINT2D *A3, DISTPTS *dl)
Definition: measures.c:1484
static void lw_dist2d_distpts_set(DISTPTS *dl, double distance, const POINT2D *p1, const POINT2D *p2)
Definition: measures.c:78
int lw_dist2d_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B, DISTPTS *dl)
lw_dist2d_comp from p to line A->B This one is now sending every occasion to lw_dist2d_pt_pt Before i...
Definition: measures.c:2250
int lw_dist2d_seg_seg(const POINT2D *A, const POINT2D *B, const POINT2D *C, const POINT2D *D, DISTPTS *dl)
Finds the shortest distance between two segments.
Definition: measures.c:1863
void lw_dist2d_distpts_init(DISTPTS *dl, int mode)
Definition: measures.c:64
int lw_dist2d_pt_pt(const POINT2D *thep1, const POINT2D *thep2, DISTPTS *dl)
Compares incoming points and stores the points closest to each other or most far away from each other...
Definition: measures.c:2308
#define DIST_MIN
Definition: measures.h:44
POINT2D p1
Definition: measures.h:52
int mode
Definition: measures.h:54
double distance
Definition: measures.h:51
Structure used in distance-calculations.
Definition: measures.h:50
double y
Definition: liblwgeom.h:404
double x
Definition: liblwgeom.h:404

References DIST_MIN, DISTPTS::distance, lw_arc_center(), lw_arc_is_pt(), lw_dist2d_distpts_init(), lw_dist2d_distpts_set(), lw_dist2d_pt_arc(), lw_dist2d_pt_pt(), lw_dist2d_pt_seg(), lw_dist2d_seg_seg(), LW_FALSE, lw_pt_in_arc(), lw_pt_in_seg(), LW_TRUE, lwerror(), DISTPTS::mode, DISTPTS::p1, POINT2D::x, and POINT2D::y.

Referenced by lw_dist2d_arc_arc(), lw_dist2d_ptarray_ptarrayarc(), rect_leaf_node_distance(), rect_leaf_node_intersects(), and test_lw_dist2d_seg_arc().

Here is the call graph for this function:
Here is the caller graph for this function: