algorithm - applications - "computational geometry an introduction"
¿Cómo calcular el punto de espejo a lo largo de una línea? (6)
En el plano 2D, tengo un punto y una línea. ¿Cómo conseguir el punto de espejo a lo largo de esta línea?
Calcule el punto más cercano en la línea al punto en cuestión. Luego invierte la dirección del vector entre esos puntos y agrégalo al punto más cercano de la línea. Voilà, has encontrado el punto de espejo.
Cuando cosas así se hacen en los programas de computadora, uno de los problemas con los que debe lidiar es realizar estos cálculos utilizando solo aritmética de enteros (o tanto como sea posible), suponiendo que la entrada está en enteros. Hacer esto en números enteros tanto como sea posible es un tema aparte que no abordaré aquí.
La siguiente es una solución "matemática", que si se implementa literalmente requerirá cálculos de coma flotante. No sé si esto es aceptable en tu caso. Puede optimizarlo a su gusto usted mismo.
(1) Represente su línea L por
A * x + B * y + C = 0
ecuación. Tenga en cuenta que el vector (A, B) es el vector normal de esta línea.
Por ejemplo, si la línea está definida por dos puntos X1(x1, y1) y X2(x2, y2) , entonces
A = y2 - y1
B = -(x2 - x1)
C = -A * x1 - B * y1
(2) Normalice la ecuación dividiendo todos los coeficientes por la longitud del vector (A, B) . Es decir, calcular la longitud
M = sqrt(A * A + B * B)
y luego calcule los valores
A'' = A / M
B'' = B / M
C'' = C / M
La ecuacion
A'' * x + B'' * y + C'' = 0
sigue siendo una ecuación equivalente de su línea L excepto que ahora el vector normal (A'', B'') es un vector unitario.
(3) Tome su punto P(px, py) y calcule el valor
D = A'' * px + B'' * py + C''
Esto le dará la distancia D firmada desde su punto P a su línea L En otras palabras, esta es la distancia desde P hasta el punto más cercano en L (realmente no nos importa el punto más cercano en sí, solo necesitamos la distancia).
El letrero indica en qué lado de la línea L el punto P Si P encuentra en el mismo lado que el vector (A'', B'') apunta hacia (lado "positivo"), la distancia es positiva. Si P está en el otro lado (lado "negativo"), la distancia es negativa.
(4) Para encontrar su punto de espejo P''(px'', py'') , necesita mover su punto P por la distancia absoluta |2 * D| a través de la línea L al otro lado.
"Al otro lado de la línea" realmente significa que si el punto P estaba en el lado "positivo" de L , entonces tenemos que moverlo contra la dirección del vector (A'', B'') hacia el lado "negativo". Y viceversa, si el punto P estaba en el lado "negativo" de L , entonces tenemos que moverlo en la dirección del vector (A'', B'') al lado "positivo".
Esto se puede expresar simplemente moviendo el punto a la distancia de -2 * D (observe el signo menos) en la dirección del vector (A'', B'') .
Eso significa que
px'' = px - 2 * A'' * D
py'' = py - 2 * B'' * D
te da tu punto de espejo P''(px'', py'') .
Alternativamente, puede usar un enfoque basado en encontrar el punto N más cercano real en la línea L y luego reflejar su punto P con relación a N Esto ya se sugiere en otras respuestas, solo describiré cómo lo haría.
(1) Construye una ecuación
A*x + B*y + C = 0
para su línea L exactamente como se describe en el paso 1 anterior. No hay necesidad de normalizar esta ecuación.
(2) Construya una ecuación para la línea perpendicular que pasa por P Digamos que la línea perpendicular está representada por
D*x + E*y + F = 0
Los coeficientes D y E se conocen de inmediato
D = B
E = -A
mientras que F se puede calcular sustituyendo el punto P en la ecuación
F = -D*px - E*py
(3) Encuentre la intersección de estas dos líneas resolviendo el sistema de dos ecuaciones lineales
A*x + B*y = -C
D*x + E*y = -F
La regla de Cramer funciona muy bien en este caso. La fórmula dada en el artículo de intersección de línea en Wikipedia no es más que una aplicación de la regla de Cramer a este sistema.
La solución le proporciona el punto N(nx, ny) más cercano que estábamos buscando.
(4) Ahora solo calcula
px'' = nx + (nx - px)
py'' = ny + (ny - py)
para encontrar su punto P''(px'', py'') .
Tenga en cuenta que este enfoque se puede implementar casi por completo en números enteros. El único paso que puede perder precisión es la división dentro de la regla de Cramer en el paso 3. Por supuesto, como siempre, el precio que tendrá que pagar por la solución "casi integral" es la necesidad de aritmética de gran número. Incluso los coeficientes C y F pueden desbordarse, sin siquiera mencionar los cálculos dentro de las fórmulas de reglas de Cramer.
He hecho exactamente esto para otro sistema que he construido. Hay mucho más que esto en mi código; así que espero haber extraído todos los bits necesarios ... Line.ClosestPoint(Point pt) es el método que desea ...
El algoritmo se basa en la idea de que la pendiente de una línea perpindicular a cualquier línea dada es el recíproco multiplicativo negativo de la pendiente de la línea dada. es decir, si una línea tiene una pendiente m, entonces la otra línea tiene una pendiente -1 / m. Entonces, todo lo que tiene que hacer es formar una línea a través del punto con pendiente igual a -1 / my encontrar la intersección de esta línea con la línea original.
public class Line
{
protected const double epsilon = 1.0e-8;
public Point Anchor { get; set; }
public double Slope { get; set; }
public virtual Point ClosestPoint(Point pt)
{ return Intersection(Make(pt, -1 / Slope)); }
protected Line(Point anchor, double slope)
{
Anchor = anchor;
Slope = slope;
}
public static Line Make(Point anchor, double slope)
{ return new Line(anchor, slope); }
public virtual Point Intersection(Line line)
{
if (lib.Within(line.Slope, Slope, epsilon))
if( lib.Within(line.YIntcpt, YIntcpt, epsilon))
// code for NoInterceptException not included
throw new NoInterceptException(
"The two lines overlap.");
else return Point.NullPoint;
// ----------------------------------------
double tm = Slope, om = line.Slope,
tx = Anchor.X, ty = Anchor.Y,
ox = line.Anchor.X, oy = line.Anchor.Y;
var x = double.IsInfinity(tm) ? tx :
double.IsInfinity(om) ? ox :
(tm * tx - om * ox + oy - ty) /
(tm - om);
var y = double.IsInfinity(tm) ?
om * (x - ox) + oy :
tm * (x - tx) + ty;
return Point.Make(x, y);
}
}
public struct Point
{
const double epsilon = 1.0e-12;
private readonly bool isDef;
private readonly double y;
private readonly double x;
public bool HasValue { get { return isDef; } }
public bool IsNull { get { return !isDef; } }
private Point(double xValue, double yValue)
{ x = xValue; y = yValue; isDef = true; }
public static Point Make(double x, double y)
{ return new Point(x, y); }
public double X
{
get
{
// code for AlgebraicException not included
if (IsNull) throw new AlgebraicException("Null Point Object");
return x;
}
}
public double Y
{
get
{
// code for AlgebraicException not included
if (IsNull) throw new AlgebraicException("Null Point Object");
return y;
}
}
public static Point NullPoint { get { return new Point();}}
// Other functionality
}
Los detalles dependen de cómo esté representada su línea. Si lo representa como un punto arbitrario P en la línea junto con un vector de columna unidad n a lo largo de la línea, entonces el punto de espejo Q ''a cualquier punto Q viene dado por:
Q ''= Q + 2 (I - nn T ) ( P - Q )
(Aquí, I es la matriz de identidad 2x2, n T es la transposición de n (tratando n como una matriz 2x1), y nn T es la matriz 2x2 formada por la multiplicación de matrices estándar de n con n T ). No es demasiado difícil demuestre que Q ''no cambiará si mueve P en cualquier lugar de la línea.
No es difícil convertir otras representaciones de líneas en una representación de vector de punto / unidad.
Supongo que tiene la ubicación del punto y una ecuación para su línea, es decir,
P=(x1,y1) and y = ax + b
Primero, el caso obvio donde a = 0 (es decir, línea paralela al eje x) rinde
P''(x2,y2), with x2 = x1, y2 = y1 + 2(b-y1)
Para el caso más general,
Obtenga la ecuación genérica para una línea ortogonal a la suya: y = cx + d, con ac = -1
==> c = -1 / a
Determine b para que P pertenezca a la línea ortogonal: y1 = -x1 / a + d
==> d = y1 + x1 / a
Obtenga la intersección entre las dos líneas: y = -x / a + y1 + x1 / a = ax + b
==> x = (y1 + x1 / a -b) / (a + 1 / a), y = a (y1 + x1 / a -b) / (a + 1 / a) + b
Obtenga el vector entre la intersección y su punto P, agréguelo al punto de intersección para obtener el punto espejo P ''.
==> P ''(x2, y2), con x2 = x1 + 2 ((y1 + x1 / a -b) / (a + 1 / a) - x1) y2 = y1 + 2 (a (y1 + x1 / a -b) / (a + 1 / a) + b - y1)
Algunos pasos se pueden simplificar, pero esta es la idea general. Hice el álgebra mientras escribía, por lo que podría haber errores. Si encuentras uno, por favor dejame saber.
Supongamos que la ecuación de la línea es ax + by + c = 0 . Ahora imagina una línea perpendicular a ella, que puede representarse por -bx + ay + d = 0 (el producto de las pendientes de dos líneas perpendiculares es -1). Ahora el problema es encontrar d . Coloque la coordenada del punto en la segunda línea, y obtendrá el valor de d fácilmente.
La segunda parte es, para encontrar un punto en la segunda línea que es equidistante como el primer punto de la primera línea. Para eso, puedes encontrar la intersección de las dos líneas. Calcule las diferencias en y del punto dado y el punto de intersección. Ahora agréguelos al valor y del punto de intersección. Eso le da el punto que necesita (puede necesitar negar las diferencias, eso depende del orden de resta que use).