Sortieren Four Points im Uhrzeigersinn

Question

Vier 2D-Punkte in einem Array. Ich brauche sie im Uhrzeigersinn zu sortieren. Ich denke, es kann mit nur einem Swap-Operation durchgeführt werden, aber ich habe nicht in der Lage gewesen, dies formell niederzulegen.

Edit: Die vier Punkte sind ein konvexes Polygon in meinem Fall

.

Edit: Die vier Punkte sind die Eckpunkte eines konvexen Polygons. Sie müssen nicht in Ordnung sein.

Answer 1

Wenn Sie eine mathematische Perspektive nehmen wollen, können wir die Permutationen von 4 Punkten berücksichtigen

In unserem Fall gibt es 4 Permutationen, die im Uhrzeigersinn sind

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

Alle anderen möglichen Permutationen können auf eine dieser Formen mit 0 oder 1 Swaps umgewandelt werden. (Ich werde nur Permutationen betrachten mit A durch, da er symmetrisch ist)

1. A B C D - fertig
2. A B D C - Swap-C und D
3. A C B D - Swap B und C
4. A C D B - Swap A und B
5. A D B C - Swap A und D
6. A D C B - Swap B und D

Somit ist nur eine Swap jemals gebraucht wird -. Aber es kann einige Arbeit zu identifizieren zu ergreifen, die

Mit dem in den ersten drei Punkte beobachtet, und die Überprüfung der Zeichen des unterzeichneten Bereich von ABC, können wir bestimmen, ob sie im Uhrzeigersinn sind oder nicht. Wenn sie im Uhrzeigersinn, dann sind wir im Fall 1 2 oder 5

zwischen diesen Fällen zu unterscheiden, haben wir zwei weitere Dreiecken zu überprüfen -. Wenn ACD im Uhrzeigersinn sind, dann können wir diese verengen zu Fall 1, andernfalls wir in Fall sein, müssen 2 oder 5

Zur Aufnahme zwischen den Fällen 2 und 5, können wir ABD testen

Wir können für den Fall von ABC überprüfen gegen den Uhrzeigersinn ähnlich.

Im schlimmsten Fall haben wir drei Dreiecken zu testen.

Wenn Sie Ihre Punkte nicht konvex sind, würden Sie das Innere Punkt finden, um den Rest sortieren, und fügen Sie dann in jedem Rand. Beachten Sie, dass, wenn der konvexe quad dann 4 Punkte ist nicht mehr eindeutig die quad bestimmen, gibt es 3 gleichermaßen gültig Quads.

Answer 2

Ein paar Gedanken wert hier zu berücksichtigen;

• Im Uhrzeigersinn ist nur sinnvoll in Bezug auf einen Ursprung. Ich würde dazu neigen, von der Entstehung als Schwerpunkt einer Reihe von Punkten zu denken. z.B. Im Uhrzeigersinn relativ zu einem Punkt an der mittleren Position der vier Punkte, anstatt die möglicherweise sehr weit entfernte Ursprung.

• Wenn Sie vier Punkte, a, b, c, d, gibt es mehr im Uhrzeigersinn Anordnungen dieser Punkte um den Ursprung. Wenn beispielsweise (a, b, c, d) eine im Uhrzeigersinn Ordnung gebildet, so dass (b, c, d, a), (c, d, a, b) und (d, a, b, c)

• Haben Ihre vier Punkte bereits ein Polygon bilden? Wenn ja, ist es eine Frage der Kontrolle und der Wickel anstatt Sortieren der Punkte Umkehr, z.B. a, b, c, d wird d, c, b, a. Wenn nicht, würde ich auf der Grundlage Sortieren der Verbindung zwischen jedem Punkt Lager und dem Ursprung, nach Wedges Antwort.

Edit: in Bezug auf Ihre Kommentare zu welchen Punkten zu tauschen;

Im Fall eines Dreiecks (a, b, c), können wir sagen, dass es im Uhrzeigersinn ist, wenn der dritte Punkt c , auf der rechten Seite der Linie ist ab . Ich verwende die folgende Seite Funktion dies auf den Koordinaten des Punktes zu bestimmen;

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

Wenn ich eine Vierpunkt konvexes Polygon haben, (a, b, c, d), kann dies als I betrachten zwei Dreiecke, (a, b, c) und (c, d, a). Wenn (a, b, c) im Gegenuhrzeigersinn ist, I den Wicklungs ändern (a, b, c, d) zu (a, d, c, b), um die Wicklung des Polygons als Ganze zu ändern, um im Uhrzeigersinn.

Ich empfehle dies mit einigen Abtastpunkten zeichnen, um zu sehen, was ich rede. Beachten Sie eine Menge von Ausnahmefällen zu tun haben, wie zum Beispiel konkave Polygone, kollineare Punkte, übereinstimmend Punkte, etc ...

Answer 3

Wenn jemand interessiert ist, hier ist meine schnelle und schmutzige Lösung für ein ähnliches Problem.

Mein Problem war, mein Rechteck Ecken in der folgenden Reihenfolge bestellt hat:

  

oben links> rechts oben> unten rechts> links unten

Im Grunde ist es Uhrzeigersinn von der oberen linken Ecke beginnen.

Die Idee für den Algorithmus ist:

die Ecken durch Reihen bestellen und dann Ecke Paare bestellen, indem cols.

