Ordina quattro punti in ordine orario

Question

Quattro punti 2D in un array. Devo ordinarli in senso orario. Penso che possa essere fatto con una sola operazione di scambio, ma non sono stato in grado di annullarlo formalmente.

Modifica: I quattro punti sono un poligono convesso nel mio caso.

Modifica: i quattro punti sono i vertici di un poligono convesso. Non devono essere in ordine.

Answer 1

Se vuoi prendere una prospettiva più matematica, possiamo considerare le permutazioni di 4 punti

Nel nostro caso ci sono 4 permutazioni che sono in senso orario

A B C D
B C D A
C D A B
D A B C

Tutte le altre possibili permutazioni possono essere convertite in una di queste forme con 0 o 1 swap. (Prenderò in considerazione solo le permutazioni che iniziano con A, in quanto simmetrico)

1. A B C D - fatto
2. A B D C - scambia C e D
3. A C B D - scambia B e C
4. A C D B - scambia A e B
5. A D B C - scambia A e D
6. A D C B - scambia B e D

Pertanto è necessario un solo scambio, ma potrebbe essere necessario del lavoro per identificare quale.

Osservando i primi tre punti e controllando il segno dell'area firmata di ABC, possiamo determinare se sono in senso orario o meno. Se sono in senso orario, allora siamo nel caso 1 2 o 5

per distinguere tra questi casi dobbiamo controllare altri due triangoli - se l'ACD è in senso orario, possiamo restringere questo caso al caso 1, altrimenti dobbiamo essere nel caso 2 o 5.

Per scegliere tra i casi 2 e 5, possiamo testare ABD

Possiamo verificare il caso dell'ABC in senso antiorario in modo simile.

Nel peggiore dei casi dobbiamo testare 3 triangoli.

Se i tuoi punti non sono convessi, potresti trovare il punto interno, ordinare il resto e quindi aggiungerlo in qualsiasi bordo. Nota che se il quad è convesso allora 4 punti non determinano più in modo univoco il quad, ci sono 3 quad ugualmente validi.

Answer 2

Un paio di pensieri che vale la pena considerare qui;

• In senso orario è significativo solo rispetto a un'origine. Tenderei a pensare all'origine come al centro di gravità di un insieme di punti. per esempio. In senso orario rispetto a un punto nella posizione media dei quattro punti, anziché l'origine forse molto lontana.

• Se hai quattro punti, a, b, c, d, esistono più ordini in senso orario di quei punti intorno alla tua origine. Ad esempio, se (a, b, c, d) formasse un ordine in senso orario, lo stesso farebbe (b, c, d, a), (c, d, a, b) e (d, a, b, c)

• I tuoi quattro punti formano già un poligono? In tal caso, si tratta di controllare e invertire l'avvolgimento piuttosto che ordinare i punti, ad es. a, b, c, d diventa d, c, b, a. Altrimenti, vorrei ordinare in base al legame tra ciascun punto e l'origine, secondo la risposta Wedges.

Modifica: riguardo ai tuoi commenti su quali punti scambiare;

Nel caso di un triangolo (a, b, c), possiamo dire che è in senso orario se il terzo punto c si trova sul lato destro della linea ab . Uso la seguente funzione laterale per determinarla in base alle coordinate del punto;

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

Se ho un poligono convesso a quattro punti, (a, b, c, d), posso considerarlo come due triangoli, (a, b, c) e (c, d, a). Se (a, b, c) è in senso antiorario, cambio l'avvolgimento (a, b, c, d) in (a, d, c, b) per cambiare l'avvolgimento del poligono nel suo complesso in senso orario.

Consiglio vivamente di disegnarlo con alcuni punti di esempio, per vedere di cosa sto parlando. Nota che hai molti casi eccezionali da affrontare, come poligoni concavi, punti colinear, punti coincidenti, ecc ...

Answer 3

Se qualcuno è interessato, ecco la mia soluzione rapida e sporca a un problema simile.

Il mio problema era che i miei angoli del rettangolo fossero ordinati nel seguente ordine:

  

in alto a sinistra > in alto a destra > in basso a destra > in basso a sinistra

Fondamentalmente è in senso orario a partire dall'angolo in alto a sinistra.

L'idea per l'algoritmo è:

Ordina gli angoli per riga e quindi ordina le coppie di angoli per colore.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}

Answer 4

Oliver ha ragione. Questo codice (community wikified) genera e ordina tutte le possibili combinazioni di una matrice di 4 punti.

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}

Answer 5

