PostGIS  2.1.10dev-r@@SVN_REVISION@@
 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 1248 of file measures.c.

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

1249 {
1250  POINT2D C; /* center of arc circle */
1251  double radius_C; /* radius of arc circle */
1252  POINT2D D; /* point on A closest to C */
1253  double dist_C_D; /* distance from C to D */
1254  int pt_in_arc, pt_in_seg;
1255  DISTPTS dltmp;
1256
1257  /* Bail out on crazy modes */
1258  if ( dl->mode < 0 )
1259  lwerror("lw_dist2d_seg_arc does not support maxdistance mode");
1260
1261  /* What if the "arc" is a point? */
1262  if ( lw_arc_is_pt(B1, B2, B3) )
1263  return lw_dist2d_pt_seg(B1, A1, A2, dl);
1264
1265  /* Calculate center and radius of the circle. */
1266  radius_C = lw_arc_center(B1, B2, B3, &C);
1267
1268  /* This "arc" is actually a line (B2 is colinear with B1,B3) */
1269  if ( radius_C < 0.0 )
1270  return lw_dist2d_seg_seg(A1, A2, B1, B3, dl);
1271
1272  /* Calculate distance between the line and circle center */
1274  if ( lw_dist2d_pt_seg(&C, A1, A2, &dltmp) == LW_FALSE )
1275  lwerror("lw_dist2d_pt_seg failed in lw_dist2d_seg_arc");
1276
1277  D = dltmp.p1;
1278  dist_C_D = dltmp.distance;
1279
1280  /* Line intersects circle, maybe arc intersects edge? */
1281  /* If so, that's the closest point. */
1282  /* If not, the closest point is one of the end points of A */
1283  if ( dist_C_D < radius_C )
1284  {
1285  double length_A; /* length of the segment A */
1286  POINT2D E, F; /* points of interection of edge A and circle(B) */
1287  double dist_D_EF; /* distance from D to E or F (same distance both ways) */
1288
1289  dist_D_EF = sqrt(radius_C*radius_C - dist_C_D*dist_C_D);
1290  length_A = sqrt((A2->x-A1->x)*(A2->x-A1->x)+(A2->y-A1->y)*(A2->y-A1->y));
1291
1292  /* Point of intersection E */
1293  E.x = D.x - (A2->x-A1->x) * dist_D_EF / length_A;
1294  E.y = D.y - (A2->y-A1->y) * dist_D_EF / length_A;
1295  /* Point of intersection F */
1296  F.x = D.x + (A2->x-A1->x) * dist_D_EF / length_A;
1297  F.y = D.y + (A2->y-A1->y) * dist_D_EF / length_A;
1298
1299
1300  /* If E is within A and within B then it's an interesction point */
1301  pt_in_arc = lw_pt_in_arc(&E, B1, B2, B3);
1302  pt_in_seg = lw_pt_in_seg(&E, A1, A2);
1303
1304  if ( pt_in_arc && pt_in_seg )
1305  {
1306  dl->distance = 0.0;
1307  dl->p1 = E;
1308  dl->p2 = E;
1309  return LW_TRUE;
1310  }
1311
1312  /* If F is within A and within B then it's an interesction point */
1313  pt_in_arc = lw_pt_in_arc(&F, B1, B2, B3);
1314  pt_in_seg = lw_pt_in_seg(&F, A1, A2);
1315
1316  if ( pt_in_arc && pt_in_seg )
1317  {
1318  dl->distance = 0.0;
1319  dl->p1 = F;
1320  dl->p2 = F;
1321  return LW_TRUE;
1322  }
1323  }
1324
1325  /* Line grazes circle, maybe arc intersects edge? */
1326  /* If so, grazing point is the closest point. */
1327  /* If not, the closest point is one of the end points of A */
1328  else if ( dist_C_D == radius_C )
1329  {
1330  /* Closest point D is also the point of grazing */
1331  pt_in_arc = lw_pt_in_arc(&D, B1, B2, B3);
1332  pt_in_seg = lw_pt_in_seg(&D, A1, A2);
1333
1334  /* Is D contained in both A and B? */
1335  if ( pt_in_arc && pt_in_seg )
1336  {
1337  dl->distance = 0.0;
1338  dl->p1 = D;
1339  dl->p2 = D;
1340  return LW_TRUE;
1341  }
1342  }
1343  /* Line misses circle. */
1344  /* If closest point to A on circle is within B, then that's the closest */
1345  /* Otherwise, the closest point will be an end point of A */
1346  else
1347  {
1348  POINT2D G; /* Point on circle closest to A */
1349  G.x = C.x + (D.x-C.x) * radius_C / dist_C_D;
1350  G.y = C.y + (D.y-C.y) * radius_C / dist_C_D;
1351
1352  pt_in_arc = lw_pt_in_arc(&G, B1, B2, B3);
1353  pt_in_seg = lw_pt_in_seg(&D, A1, A2);
1354
1355  /* Closest point is on the interior of A and B */
1356  if ( pt_in_arc && pt_in_seg )
1357  return lw_dist2d_pt_pt(&D, &G, dl);
1358
1359  }
1360
1361  /* Now we test the many combinations of end points with either */
1362  /* arcs or edges. Each previous check determined if the closest */
1363  /* potential point was within the arc/segment inscribed on the */
1364  /* line/circle holding the arc/segment. */
1365
1366  /* Closest point is in the arc, but not in the segment, so */
1367  /* one of the segment end points must be the closest. */
1368  if ( pt_in_arc & ! pt_in_seg )
1369  {
1370  lw_dist2d_pt_arc(A1, B1, B2, B3, dl);
1371  lw_dist2d_pt_arc(A2, B1, B2, B3, dl);
1372  return LW_TRUE;
1373  }
1374  /* or, one of the arc end points is the closest */
1375  else if ( pt_in_seg && ! pt_in_arc )
1376  {
1377  lw_dist2d_pt_seg(B1, A1, A2, dl);
1378  lw_dist2d_pt_seg(B3, A1, A2, dl);
1379  return LW_TRUE;
1380  }
1381  /* Finally, one of the end-point to end-point combos is the closest. */
1382  else
1383  {
1384  lw_dist2d_pt_pt(A1, B1, dl);
1385  lw_dist2d_pt_pt(A1, B3, dl);
1386  lw_dist2d_pt_pt(A2, B1, dl);
1387  lw_dist2d_pt_pt(A2, B3, dl);
1388  return LW_TRUE;
1389  }
1390
1391  return LW_FALSE;
1392 }
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:228
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 mode
Definition: measures.h:26
#define DIST_MIN
POINT2D p1
Definition: measures.h:24
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:67
double x
Definition: liblwgeom.h:284
#define LW_FALSE
Definition: liblwgeom.h:52
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:51
int lw_dist2d_pt_arc(const POINT2D *P, const POINT2D *A1, const POINT2D *A2, const POINT2D *A3, DISTPTS *dl)
Definition: measures.c:1395
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 occation to lw_dist2d_pt_pt Before i...
Definition: measures.c:2011
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:1624
POINT2D p2
Definition: measures.h:25
double y
Definition: liblwgeom.h:284
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
double distance
Definition: measures.h:23
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
Structure used in distance-calculations.
Definition: measures.h:21
void lw_dist2d_distpts_init(DISTPTS *dl, int mode)
Definition: measures.c:27
int lw_dist2d_pt_pt(const POINT2D *thep1, const POINT2D *thep2, DISTPTS *dl)
Compares incomming points and stores the points closest to each other or most far away from each othe...
Definition: measures.c:2087

Here is the call graph for this function:

Here is the caller graph for this function: