PostGIS  2.4.9dev-r@@SVN_REVISION@@

◆ lw_dist3d_seg_seg()

int lw_dist3d_seg_seg ( POINT3DZ s1p1,
POINT3DZ s1p2,
POINT3DZ s2p1,
POINT3DZ s2p2,
DISTPTS3D dl 
)

Finds the two closest points on two linesegments.

Definition at line 921 of file measures3d.c.

References DOT, get_3dvector_from_points(), lw_dist3d_pt_pt(), lw_dist3d_pt_seg(), LW_FALSE, LW_TRUE, rect_node::p1, rect_node::p2, DISTPTS3D::twisted, POINT3DZ::x, POINT3DZ::y, and POINT3DZ::z.

Referenced by lw_dist3d_ptarray_ptarray().

922 {
923  VECTOR3D v1, v2, vl;
924  double s1k, s2k; /*two variables representing where on Line 1 (s1k) and where on Line 2 (s2k) a connecting line between the two lines is perpendicular to both lines*/
925  POINT3DZ p1, p2;
926  double a, b, c, d, e, D;
927 
928  /*s1p1 and s1p2 are the same point */
929  if ( ( s1p1->x == s1p2->x) && (s1p1->y == s1p2->y) && (s1p1->z == s1p2->z) )
930  {
931  return lw_dist3d_pt_seg(s1p1,s2p1,s2p2,dl);
932  }
933  /*s2p1 and s2p2 are the same point */
934  if ( ( s2p1->x == s2p2->x) && (s2p1->y == s2p2->y) && (s2p1->z == s2p2->z) )
935  {
936  dl->twisted= ((dl->twisted) * (-1));
937  return lw_dist3d_pt_seg(s2p1,s1p1,s1p2,dl);
938  }
939 
940 /*
941  Here we use algorithm from softsurfer.com
942  that can be found here
943  http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm
944 */
945 
946  if (!get_3dvector_from_points(s1p1, s1p2, &v1))
947  return LW_FALSE;
948 
949  if (!get_3dvector_from_points(s2p1, s2p2, &v2))
950  return LW_FALSE;
951 
952  if (!get_3dvector_from_points(s2p1, s1p1, &vl))
953  return LW_FALSE;
954 
955  a = DOT(v1,v1);
956  b = DOT(v1,v2);
957  c = DOT(v2,v2);
958  d = DOT(v1,vl);
959  e = DOT(v2,vl);
960  D = a*c - b*b;
961 
962 
963  if (D <0.000000001)
964  { /* the lines are almost parallel*/
965  s1k = 0.0; /*If the lines are paralell we try by using the startpoint of first segment. If that gives a projected point on the second line outside segment 2 it wil be found that s2k is >1 or <0.*/
966  if(b>c) /* use the largest denominator*/
967  {
968  s2k=d/b;
969  }
970  else
971  {
972  s2k =e/c;
973  }
974  }
975  else
976  {
977  s1k = (b*e - c*d) / D;
978  s2k = (a*e - b*d) / D;
979  }
980 
981  /* Now we check if the projected closest point on the infinite lines is outside our segments. If so the combinations with start and end points will be tested*/
982  if(s1k<0.0||s1k>1.0||s2k<0.0||s2k>1.0)
983  {
984  if(s1k<0.0)
985  {
986 
987  if (!lw_dist3d_pt_seg(s1p1, s2p1, s2p2, dl))
988  {
989  return LW_FALSE;
990  }
991  }
992  if(s1k>1.0)
993  {
994 
995  if (!lw_dist3d_pt_seg(s1p2, s2p1, s2p2, dl))
996  {
997  return LW_FALSE;
998  }
999  }
1000  if(s2k<0.0)
1001  {
1002  dl->twisted= ((dl->twisted) * (-1));
1003  if (!lw_dist3d_pt_seg(s2p1, s1p1, s1p2, dl))
1004  {
1005  return LW_FALSE;
1006  }
1007  }
1008  if(s2k>1.0)
1009  {
1010  dl->twisted= ((dl->twisted) * (-1));
1011  if (!lw_dist3d_pt_seg(s2p2, s1p1, s1p2, dl))
1012  {
1013  return LW_FALSE;
1014  }
1015  }
1016  }
1017  else
1018  {/*Find the closest point on the edges of both segments*/
1019  p1.x=s1p1->x+s1k*(s1p2->x-s1p1->x);
1020  p1.y=s1p1->y+s1k*(s1p2->y-s1p1->y);
1021  p1.z=s1p1->z+s1k*(s1p2->z-s1p1->z);
1022 
1023  p2.x=s2p1->x+s2k*(s2p2->x-s2p1->x);
1024  p2.y=s2p1->y+s2k*(s2p2->y-s2p1->y);
1025  p2.z=s2p1->z+s2k*(s2p2->z-s2p1->z);
1026 
1027  if (!lw_dist3d_pt_pt(&p1,&p2,dl))/* Send the closest points to point-point calculation*/
1028  {
1029  return LW_FALSE;
1030  }
1031  }
1032  return LW_TRUE;
1033 }
double z
Definition: liblwgeom.h:334
double y
Definition: liblwgeom.h:334
double x
Definition: liblwgeom.h:334
#define DOT(u, v)
Definition: measures3d.h:31
#define LW_FALSE
Definition: liblwgeom.h:77
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:76
int lw_dist3d_pt_pt(POINT3DZ *thep1, POINT3DZ *thep2, DISTPTS3D *dl)
Compares incomming points and stores the points closest to each other or most far away from each othe...
Definition: measures3d.c:835
int twisted
Definition: measures3d.h:45
static int get_3dvector_from_points(POINT3DZ *p1, POINT3DZ *p2, VECTOR3D *v)
Definition: measures3d.c:45
int lw_dist3d_pt_seg(POINT3DZ *p, POINT3DZ *A, POINT3DZ *B, DISTPTS3D *dl)
If searching for min distance, this one finds the closest point on segment A-B from p...
Definition: measures3d.c:770
Here is the call graph for this function:
Here is the caller graph for this function: