PostGIS  3.1.6dev-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 1863 of file measures.c.

1864 {
1865  double s_top, s_bot, s;
1866  double r_top, r_bot, r;
1867 
1868  /*A and B are the same point */
1869  if ((A->x == B->x) && (A->y == B->y))
1870  {
1871  return lw_dist2d_pt_seg(A, C, D, dl);
1872  }
1873 
1874  /*U and V are the same point */
1875  if ((C->x == D->x) && (C->y == D->y))
1876  {
1877  dl->twisted = ((dl->twisted) * (-1));
1878  return lw_dist2d_pt_seg(D, A, B, dl);
1879  }
1880 
1881  /* AB and CD are line segments */
1882  /* from comp.graphics.algo
1883 
1884  Solving the above for r and s yields
1885  (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
1886  r = ----------------------------- (eqn 1)
1887  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1888 
1889  (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
1890  s = ----------------------------- (eqn 2)
1891  (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
1892  Let P be the position vector of the intersection point, then
1893  P=A+r(B-A) or
1894  Px=Ax+r(Bx-Ax)
1895  Py=Ay+r(By-Ay)
1896  By examining the values of r & s, you can also determine some other limiting conditions:
1897  If 0<=r<=1 & 0<=s<=1, intersection exists
1898  r<0 or r>1 or s<0 or s>1 line segments do not intersect
1899  If the denominator in eqn 1 is zero, AB & CD are parallel
1900  If the numerator in eqn 1 is also zero, AB & CD are collinear.
1901 
1902  */
1903  r_top = (A->y - C->y) * (D->x - C->x) - (A->x - C->x) * (D->y - C->y);
1904  r_bot = (B->x - A->x) * (D->y - C->y) - (B->y - A->y) * (D->x - C->x);
1905 
1906  s_top = (A->y - C->y) * (B->x - A->x) - (A->x - C->x) * (B->y - A->y);
1907  s_bot = (B->x - A->x) * (D->y - C->y) - (B->y - A->y) * (D->x - C->x);
1908 
1909  if ((r_bot == 0) || (s_bot == 0))
1910  {
1911  if ((lw_dist2d_pt_seg(A, C, D, dl)) && (lw_dist2d_pt_seg(B, C, D, dl)))
1912  {
1913  /* change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
1914  dl->twisted *= -1;
1915  return ((lw_dist2d_pt_seg(C, A, B, dl)) && (lw_dist2d_pt_seg(D, A, B, dl)));
1916  }
1917  else
1918  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1919  }
1920 
1921  s = s_top / s_bot;
1922  r = r_top / r_bot;
1923 
1924  if (((r < 0) || (r > 1) || (s < 0) || (s > 1)) || (dl->mode == DIST_MAX))
1925  {
1926  if ((lw_dist2d_pt_seg(A, C, D, dl)) && (lw_dist2d_pt_seg(B, C, D, dl)))
1927  {
1928  /* change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
1929  dl->twisted *= -1;
1930  return ((lw_dist2d_pt_seg(C, A, B, dl)) && (lw_dist2d_pt_seg(D, A, B, dl)));
1931  }
1932  else
1933  return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
1934  }
1935  else
1936  {
1937  /* If there is intersection we identify the intersection point and return it but only if we are looking
1938  * for mindistance */
1939  if (dl->mode == DIST_MIN)
1940  {
1941  POINT2D theP;
1942 
1943  if (((A->x == C->x) && (A->y == C->y)) || ((A->x == D->x) && (A->y == D->y)))
1944  {
1945  theP.x = A->x;
1946  theP.y = A->y;
1947  }
1948  else if (((B->x == C->x) && (B->y == C->y)) || ((B->x == D->x) && (B->y == D->y)))
1949  {
1950  theP.x = B->x;
1951  theP.y = B->y;
1952  }
1953  else
1954  {
1955  theP.x = A->x + r * (B->x - A->x);
1956  theP.y = A->y + r * (B->y - A->y);
1957  }
1958  lw_dist2d_distpts_set(dl, 0, &theP, &theP);
1959  }
1960  return LW_TRUE;
1961  }
1962 }
char * s
Definition: cu_in_wkt.c:23
char * r
Definition: cu_in_wkt.c:24
#define LW_FALSE
Definition: liblwgeom.h:108
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:107
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
#define DIST_MIN
Definition: measures.h:44
#define DIST_MAX
Definition: measures.h:43
int twisted
Definition: measures.h:55
int mode
Definition: measures.h:54
double y
Definition: liblwgeom.h:404
double x
Definition: liblwgeom.h:404

References DIST_MAX, DIST_MIN, lw_dist2d_distpts_set(), lw_dist2d_pt_seg(), LW_FALSE, LW_TRUE, DISTPTS::mode, r, s, DISTPTS::twisted, POINT2D::x, and POINT2D::y.

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

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