subzero - geometry dash world
Conecte dos segmentos de línea (7)
Consejo rápido: si quiere comparar distancias basadas en puntos, no es necesario hacer las raíces cuadradas.
Por ejemplo, para ver si P-to-Q es una distancia menor que Q-to-R, simplemente marque (pseudocódigo):
square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y)
Dado dos segmentos de línea 2D, A y B, ¿cómo calculo la longitud del segmento de línea 2D más corto, C, que conecta A y B?
Papel de Gernot Hoffmann (algoritmo y código Pascal):
Esta página tiene información que puede estar buscando.
Esta página tiene una breve descripción para encontrar la distancia más corta entre dos líneas, aunque el enlace de @ strager incluye algún código (¡en Fortran!)
Considere sus dos segmentos de línea A y B para ser representados por dos puntos cada uno:
línea A representada por A1 (x, y), A2 (x, y)
Línea B representada por B1 (x, y) B2 (x, y)
Primero compruebe si las dos líneas se cruzan usando este algoritmo.
Si se cruzan , entonces la distancia entre las dos líneas es cero, y el segmento de línea que los une es el punto de intersección.
Si no se cruzan , utilice este método: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/ para calcular la distancia más corta entre:
- punto A1 y línea B
- Punto A2 y línea B
- Punto B1 y línea A
- Punto B2 y línea A
El más corto de esos cuatro segmentos de línea es tu respuesta.
Afterlife''s dijo: "Primero comprueba si las dos líneas se cruzan usando este algoritmo", pero no indicó a qué algoritmo se refería. Obviamente, lo que importa es la intersección de los segmentos de línea , no las líneas extendidas; cualquier segmento de línea no paralelo (excluyendo los puntos finales coincidentes que no definen una línea) se intersectará, pero la distancia entre los segmentos de línea no será necesariamente cero. Así que supongo que quiso decir "segmentos de línea" en lugar de "líneas" allí.
El enlace que dio Afterlife es un enfoque muy elegante para encontrar el punto más cercano de una línea (o segmento de línea, o rayo) a otro punto arbitrario. Esto funciona para encontrar la distancia desde cada punto final al otro segmento de línea (restringir el parámetro calculado u a ser no menos de 0 para un segmento de línea o rayo y no ser más de 1 para un segmento de línea), pero no lo hace maneje la posibilidad de que un punto interior en un segmento de línea esté más cerca que cualquiera de los extremos ya que en realidad se cruzan, por lo que se requiere un control adicional sobre la intersección.
En cuanto al algoritmo para determinar la intersección del segmento de línea, un enfoque sería encontrar la intersección de las líneas extendidas (si es paralelo, entonces ya terminaste), y luego determinar si ese punto está dentro de ambos segmentos de línea, como tomando el producto de puntos de los vectores desde el punto de intersección, T, a los dos puntos finales:
((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) * (Ty - A2y))
Si esto es negativo (o "cero"), entonces T está entre A1 y A2 (o en un punto final). Verifique de manera similar para el otro segmento de línea. Si cualquiera fue mayor que "cero", los segmentos de línea no se intersectan. Por supuesto, esto depende de encontrar primero la intersección de las líneas extendidas, lo que puede requerir expresar cada línea como una ecuación y resolver el sistema mediante reducción gaussiana (etc.).
Pero puede haber una manera más directa sin tener que resolver el punto de intersección, tomando el producto cruzado de los vectores (B1-A1) y (B2-A1) y el producto cruzado de los vectores (B1-A2) y (B2-A2). Si estos productos cruzados están en la misma dirección, entonces A1 y A2 están en el mismo lado de la línea B; si están en direcciones opuestas, entonces están en lados opuestos de la línea B (y si es 0, entonces uno o ambos están en la línea B). De forma similar, compruebe los productos cruzados de los vectores (A1-B1) y (A2-B1) y de (A1-B2) y (A2-B2). Si cualquiera de estos productos cruzados es "cero", o si los puntos finales de ambos segmentos de línea caen en lados opuestos de la otra línea, entonces los segmentos de línea mismos deben cruzarse, de lo contrario no se cruzan.
Por supuesto, necesita una fórmula práctica para calcular un producto cruzado de dos vectores a partir de sus coordenadas. O si pudieras determinar los ángulos (siendo positivo o negativo), no necesitarías el producto cruzado real, ya que es la dirección de los ángulos entre los vectores lo que realmente nos importa (o el seno del ángulo, realmente) . Pero creo que la fórmula para el producto cruzado (en 2-D) es simplemente:
Cruz (V1, V2) = (V1x * V2y) - (V2x * V1y)
Este es el componente del eje z del vector de producto cruzado 3-D (donde los componentes xey deben ser cero, porque los vectores iniciales están en el plano z = 0), por lo que simplemente puede mirar el signo (o "cero").
Por lo tanto, podría usar uno de estos dos métodos para verificar la intersección del segmento de línea en el algoritmo Afterlife describe (haciendo referencia al enlace).
Usando la idea general de los algoritmos de Afterlife y Rob Parker anteriores, aquí hay una versión en C ++ de un conjunto de métodos para obtener la distancia mínima entre 2 segmentos 2D arbitrarios. Esto manejará segmentos superpuestos, segmentos paralelos, segmentos intersecantes y no intersecantes. Además, usa varios valores epsilon para proteger contra la imprecisión de punto flotante. Finalmente, además de devolver la distancia mínima, este algoritmo le dará el punto en el segmento 1 más cercano al segmento 2 (que también es el punto de intersección si los segmentos se cruzan). Sería bastante trivial devolver también el punto en [p3, p4] más cercano a [p1, p2] si así lo desea, pero lo dejo como ejercicio para el lector :)
// minimum distance (squared) between vertices, i.e. minimum segment length (squared)
#define EPSILON_MIN_VERTEX_DISTANCE_SQUARED 0.00000001
// An arbitrary tiny epsilon. If you use float instead of double, you''ll probably want to change this to something like 1E-7f
#define EPSILON_TINY 1.0E-14
// Arbitrary general epsilon. Useful for places where you need more "slop" than EPSILON_TINY (which is most places).
// If you use float instead of double, you''ll likely want to change this to something like 1.192092896E-04
#define EPSILON_GENERAL 1.192092896E-07
bool AreValuesEqual(double val1, double val2, double tolerance)
{
if (val1 >= (val2 - tolerance) && val1 <= (val2 + tolerance))
{
return true;
}
return false;
}
double PointToPointDistanceSquared(double p1x, double p1y, double p2x, double p2y)
{
double dx = p2x - p1x;
double dy = p2y - p1y;
return (dx * dx) + (dy * dy);
}
double PointSegmentDistanceSquared( double px, double py,
double p1x, double p1y,
double p2x, double p2y,
double& t,
double& qx, double& qy)
{
double dx = p2x - p1x;
double dy = p2y - p1y;
double dp1x = px - p1x;
double dp1y = py - p1y;
const double segLenSquared = (dx * dx) + (dy * dy);
if (AreValuesEqual(segLenSquared, 0.0, EPSILON_MIN_VERTEX_DISTANCE_SQUARED))
{
// segment is a point.
qx = p1x;
qy = p1y;
t = 0.0;
return ((dp1x * dp1x) + (dp1y * dp1y));
}
else
{
t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
if (t <= EPSILON_TINY)
{
// intersects at or to the "left" of first segment vertex (p1x, p1y). If t is approximately 0.0, then
// intersection is at p1. If t is less than that, then there is no intersection (i.e. p is not within
// the ''bounds'' of the segment)
if (t >= -EPSILON_TINY)
{
// intersects at 1st segment vertex
t = 0.0;
}
// set our ''intersection'' point to p1.
qx = p1x;
qy = p1y;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
}
else if (t >= (1.0 - EPSILON_TINY))
{
// intersects at or to the "right" of second segment vertex (p2x, p2y). If t is approximately 1.0, then
// intersection is at p2. If t is greater than that, then there is no intersection (i.e. p is not within
// the ''bounds'' of the segment)
if (t <= (1.0 + EPSILON_TINY))
{
// intersects at 2nd segment vertex
t = 1.0;
}
qx = p2x;
qy = p2y;
// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
// we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
}
else
{
// The projection of the point to the point on the segment that is perpendicular succeeded and the point
// is ''within'' the bounds of the segment. Set the intersection point as that projected point.
qx = ((1.0 - t) * p1x) + (t * p2x);
qy = ((1.0 - t) * p1y) + (t * p2y);
// for debugging
//ASSERT(AreValuesEqual(qx, p1x + (t * dx), EPSILON_TINY));
//ASSERT(AreValuesEqual(qy, p1y + (t * dy), EPSILON_TINY));
}
// return the squared distance from p to the intersection point.
double dpqx = px - qx;
double dpqy = py - qy;
return ((dpqx * dpqx) + (dpqy * dpqy));
}
}
double SegmentSegmentDistanceSquared( double p1x, double p1y,
double p2x, double p2y,
double p3x, double p3y,
double p4x, double p4y,
double& qx, double& qy)
{
// check to make sure both segments are long enough (i.e. verts are farther apart than minimum allowed vert distance).
// If 1 or both segments are shorter than this min length, treat them as a single point.
double segLen12Squared = PointToPointDistanceSquared(p1x, p1y, p2x, p2y);
double segLen34Squared = PointToPointDistanceSquared(p3x, p3y, p4x, p4y);
double t = 0.0;
double minDist2 = 1E+38;
if (segLen12Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
{
qx = p1x;
qy = p1y;
if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
{
// point to point
minDist2 = PointToPointDistanceSquared(p1x, p1y, p3x, p3y);
}
else
{
// point - seg
minDist2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y);
}
return minDist2;
}
else if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED)
{
// seg - point
minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy);
return minDist2;
}
// if you have a point class and/or methods to do cross products, you can use those here.
// This is what we''re actually doing:
// Point2D delta43(p4x - p3x, p4y - p3y); // dir of p3 -> p4
// Point2D delta12(p1x - p2x, p1y - p2y); // dir of p2 -> p1
// double d = delta12.Cross2D(delta43);
double d = ((p4y - p3y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p3x));
bool bParallel = AreValuesEqual(d, 0.0, EPSILON_GENERAL);
if (!bParallel)
{
// segments are not parallel. Check for intersection.
// Point2D delta42(p4x - p2x, p4y - p2y); // dir of p2 -> p4
// t = 1.0 - (delta42.Cross2D(delta43) / d);
t = 1.0 - ((((p4y - p3y) * (p4x - p2x)) - ((p4y - p2y) * (p4x - p3x))) / d);
double seg12TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED / segLen12Squared);
if (t >= -seg12TEps && t <= (1.0 + seg12TEps))
{
// inside [p1,p2]. Segments may intersect.
// double s = 1.0 - (delta12.Cross2D(delta42) / d);
double s = 1.0 - ((((p4y - p2y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p2x))) / d);
double seg34TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED / segLen34Squared);
if (s >= -seg34TEps && s <= (1.0 + seg34TEps))
{
// segments intersect!
minDist2 = 0.0;
qx = ((1.0 - t) * p1x) + (t * p2x);
qy = ((1.0 - t) * p1y) + (t * p2y);
// for debugging
//double qsx = ((1.0 - s) * p3x) + (s * p4x);
//double qsy = ((1.0 - s) * p3y) + (s * p4y);
//ASSERT(AreValuesEqual(qx, qsx, EPSILON_MIN_VERTEX_DISTANCE_SQUARED));
//ASSERT(AreValuesEqual(qy, qsy, EPSILON_MIN_VERTEX_DISTANCE_SQUARED));
return minDist2;
}
}
}
// Segments do not intersect. Find closest point and return dist. No other way at this
// point except to just brute-force check each segment end-point vs opposite segment. The
// minimum distance of those 4 tests is the closest point.
double tmpQx, tmpQy, tmpD2;
minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy);
tmpD2 = PointSegmentDistanceSquared(p4x, p4y, p1x, p1y, p2x, p2y, t, tmpQx, tmpQy);
if (tmpD2 < minDist2)
{
qx = tmpQx;
qy = tmpQy;
minDist2 = tmpD2;
}
tmpD2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy);
if (tmpD2 < minDist2)
{
qx = p1x;
qy = p1y;
minDist2 = tmpD2;
}
tmpD2 = PointSegmentDistanceSquared(p2x, p2y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy);
if (tmpD2 < minDist2)
{
qx = p2x;
qy = p2y;
minDist2 = tmpD2;
}
return minDist2;
}