Выпуклый корпус из 4-х точек

Question

Я бы хотел, чтобы алгоритм вычислил выпуклую оболочку из четырех 2D-точек. Я рассмотрел алгоритмы для обобщенной проблемы, но мне интересно, есть ли простое решение для 4 пунктов.

Answer 1

Возьми три из точек, и определить, является ли по часовой стрелке или против часовой стрелки ::

triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y) 

их треугольник Для правосторонней системы координат, это значение будет положительным, если ABC против часовой стрелки, отрицательный для часовой стрелки, и ноль, если они коллинеарны. Но для левосторонней системы координат будет справедливо следующее: ориентация относительна.

Compute сопоставимые значения для трех треугольников, содержащих четвертую точку:

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] 

Answer 2

Вот более одноранговой алгоритм конкретных 4 пунктов:

• НАЙДИТЕ индексы точек с минимальным-X, максимум-X, минимальный-Y и максимальной-Y и получить уникальные значения из это. Например, индексы могут быть 0,2,1,2, а уникальные значения - 0,2,1.
• Если имеется 4 уникальных значения, то выпуклая оболочка состоит из всех 4 точек.
• Если есть 3 уникальных значения, то эти 3 точки определенно находятся в выпуклой оболочке. Проверьте, находится ли 4-й пункт в этом треугольнике; если нет, то он также является частью выпуклой оболочки.
• Если есть 2 уникальных значения, то эти 2 точки находятся на корпусе. Из остальных 2 пунктов точка, которая находится дальше от этой линии, соединяющей эти 2 точки, определенно находится на корпусе. Сделайте тест сдерживания треугольника, чтобы проверить, находится ли другая точка в корпусе.
• Если есть 1 уникальное значение, то все 4 точки сопутствуют.

Некоторые вычисления не требуется, если есть 4 точки, чтобы правильно заказать их таким образом, чтобы избежать получать лук галстук форму. Хммм ... Похоже, что есть достаточно особых случаев, чтобы оправдать использование обобщенного алгоритма. Тем не менее, вы можете настроить это, чтобы работать быстрее, чем обобщенный алгоритм.

Answer 3

Или просто использовать Jarvis march.

Answer 4

Я сделал a proof of concept fiddle на основе грубой версии алгоритма упаковки подарка.

Неэффективен в общем случае, но достаточно всего 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; 
} 

Это было весело :)

Answer 5

Я написал быструю реализацию ответа comingstorm, используя таблицу поиска. Дело в том, что все четыре точки являются colinear: не, так как мое приложение не нуждается в нем. Если точки коллинеарны, алгоритм устанавливает первую точку указателя [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]]; 
} 

Answer 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 

} 

Answer 7

На основании решения comingstorm, я создал решение C#, который обрабатывает вырожденные случаи (например, 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/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(); 
    } 
    } 

Вы должны реализовать эту шаблонного для векторного типа:

// 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));