Я бы хотел, чтобы алгоритм вычислил выпуклую оболочку из четырех 2D-точек. Я рассмотрел алгоритмы для обобщенной задачи, но мне интересно, есть ли простое решение для 4 точек.
Выпуклый корпус из 4 точек
Ответ 1
Возьмите три точки и определите, будет ли их треугольник по часовой стрелке или против часовой стрелки::
triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)
Для правой системы координат это значение будет положительным, если ABC против часовой стрелки, отрицательное значение по часовой стрелке и ноль, если они коллинеарны. Но для левосторонней системы координат будет справедливо следующее: ориентация относительна.
Вычислить сопоставимые значения для трех треугольников, содержащих четвертую точку:
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)
Если все три из {ABD, BCD, CAD} имеют тот же знак, что и ABC, то D внутри ABC, а корпус - треугольник ABC.
Если два из {ABD, BCD, CAD} имеют тот же знак, что и ABC, и один имеет знак противоположности, то все четыре точки экстремальны, а корпус - четырехугольник ABCD.
Если один из {ABD, BCD, CAD} имеет тот же знак, что и ABC, а два имеют противоположный знак, то выпуклая оболочка - это треугольник с тем же знаком; остальная точка находится внутри него.
Если любое из значений треугольника равно нулю, три точки являются коллинеарными, а средняя точка не является экстремальной. Если все четыре точки коллинеарны, все четыре значения должны быть равны нулю, а корпус будет либо линией, либо точкой. Остерегайтесь проблем с числовой устойчивостью в этих случаях!
В тех случаях, когда ABC положительна:
ABC ABD BCD CAD hull
------------------------
+ + + + ABC
+ + + - ABCD
+ + - + ABCD
+ + - - ABD
+ - + + ABCD
+ - + - BCD
+ - - + CAD
+ - - - [should not happen]
Ответ 2
Или просто используйте Jarvis march.
Ответ 3
Здесь более ad-hoc-алгоритм, специфичный для 4-х точек:
- Найдите индексы точек с минимумом-X, максимумом-X, минимумом-Y и максимумом-Y и получите от него уникальные значения. Например, индексы могут быть 0,2,1,2, а уникальные значения будут равны 0,2,1.
- Если имеется 4 уникальных значения, то выпуклая оболочка состоит из всех 4 точек.
- Если есть 3 уникальных значения, то эти 3 точки определенно находятся в выпуклой оболочке. Проверьте, находится ли 4-й пункт в этом треугольнике; если нет, то он также является частью выпуклой оболочки.
- Если имеется 2 уникальных значения, то эти 2 точки находятся на корпусе. Из остальных 2 пунктов точка, которая находится дальше от этой линии, соединяющей эти 2 точки, определенно находится на корпусе. Сделайте тест сдерживания треугольника, чтобы проверить, находится ли другая точка в корпусе.
- Если есть 1 уникальное значение, то все 4 точки сопутствуют.
Некоторые вычисления необходимы, если есть 4 балла, чтобы правильно их упорядочить, чтобы избежать получения формы лук-галстук. Хммм... Похоже, что есть достаточно особых случаев, чтобы оправдать использование обобщенного алгоритма. Тем не менее, вы можете настроить это, чтобы работать быстрее, чем обобщенный алгоритм.
Ответ 4
Я сделал доказательство концептуальной скрипты на основе грубой версии алгоритма упаковки подарка.
Неэффективен в общем случае, но достаточно всего 4 пункта.
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;
}
Было весело:)
Ответ 5
Я написал быструю реализацию ответного ответа, используя справочную таблицу. Случай, когда все четыре точки коллинеарны, не, поскольку мое приложение не нуждается в нем. Если точки коллинеарны, алгоритм устанавливает первую точку указателя [0] в нуль. Корпус содержит 3 точки, если точка [3] является нулевым указателем, иначе корпус имеет 4 точки. Корпус находится в направлении против часовой стрелки для системы координат, где ось y указывает на верхнюю и ось x вправо.
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]];
}
Ответ 6
На основе ответа @comingstorm я создал решение 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
}
Ответ 7
Основываясь на решении о срочном вызове, я создал решение С#, которое обрабатывает вырожденные случаи (например, 4 точки образуют линию или точку).
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/info/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();
}
}
Вам понадобится реализовать этот шаблон для вашего векторного типа:
// 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));