Calcola l'area dalle coordinate con la formula del laccio (devozione del valore assoluto in modo tale che l'area possa essere positiva o negativa) per ogni permutazione dei punti. I valori massimi dell'area sembrano corrispondere a quadrilateri semplici diretti: Quadrilateri diretti semplici trovati con la formula del laccio

Answer 6

Risolvilo a lungo, quindi ottimizzalo.

Un problema più specifico sarebbe quello di ordinare le coordinate diminuendo l'angolo rispetto all'asse x positivo. Questo angolo, in radianti, sarà dato da questa funzione:

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

Quindi, ovviamente, si tratta solo di ordinare le coordinate per angolo. Nota che arctan (w) > arctan (z) se e solo se x > z, così puoi ottimizzare una funzione che confronta abbastanza facilmente gli angoli tra loro.

L'ordinamento in modo tale che l'angolo decresca monotonicamente su una finestra (o che aumenti al massimo una volta) è un po 'diverso.

Al posto di una dimostrazione approfondita, citerò che ho verificato che una singola operazione di scambio ordinerà 4 punti 2D in senso orario. Determinare quale operazione di swap è necessaria è ovviamente il trucco.

Answer 7

Ho un ulteriore miglioramento da aggiungere alla mia risposta precedente

ricorda: questi sono i casi in cui possiamo trovarci.

1. A B C D
2. A B D C
3. A C B D
4. A C D B
5. A D B C
6. A D C B

Se ABC è in senso antiorario (ha un'area con segno negativo), allora siamo nei casi 3, 4, 6. Se scambiamo B & amp; C in questo caso, quindi ci rimangono le seguenti possibilità:

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A D B C
6. A D B C

Successivamente possiamo verificare ABD e scambiare B & amp; D se è in senso antiorario (casi 5, 6)

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A B D C
6. A B D C

Infine, dobbiamo controllare ACD e scambiare C & amp; D se ACD è in senso antiorario. Ora sappiamo che i nostri punti sono tutti in ordine.

Questo metodo non è efficiente come il mio metodo precedente: ciò richiede 3 controlli ogni volta e più di uno scambio; ma il codice sarebbe molto più semplice.

Answer 8

var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

Dove si trova il punto di riferimento all'interno del poligono.

Maggiori informazioni su questo sito

Answer 9

se hai solo bisogno di affrontare 4 punti, allora c'è un modo molto semplice per farlo

1. ordina per valore y

2. la riga superiore indica i primi due punti, la riga inferiore indica gli altri 2 punti

3. per la riga superiore e inferiore, ordinali per valore x

.

corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]

topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]

Answer 10

Credo che tu abbia ragione che un singolo scambio può garantire che un poligono rappresentato da quattro punti nel piano sia convesso. Le domande che rimangono a cui rispondere sono:

• Questo set di quattro punti è un poligono convesso?
• In caso negativo, quali due punti devono essere scambiati?
• Quale direzione è in senso orario?

Su ulteriore riflessione, penso che l'unica risposta alla seconda domanda sopra sia "le due medie".

Answer 11

Che ne dici di questo?

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

idee?

Answer 12

Dovresti dare un'occhiata alla Graham's Scan. Ovviamente dovrai adattarlo poiché trova i punti in senso antiorario.

p.s: potrebbe essere eccessivo per 4 punti, ma se il numero di punti aumenta potrebbe essere interessante

Answer 13

if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

Il primo 'if / elif' porta i quattro punti in senso orario o in senso antiorario. (Dato che il tuo poligono è convesso, l'unica altra alternativa 'incrocio' è 'AC crosses BD', il che significa che i quattro punti sono già ordinati.) L'ultimo "if" inverte l'orientamento ogni volta che è in senso antiorario.

Answer 14

se assumiamo che il punto x sia più grande del punto y se l'angolo che ha con il punto (0,0) è più grande, allora possiamo implementarlo in questo modo in c #

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}

Answer 15

La risposta di Wedge è corretta.

Per implementarlo facilmente, penso allo stesso modo di smacl: devi trovare il centro del confine e tradurre i tuoi punti in quel centro.

In questo modo:

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

Quindi, diminuisci centerPointX e centerPointY da ciascun punto per tradurlo nell'origine del confine.

Infine, applica la soluzione di Wedge con una sola svolta: ottieni il valore assoluto di arctan (x / y) per ogni istanza (ha funzionato per me in questo modo).

Answer 16

if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

Il '>' potrebbe essere nella direzione sbagliata, ma hai capito.