// 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 ist richtig. Dieser Code (Gemeinde wikified) erzeugt und sortiert alle möglichen Kombinationen aus einer Anordnung von 4 Punkten.

#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

Berechne die Fläche von den Koordinaten mit der shoelace Formel (entleerten des Absolutwertes derart, dass der Bereich, positiv oder negativ sein kann) für jeweils Punkte Permutationen. Die maximalen Flächenwerte scheinen zu entsprechen einfache Vierecken zu richten: einfache Direktvierecke mit der shoelace Formel

Answer 6

es Arbeit des langen Weg aus dann optimieren.

Ein spezifischeres Problem wäre, um die Koordinaten zu sortieren, um einen Winkel relativ zu der positiven x-Achse abnimmt. Dieser Winkel im Bogenmaß wird durch diese Funktion angegeben werden:

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

Dann, natürlich, es ist nur eine Frage der Koordinaten durch den Winkel zu sortieren. Beachten Sie, dass arctan (w)> arctan (z), wenn und nur wenn x> z, so dass Sie eine Funktion optimieren, die ziemlich leicht Winkel zueinander vergleicht.

Sortieranlagen so dass der Winkel monoton abnehmend über ein Fenster (oder so, dass sie höchstens einmal erhöht) ist ein bisschen anders.

Anstelle einem umfangreichen Beweis werde ich erwähnen, dass ich festgestellt, dass eine einzelne Swap-Operation 4 2D-Punkte im Uhrzeigersinn sortiert werden. die Bestimmung der Austauschoperation erforderlich ist, ist der Trick, natürlich.

Answer 7

Ich habe eine weitere Verbesserung meiner vorherigen Antwort hinzufügen

erinnern -. Das sind die Fälle, die wir in sein

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

Wenn ABC gegen den Uhrzeigersinn (negativen unterzeichnet Bereich) ist, dann sind wir in den Fällen, 3, 4, 6. Wenn wir B & C in diesem Fall tauschen, dann sind wir mit den folgenden Möglichkeiten haben:

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

Als nächstes können wir prüfen für ABD und Swap-B & D, wenn es gegen den Uhrzeigersinn (Fälle 5, 6)

ist

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

Schließlich brauchen wir ACD und Swap-C & D überprüfen, ob ACD gegen den Uhrzeigersinn ist. Jetzt wissen wir, unsere Punkte alle in Ordnung sind.

Diese Methode ist nicht so effizient wie meine früheren Verfahren - das 3 prüft jedes Mal erfordert, und mehr als einen Swap; aber der Code wäre viel einfacher sein.

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

Wo Bezugspunkt liegt innerhalb des Polygons.

Weitere Informationen zu dieser Website

Answer 9

, wenn Sie nur mit 4 Punkten befassen müssen, dann gibt es eine sehr einfache Art und Weise zu tun, dass

1. sortiert nach y-Wert

2. obere Reihe die ersten beiden Punkte sind, untere Reihe der Rest 2 Punkte

3. für obere und untere Reihe, sortiert sie durch x-Wert

.

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

Ich glaube, du hast Recht, dass eine einzelne Swap, dass ein Polygon, das durch vier Punkte in der Ebene dargestellt gewährleisten kann, ist konvex. Die Fragen, die beantwortet werden bleiben, sind:

• Ist dieser Satz von vier Punkten eine konvexe Polygon?
• Wenn nein, dann die zwei Punkte müssen ausgetauscht werden?
• Welche Richtung ist im Uhrzeigersinn?

Bei der weiteren Reflexion, ich denke, dass die einzige Antwort auf die zweite Frage oben ist „die Mitte zwei“.

Answer 11

Wie wäre das?

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

Ideen?

Answer 12

Sie sollten bei der Grahams Scan einen Blick darauf werfen. Natürlich müssen Sie es anpassen, da sie gegen den Uhrzeigersinn auf die Punkte findet.

P. S: Dies könnte viel des Guten für 4 Punkte, aber wenn die Anzahl der Punkte erhöhen könnte es interessant sein,

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.

Der erste 'if / elif' bringt die vier Punkte im Uhrzeigersinn oder entgegen dem Uhrzeigersinn. (Da Ihr Polygon konvex ist, die einzige andere ‚Kreuzung‘ Alternative ‚AC kreuzt BD‘, was bedeutet, dass die vier Punkte sind bereits sortiert.) Das letzte ‚wenn‘ invertiert Orientierung, wenn es gegen den Uhrzeigersinn.

Answer 14

Wenn wir diesen Punkt x größer ist als Punkt y annehmen, wenn der Winkel, den sie mit dem Punkt hat (0,0) größer ist, dann können wir diese auf diese Weise in c # implementieren

    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

Wedges Antwort korrekt ist.

es leicht zu implementieren, denke ich, die gleiche Art und Weise wie smacl: Sie müssen die Grenze Zentrum finden und Ihre Punkte zu diesem Zentrum übersetzen

.

Wie folgt aus:

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

Dann verringern centerPointX und centerPointY von jedem poin, um es zu Grenze des Ursprungs zu übersetzen.

Schließlich gilt Wedge-Lösung mit einem Dreh. Den absoluten Wert von arctan Get (x / y) für jede Instanz (arbeitete für mich, dass die Art und Weise)

Answer 16

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

Die ‚>‘ könnte die falsche Art und Weise gegenüberstehen, aber Sie bekommen die Idee.