Scafo convesso di 4 punti

Question

Vorrei un algoritmo per calcolare lo scafo convesso di 4 punti 2D. Ho esaminato gli algoritmi per il problema generalizzato, ma mi chiedo se esiste una soluzione semplice per 4 punti.

Answer 1

Prendere tre punti, e determinare se il triangolo è in senso orario o antiorario ::

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

Per un sistema di coordinate destrorso, questo valore sarà positivo se ABC è antiorario, negativa per orario, e zero se sono collineari. Tuttavia, quanto segue funzionerà altrettanto bene per un sistema di coordinate mancino, in quanto l'orientamento è relativo.

calcolare i valori comparabili per tre triangoli contenenti il ​​quarto 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) 

Se tutte e tre {ABD, BCD, CAD} hanno lo stesso segno di ABC, allora D è all'interno ABC, e lo scafo è triangolo ABC.

Se due di {ABD, BCD, CAD} hanno lo stesso segno di ABC e uno ha il segno opposto, tutti e quattro i punti sono estremi e lo scafo è quadrilatero ABCD.

Se uno di {ABD, BCD, CAD} ha lo stesso segno di ABC e due hanno il segno opposto, lo scafo convesso è il triangolo con lo stesso segno; il punto rimanente è al suo interno.

Se uno dei valori del triangolo è zero, i tre punti sono collineari e il punto medio non è estremo. Se tutti e quattro i punti sono collineari, tutti e quattro i valori dovrebbero essere zero e lo scafo sarà una linea o un punto. Attenzione ai problemi di robustezza numerica in questi casi!

Per quei casi in cui ABC è positivo:

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

Answer 2

Ecco un altro algoritmo specifico a 4 punti-hoc:

• Trova gli indici dei punti con un minimo-X, massimo-X, minima-Y e il massimo-Y e ottenere i valori unici da Questo. Ad esempio, gli indici possono essere 0,2,1,2 e i valori unici saranno 0,2,1.
• Se ci sono 4 valori univoci, lo scafo convesso è composto da tutti e 4 i punti.
• Se ci sono 3 valori unici, questi 3 punti sono sicuramente nello scafo convesso. Controlla se il 4 ° punto si trova all'interno di questo triangolo; se no, fa anche parte dello scafo convesso.
• Se ci sono 2 valori univoci, questi 2 punti si trovano sullo scafo. Degli altri 2 punti, il punto che è più lontano da questa linea che unisce questi 2 punti è sicuramente sullo scafo. Effettua un test di contenimento a triangolo per verificare se anche l'altro punto si trova nello scafo.
• Se è presente 1 valore univoco, tutti i 4 punti coincidono.

Alcuni calcolo è necessaria se ci sono 4 punti per ordinare correttamente in modo da evitare di ottenere un cravattino forma. Hmmm .... Sembra che ci siano abbastanza casi speciali per giustificare l'uso di un algoritmo generalizzato. Tuttavia, è possibile ottimizzarlo per eseguire più rapidamente di un algoritmo generalizzato.

Answer 3

o semplicemente usare Jarvis march.

Answer 4

Ho fatto a proof of concept fiddle basato su una versione grezza dell'algoritmo di confezionamento regalo.

Non efficiente nel caso generale, ma sufficiente per solo 4 punti.

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

E 'stato divertente :)

Answer 5

ho scritto una rapida implementazione della risposta di comingstorm utilizzando una tabella di ricerca. Il caso in cui tutti e quattro i punti sono paralleli è non trattati poiché la mia applicazione non ne ha bisogno. Se i punti sono paralleli, l'algoritmo imposta il primo punto del puntatore [0] su null. Lo scafo contiene 3 punti se il punto [3] è il puntatore nullo, altrimenti lo scafo ha 4 punti. Lo scafo è in senso antiorario per un sistema di coordinate in cui l'asse y punta verso l'alto e l'asse x verso destra.

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

in base alla risposta @comingstorm ho creato soluzione 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

Sulla base di soluzione di comingstorm Ho creato una soluzione C# che gestisce casi degeneri (per esempio 4 punti di linea 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(); 
    } 
    } 

Avrai bisogno di implementare questa boilerplate per il vostro tipo di vettore:

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