Me gustaría un algoritmo para calcular el casco convexo de 4 puntos 2D. He analizado los algoritmos para el problema generalizado, pero me pregunto si hay una solución simple para 4 puntos.Casco convexo de 4 puntos
tomar tres de los puntos, y determinar si su triángulo es la derecha o izquierda ::
triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)
Para un sistema de coordenadas de mano derecha, este valor será positivo si ABC es a la izquierda, negativo para las agujas del reloj, y cero si son colineales. Pero, lo siguiente funcionará igual de bien para un sistema de coordenadas para zurdos, ya que la orientación es relativa.
calcular valores comparables para los tres triángulos que contienen el cuarto punto:
triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)
Si los tres de {ABD, BCD, CAD} tienen el mismo signo que ABC, entonces D está dentro de ABC, y el casco es triángulo ABC.
Si dos de {ABD, BCD, CAD} tienen el mismo signo que ABC, y uno tiene el signo opuesto, entonces los cuatro puntos son extremos, y el casco es cuadrilátero ABCD.
Si uno de {ABD, BCD, CAD} tiene el mismo signo que ABC, y dos tienen el signo opuesto, entonces el casco convexo es el triángulo con el mismo signo; el punto restante está dentro de él.
Si cualquiera de los valores del triángulo son cero, los tres puntos son colineales y el punto medio no es extremo. Si los cuatro puntos son colineales, los cuatro valores deben ser cero, y el casco será una línea o un punto. ¡Tenga cuidado con los problemas de robustez numérica en estos casos!
Para aquellos casos en los que ABC es positivo:
ABC ABD BCD CAD hull
------------------------
+ + + + ABC
+ + + - ABCD
+ + - + ABCD
+ + - - ABD
+ - + + ABCD
+ - + - BCD
+ - - + CAD
+ - - - [should not happen]
Aquí está una más ad-hoc algoritmo específico a 4 puntos:
algún cálculo es necesario si hay 4 puntos para ordenar correctamente a fin de evitar una corbata de lazo forma. Hmmm .... Parece que hay suficientes casos especiales para justificar el uso de un algoritmo generalizado. Sin embargo, podría sintonizar esto para ejecutar más rápido que un algoritmo generalizado.
o simplemente utilizar Jarvis march.
sí. agradable y simple. aquí hay una buena implementación-- http://tixxit.net/2009/12/jarvis-march/ – milkplus
Hice a proof of concept fiddle según una versión cruda del algoritmo de envoltura de regalos.
No es eficiente en el caso general, pero es suficiente solo para 4 puntos.
function Point (x, y)
{
this.x = x;
this.y = y;
}
Point.prototype.equals = function (p)
{
return this.x == p.x && this.y == p.y;
};
Point.prototype.distance = function (p)
{
return Math.sqrt (Math.pow (this.x-p.x, 2)
+ Math.pow (this.y-p.y, 2));
};
function convex_hull (points)
{
function left_oriented (p1, p2, candidate)
{
var det = (p2.x - p1.x) * (candidate.y - p1.y)
- (candidate.x - p1.x) * (p2.y - p1.y);
if (det > 0) return true; // left-oriented
if (det < 0) return false; // right oriented
// select the farthest point in case of colinearity
return p1.distance (candidate) > p1.distance (p2);
}
var N = points.length;
var hull = [];
// get leftmost point
var min = 0;
for (var i = 1; i != N; i++)
{
if (points[i].y < points[min].y) min = i;
}
hull_point = points[min];
// walk the hull
do
{
hull.push(hull_point);
var end_point = points[0];
for (var i = 1; i != N; i++)
{
if ( hull_point.equals (end_point)
|| left_oriented (hull_point,
end_point,
points[i]))
{
end_point = points[i];
}
}
hull_point = end_point;
}
/*
* must compare coordinates values (and not simply objects)
* for the case of 4 co-incident points
*/
while (!end_point.equals (hull[0]));
return hull;
}
fue divertido :)
He escrito una aplicación rápida de la respuesta de comingstorm utilizando una tabla de consulta. El caso en que los cuatro puntos son colineales es no tratado, ya que mi aplicación no lo necesita. Si los puntos son colineales, el algoritmo establece el primer punto del puntero [0] en nulo. El casco contiene 3 puntos si el punto [3] es el puntero nulo, sino que el casco tiene 4 puntos. El casco está en el sentido contrario a las agujas del reloj para un sistema de coordenadas donde el eje y apunta a la parte superior y el eje x a la derecha.
const char hull4_table[] = {
1,2,3,0,1,2,3,0,1,2,4,3,1,2,3,0,1,2,3,0,1,2,4,0,1,2,3,4,1,2,4,0,1,2,4,0,
1,2,3,0,1,2,3,0,1,4,3,0,1,2,3,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
1,4,2,3,1,4,3,0,1,4,3,0,2,3,4,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,2,4,0,1,3,4,0,1,2,4,0,1,2,4,0,
0,0,0,0,0,0,0,0,1,4,3,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,4,0,0,0,0,0,0,0,0,0,
1,4,2,0,1,4,2,0,1,4,3,0,1,4,2,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,2,4,3,0,1,3,4,0,1,3,4,0,1,3,2,4,
0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,3,2,0,1,3,4,0,1,3,2,0,1,3,2,0,
1,4,2,0,1,4,2,0,1,4,3,2,1,4,2,0,1,3,2,0,1,3,2,0,1,3,4,2,1,3,2,0,1,3,2,0
};
struct Vec2i {
int x, y;
};
typedef long long int64;
inline int sign(int64 x) {
return (x > 0) - (x < 0);
}
inline int64 orientation(const Vec2i& a, const Vec2i& b, const Vec2i& c) {
return (int64)(b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
void convex_hull4(const Vec2i** points) {
const Vec2i* p[5] = {(Vec2i*)0, points[0], points[1], points[2], points[3]};
char abc = (char)1 - sign(orientation(*points[0], *points[1], *points[2]));
char abd = (char)1 - sign(orientation(*points[0], *points[1], *points[3]));
char cad = (char)1 - sign(orientation(*points[2], *points[0], *points[3]));
char bcd = (char)1 - sign(orientation(*points[1], *points[2], *points[3]));
const char* t = hull4_table + (int)4 * (bcd + 3*cad + 9*abd + 27*abc);
points[0] = p[t[0]];
points[1] = p[t[1]];
points[2] = p[t[2]];
points[3] = p[t[3]];
}
Basado en respuesta @comingstorm I creado solución Swift:
func convexHull4(a: Pt, b: Pt, c: Pt, d: Pt) -> [LineSegment]? {
let abc = (a.y-b.y)*c.x + (b.x-a.x)*c.y + (a.x*b.y-b.x*a.y)
let abd = (a.y-b.y)*d.x + (b.x-a.x)*d.y + (a.x*b.y-b.x*a.y)
let bcd = (b.y-c.y)*d.x + (c.x-b.x)*d.y + (b.x*c.y-c.x*b.y)
let cad = (c.y-a.y)*d.x + (a.x-c.x)*d.y + (c.x*a.y-a.x*c.y)
if (abc > 0 && abd > 0 && bcd > 0 && cad > 0) ||
(abc < 0 && abd < 0 && bcd < 0 && cad < 0) {
//abc
return [
LineSegment(p1: a, p2: b),
LineSegment(p1: b, p2: c),
LineSegment(p1: c, p2: a)
]
} else if (abc > 0 && abd > 0 && bcd > 0 && cad < 0) ||
(abc < 0 && abd < 0 && bcd < 0 && cad > 0) {
//abcd
return [
LineSegment(p1: a, p2: b),
LineSegment(p1: b, p2: c),
LineSegment(p1: c, p2: d),
LineSegment(p1: d, p2: a)
]
} else if (abc > 0 && abd > 0 && bcd < 0 && cad > 0) ||
(abc < 0 && abd < 0 && bcd > 0 && cad < 0) {
//abdc
return [
LineSegment(p1: a, p2: b),
LineSegment(p1: b, p2: d),
LineSegment(p1: d, p2: c),
LineSegment(p1: c, p2: a)
]
} else if (abc > 0 && abd < 0 && bcd > 0 && cad > 0) ||
(abc < 0 && abd > 0 && bcd < 0 && cad < 0) {
//acbd
return [
LineSegment(p1: a, p2: c),
LineSegment(p1: c, p2: b),
LineSegment(p1: b, p2: d),
LineSegment(p1: d, p2: a)
]
} else if (abc > 0 && abd > 0 && bcd < 0 && cad < 0) ||
(abc < 0 && abd < 0 && bcd > 0 && cad > 0) {
//abd
return [
LineSegment(p1: a, p2: b),
LineSegment(p1: b, p2: d),
LineSegment(p1: d, p2: a)
]
} else if (abc > 0 && abd < 0 && bcd > 0 && cad < 0) ||
(abc < 0 && abd > 0 && bcd < 0 && cad > 0) {
//bcd
return [
LineSegment(p1: b, p2: c),
LineSegment(p1: c, p2: d),
LineSegment(p1: d, p2: b)
]
} else if (abc > 0 && abd < 0 && bcd < 0 && cad > 0) ||
(abc < 0 && abd > 0 && bcd > 0 && cad < 0) {
//cad
return [
LineSegment(p1: c, p2: a),
LineSegment(p1: a, p2: d),
LineSegment(p1: d, p2: c)
]
}
return nil
}
basado en la solución de comingstorm He creado una solución # C que maneja casos degenerados (por ejemplo 4 puntos de línea forma o punto).
https://gist.github.com/miyu/6e32e993d93d932c419f1f46020e23f0
public static IntVector2[] ConvexHull3(IntVector2 a, IntVector2 b, IntVector2 c) {
var abc = Clockness(a, b, c);
if (abc == Clk.Neither) {
var (s, t) = FindCollinearBounds(a, b, c);
return s == t ? new[] { s } : new[] { s, t };
}
if (abc == Clk.Clockwise) {
return new[] { c, b, a };
}
return new[] { a, b, c };
}
public static (IntVector2, IntVector2) FindCollinearBounds(IntVector2 a, IntVector2 b, IntVector2 c) {
var ab = a.To(b).SquaredNorm2();
var ac = a.To(c).SquaredNorm2();
var bc = b.To(c).SquaredNorm2();
if (ab > ac) {
return ab > bc ? (a, b) : (b, c);
} else {
return ac > bc ? (a, c) : (b, c);
}
}
// See https://stackoverflow.com/questions/2122305/convex-hull-of-4-points
public static IntVector2[] ConvexHull4(IntVector2 a, IntVector2 b, IntVector2 c, IntVector2 d) {
var abc = Clockness(a, b, c);
if (abc == Clk.Neither) {
var (s, t) = FindCollinearBounds(a, b, c);
return ConvexHull3(s, t, d);
}
// make abc ccw
if (abc == Clk.Clockwise) (a, c) = (c, a);
var abd = Clockness(a, b, d);
var bcd = Clockness(b, c, d);
var cad = Clockness(c, a, d);
if (abd == Clk.Neither) {
var (s, t) = FindCollinearBounds(a, b, d);
return ConvexHull3(s, t, c);
}
if (bcd == Clk.Neither) {
var (s, t) = FindCollinearBounds(b, c, d);
return ConvexHull3(s, t, a);
}
if (cad == Clk.Neither) {
var (s, t) = FindCollinearBounds(c, a, d);
return ConvexHull3(s, t, b);
}
if (abd == Clk.CounterClockwise) {
if (bcd == Clk.CounterClockwise && cad == Clk.CounterClockwise) return new[] { a, b, c };
if (bcd == Clk.CounterClockwise && cad == Clk.Clockwise) return new[] { a, b, c, d };
if (bcd == Clk.Clockwise && cad == Clk.CounterClockwise) return new[] { a, b, d, c };
if (bcd == Clk.Clockwise && cad == Clk.Clockwise) return new[] { a, b, d };
throw new InvalidStateException();
} else {
if (bcd == Clk.CounterClockwise && cad == Clk.CounterClockwise) return new[] { a, d, b, c };
if (bcd == Clk.CounterClockwise && cad == Clk.Clockwise) return new[] { d, b, c };
if (bcd == Clk.Clockwise && cad == Clk.CounterClockwise) return new[] { a, d, c };
// 4th state impossible
throw new InvalidStateException();
}
}
Tendrá que poner en práctica este texto modelo para su tipo de vector:
// relative to screen coordinates, so top left origin, x+ right, y+ down.
// clockwise goes from origin to x+ to x+/y+ to y+ to origin, like clockwise if
// you were to stare at a clock on your screen
//
// That is, if you draw an angle between 3 points on your screen, the clockness of that
// direction is the clockness this would return.
public enum Clockness {
Clockwise = -1,
Neither = 0,
CounterClockwise = 1
}
public static Clockness Clockness(IntVector2 a, IntVector2 b, IntVector2 c) => Clockness(b - a, b - c);
public static Clockness Clockness(IntVector2 ba, IntVector2 bc) => Clockness(ba.X, ba.Y, bc.X, bc.Y);
public static Clockness Clockness(cInt ax, cInt ay, cInt bx, cInt by, cInt cx, cInt cy) => Clockness(bx - ax, by - ay, bx - cx, by - cy);
public static Clockness Clockness(cInt bax, cInt bay, cInt bcx, cInt bcy) => (Clockness)Math.Sign(Cross(bax, bay, bcx, bcy));
+1: elegante y eficiente. – Tarydon
En realidad, al analizar esto, debería ser un poco más eficiente * y * preciso si primero haces todas las diferencias: ABC = (Ay-Por) * (Cx-Ax) + (Bx-Ax) * (Cy- Ay) [y así sucesivamente para ABD, etc.] – comingstorm
¿Es posible determinar exactamente 'cuadrilátero ABCD'? Experimenté un poco y descubrí que, en algunos casos, el casco convexo es ABCD y en otros ACDB. No estoy súper claro cómo mapear esto. –