PostGIS  2.1.10dev-r@@SVN_REVISION@@
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.

This function is changed so it is not doing any comparasion of distance but just sending every possible combination further to lw_dist2d_pt_seg

Definition at line 1624 of file measures.c.

References DIST_MAX, DIST_MIN, DISTPTS::distance, lw_dist2d_pt_seg(), LW_FALSE, LW_TRUE, LWDEBUGF, lwerror(), DISTPTS::mode, DISTPTS::p1, DISTPTS::p2, r, s, DISTPTS::twisted, POINT2D::x, and POINT2D::y.

Referenced by lw_dist2d_arc_arc(), lw_dist2d_ptarray_ptarray(), and lw_dist2d_seg_arc().

1625 {
1626  double s_top, s_bot,s;
1627  double r_top, r_bot,r;
1628 
1629  LWDEBUGF(2, "lw_dist2d_seg_seg [%g,%g]->[%g,%g] by [%g,%g]->[%g,%g]",
1630  A->x,A->y,B->x,B->y, C->x,C->y, D->x, D->y);
1631 
1632  /*A and B are the same point */
1633  if ( ( A->x == B->x) && (A->y == B->y) )
1634  {
1635  return lw_dist2d_pt_seg(A,C,D,dl);
1636  }
1637  /*U and V are the same point */
1638 
1639  if ( ( C->x == D->x) && (C->y == D->y) )
1640  {
1641  dl->twisted= ((dl->twisted) * (-1));
1642  return lw_dist2d_pt_seg(D,A,B,dl);
1643  }
1644  /* AB and CD are line segments */
1645  /* from comp.graphics.algo
1646 
1647  Solving the above for r and s yields
1648  (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
1649  r = ----------------------------- (eqn 1)
1650  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1651 
1652  (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
1653  s = ----------------------------- (eqn 2)
1654  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1655  Let P be the position vector of the intersection point, then
1656  P=A+r(B-A) or
1657  Px=Ax+r(Bx-Ax)
1658  Py=Ay+r(By-Ay)
1659  By examining the values of r & s, you can also determine some other limiting conditions:
1660  If 0<=r<=1 & 0<=s<=1, intersection exists
1661  r<0 or r>1 or s<0 or s>1 line segments do not intersect
1662  If the denominator in eqn 1 is zero, AB & CD are parallel
1663  If the numerator in eqn 1 is also zero, AB & CD are collinear.
1664 
1665  */
1666  r_top = (A->y-C->y)*(D->x-C->x) - (A->x-C->x)*(D->y-C->y);
1667  r_bot = (B->x-A->x)*(D->y-C->y) - (B->y-A->y)*(D->x-C->x);
1668 
1669  s_top = (A->y-C->y)*(B->x-A->x) - (A->x-C->x)*(B->y-A->y);
1670  s_bot = (B->x-A->x)*(D->y-C->y) - (B->y-A->y)*(D->x-C->x);
1671 
1672  if ( (r_bot==0) || (s_bot == 0) )
1673  {
1674  if ((lw_dist2d_pt_seg(A,C,D,dl)) && (lw_dist2d_pt_seg(B,C,D,dl)))
1675  {
1676  dl->twisted= ((dl->twisted) * (-1)); /*here we change the order of inputted geometrys and that we notice by changing sign on dl->twisted*/
1677  return ((lw_dist2d_pt_seg(C,A,B,dl)) && (lw_dist2d_pt_seg(D,A,B,dl))); /*if all is successful we return true*/
1678  }
1679  else
1680  {
1681  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1682  }
1683  }
1684 
1685  s = s_top/s_bot;
1686  r= r_top/r_bot;
1687 
1688  if (((r<0) || (r>1) || (s<0) || (s>1)) || (dl->mode == DIST_MAX))
1689  {
1690  if ((lw_dist2d_pt_seg(A,C,D,dl)) && (lw_dist2d_pt_seg(B,C,D,dl)))
1691  {
1692  dl->twisted= ((dl->twisted) * (-1)); /*here we change the order of inputted geometrys and that we notice by changing sign on dl->twisted*/
1693  return ((lw_dist2d_pt_seg(C,A,B,dl)) && (lw_dist2d_pt_seg(D,A,B,dl))); /*if all is successful we return true*/
1694  }
1695  else
1696  {
1697  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1698  }
1699  }
1700  else
1701  {
1702  if (dl->mode == DIST_MIN) /*If there is intersection we identify the intersection point and return it but only if we are looking for mindistance*/
1703  {
1704  POINT2D theP;
1705 
1706  if (((A->x==C->x)&&(A->y==C->y))||((A->x==D->x)&&(A->y==D->y)))
1707  {
1708  theP.x = A->x;
1709  theP.y = A->y;
1710  }
1711  else if (((B->x==C->x)&&(B->y==C->y))||((B->x==D->x)&&(B->y==D->y)))
1712  {
1713  theP.x = B->x;
1714  theP.y = B->y;
1715  }
1716  else
1717  {
1718  theP.x = A->x+r*(B->x-A->x);
1719  theP.y = A->y+r*(B->y-A->y);
1720  }
1721  dl->distance=0.0;
1722  dl->p1=theP;
1723  dl->p2=theP;
1724  }
1725  return LW_TRUE;
1726 
1727  }
1728  lwerror("unspecified error in function lw_dist2d_seg_seg");
1729  return LW_FALSE; /*If we have come here something is wrong*/
1730 }
char * r
Definition: cu_in_wkt.c:25
#define DIST_MAX
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_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
POINT2D p2
Definition: measures.h:25
double y
Definition: liblwgeom.h:284
char * s
Definition: cu_in_wkt.c:24
int twisted
Definition: measures.h:27
double distance
Definition: measures.h:23
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55

Here is the call graph for this function:

Here is the caller graph for this function: