Wypukły kadłub 4 punktów

Question

Chciałbym algorytmu do obliczenia wypukłego kadłuba z 4 punktów 2D. Przyjrzałem się algorytmom uogólnionego problemu, ale zastanawiam się, czy istnieje proste rozwiązanie dla 4 punktów.

Answer 1

Weź trzy punkty, a także określić, czy ich trójkąt jest prawo lub w lewo ::

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

Dla prawoskrętny układ współrzędnych, wartość ta będzie pozytywny, jeśli ABC jest przeciwnie, negatywne dla ruchu wskazówek zegara, i zero, jeśli są współliniowe. Jednak następujące czynności będą działać równie dobrze dla leworęcznego układu współrzędnych, ponieważ orientacja jest względna.

Oblicz porównywalnych wartości dla trójkątów zawierających czwarty punkt:

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) 

Jeśli wszystkie trzy {ABD BCD, CAD} ma taki sam znak, jak ABC, a D jest wewnątrz ABC, a kadłub trójkąt ABC.

Jeśli dwa {ABD, BCD, CAD} mają taki sam znak jak ABC, a jeden ma przeciwny znak, to wszystkie cztery punkty są ekstremalne, a kadłub jest czworoboczny ABCD.

Jeśli jeden z {ABD, BCD, CAD} ma taki sam znak jak ABC, a dwa mają przeciwny znak, wówczas wypukły kadłub jest trójkątem o tym samym znaku; pozostały punkt jest w środku.

Jeśli którakolwiek z wartości trójkąta wynosi zero, trzy punkty są współliniowe, a środkowy punkt nie jest ekstremalny. Jeśli wszystkie cztery punkty są współliniowe, wszystkie cztery wartości powinny wynosić zero, a kadłub będzie albo linią, albo punktem. W takich przypadkach należy wystrzegać się numerycznych problemów związanych z wytrzymałością!

Dla tych przypadków, w których ABC jest pozytywne:

ABC ABD BCD CAD hull 
------------------------ 
+ + + + ABC 
+ + + - ABCD 
+ + - + ABCD 
+ + - - ABD 
+ - + + ABCD 
+ - + - BCD 
+ - - + CAD 
+ - - - [should not happen] 

Answer 2

Oto bardziej ad-hoc algorytm specyficzny do 4 punktów:

• wybrać indeksy punktów z minimalnym-X, maksymalnego X, minimalnej Y i maksymalnej Y i uzyskać unikalne wartości z to. Na przykład indeksy mogą wynosić 0,2,1,2, a wartości unikatowe wynoszą 0,2,1.
• Jeśli istnieją 4 unikalne wartości, wówczas wypukły kadłub składa się ze wszystkich 4 punktów.
• Jeśli występują 3 unikalne wartości, to te 3 punkty znajdują się zdecydowanie w wypukłym kadłubie. Sprawdź, czy czwarty punkt leży w tym trójkącie; jeśli nie, jest to również część wypukłego kadłuba.
• Jeśli są 2 unikalne wartości, to te 2 punkty znajdują się na kadłubie. Z pozostałych 2 punktów punkt znajdujący się dalej od tej linii, łączący te 2 punkty, znajduje się zdecydowanie na kadłubie. Wykonaj test izolacji trójkąta, aby sprawdzić, czy drugi punkt znajduje się również w kadłubie.
• Jeśli występuje 1 unikalna wartość, wszystkie 4 punkty są współwystępujące.

Niektóre obliczenia jest wymagane, jeżeli istnieją 4 punkty zamówić je prawidłowo, tak aby uniknąć coraz muszka kształt. Hmmm .... Wygląda na to, że istnieje wystarczająco dużo specjalnych przypadków uzasadniających użycie uogólnionego algorytmu. Można jednak ustawić to tak, aby działało szybciej niż uogólniony algorytm.

Answer 3

Albo po prostu użyć Jarvis march.

Answer 4

Zrobiłem a proof of concept fiddle w oparciu o prostą wersję algorytmu pakowania prezentów.

Nieefektywne w ogólnym przypadku, ale wystarczające tylko na 4 punkty.

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; 
} 

Było fajnie :)

Answer 5

Pisałem szybki realizację odpowiedź comingstorm za pomocą tabeli odnośników. Przypadek, w którym wszystkie cztery punkty są współliniowe, jest traktowany , a nie, ponieważ moja aplikacja go nie potrzebuje. Jeśli punkty są współliniowe, algorytm ustawia pierwszy wskaźnik punktu [0] na wartość null. Kadłub zawiera 3 punkty, jeśli punkt [3] jest wskaźnikiem zerowym, w przeciwnym razie kadłub ma 4 punkty. Kadłub jest w kolejności przeciwnej do ruchu wskazówek zegara dla układu współrzędnych, w którym oś y wskazuje na szczyt, a oś x na prawo.

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

podstawie @comingstorm odpowiedzi Stworzyłem Swift rozwiązanie:

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

oparciu o rozwiązania comingstorm za Utworzyłem rozwiązanie C#, który obsługuje zdegenerowanych przypadki (np 4 punkty forma wiersza lub punkt).

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(); 
    } 
    } 

Musisz wdrożyć ten boilerplate dla danego typu wektorowego:

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