PostGIS  2.5.7dev-r@@SVN_REVISION@@

## ◆ lw_dist2d_seg_seg()

 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 comparison of distance but just sending every possible combination further to lw_dist2d_pt_seg

Definition at line 1821 of file measures.c.

1822 {
1823  double s_top, s_bot,s;
1824  double r_top, r_bot,r;
1825
1826  LWDEBUGF(2, "lw_dist2d_seg_seg [%g,%g]->[%g,%g] by [%g,%g]->[%g,%g]",
1827  A->x,A->y,B->x,B->y, C->x,C->y, D->x, D->y);
1828
1829  /*A and B are the same point */
1830  if ( ( A->x == B->x) && (A->y == B->y) )
1831  {
1832  return lw_dist2d_pt_seg(A,C,D,dl);
1833  }
1834  /*U and V are the same point */
1835
1836  if ( ( C->x == D->x) && (C->y == D->y) )
1837  {
1838  dl->twisted= ((dl->twisted) * (-1));
1839  return lw_dist2d_pt_seg(D,A,B,dl);
1840  }
1841  /* AB and CD are line segments */
1842  /* from comp.graphics.algo
1843
1844  Solving the above for r and s yields
1845  (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
1846  r = ----------------------------- (eqn 1)
1847  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1848
1849  (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
1850  s = ----------------------------- (eqn 2)
1851  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1852  Let P be the position vector of the intersection point, then
1853  P=A+r(B-A) or
1854  Px=Ax+r(Bx-Ax)
1855  Py=Ay+r(By-Ay)
1856  By examining the values of r & s, you can also determine some other limiting conditions:
1857  If 0<=r<=1 & 0<=s<=1, intersection exists
1858  r<0 or r>1 or s<0 or s>1 line segments do not intersect
1859  If the denominator in eqn 1 is zero, AB & CD are parallel
1860  If the numerator in eqn 1 is also zero, AB & CD are collinear.
1861
1862  */
1863  r_top = (A->y-C->y)*(D->x-C->x) - (A->x-C->x)*(D->y-C->y);
1864  r_bot = (B->x-A->x)*(D->y-C->y) - (B->y-A->y)*(D->x-C->x);
1865
1866  s_top = (A->y-C->y)*(B->x-A->x) - (A->x-C->x)*(B->y-A->y);
1867  s_bot = (B->x-A->x)*(D->y-C->y) - (B->y-A->y)*(D->x-C->x);
1868
1869  if ( (r_bot==0) || (s_bot == 0) )
1870  {
1871  if ((lw_dist2d_pt_seg(A,C,D,dl)) && (lw_dist2d_pt_seg(B,C,D,dl)))
1872  {
1873  dl->twisted= ((dl->twisted) * (-1)); /*here we change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
1874  return ((lw_dist2d_pt_seg(C,A,B,dl)) && (lw_dist2d_pt_seg(D,A,B,dl))); /*if all is successful we return true*/
1875  }
1876  else
1877  {
1878  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1879  }
1880  }
1881
1882  s = s_top/s_bot;
1883  r= r_top/r_bot;
1884
1885  if (((r<0) || (r>1) || (s<0) || (s>1)) || (dl->mode == DIST_MAX))
1886  {
1887  if ((lw_dist2d_pt_seg(A,C,D,dl)) && (lw_dist2d_pt_seg(B,C,D,dl)))
1888  {
1889  dl->twisted= ((dl->twisted) * (-1)); /*here we change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
1890  return ((lw_dist2d_pt_seg(C,A,B,dl)) && (lw_dist2d_pt_seg(D,A,B,dl))); /*if all is successful we return true*/
1891  }
1892  else
1893  {
1894  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1895  }
1896  }
1897  else
1898  {
1899  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*/
1900  {
1901  POINT2D theP;
1902
1903  if (((A->x==C->x)&&(A->y==C->y))||((A->x==D->x)&&(A->y==D->y)))
1904  {
1905  theP.x = A->x;
1906  theP.y = A->y;
1907  }
1908  else if (((B->x==C->x)&&(B->y==C->y))||((B->x==D->x)&&(B->y==D->y)))
1909  {
1910  theP.x = B->x;
1911  theP.y = B->y;
1912  }
1913  else
1914  {
1915  theP.x = A->x+r*(B->x-A->x);
1916  theP.y = A->y+r*(B->y-A->y);
1917  }
1918  dl->distance=0.0;
1919  dl->p1=theP;
1920  dl->p2=theP;
1921  }
1922  return LW_TRUE;
1923  }
1924 }
char * s
Definition: cu_in_wkt.c:23
char * r
Definition: cu_in_wkt.c:24
#define LW_FALSE
Definition: liblwgeom.h:77
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:76
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
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:2206
#define DIST_MIN
Definition: measures.h:44
#define DIST_MAX
Definition: measures.h:43
POINT2D p1
Definition: measures.h:52
POINT2D p2
Definition: measures.h:53
int twisted
Definition: measures.h:55
int mode
Definition: measures.h:54
double distance
Definition: measures.h:51
double y
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:331
Here is the call graph for this function:
Here is the caller graph for this function: