Punkte Ordnen

[wulfgang]

Hallo,

ich habe folgendes Problem. Eine Liste mit zufälligen Punkten auf einer Zeichenfläche mit Koordinaten. Diese Punkte sollen Eckpunkte für ein nicht überschlagendes Polygon sein. Die Verbindungslinien der Punkte sollen sich also nicht kreuzen. Dafür muss ich die Punkte ja irgendwie ordnen.

Kennt jemand hierfür einen Algorithmus? Gibt es dafür überhaupt einen????????

[MartinSt]

willst du die Punkte "nur" ordnen oder das/ein passendes Polygon ermitteln/zeichnen?

[wulfgang]

Guten Morgen,

also ich möchte die Punkte erst ordnen und dann das Polygon zeichnen. Die Zeichenfunktion verbindet Punkte, die ihr direkt hintereinander übergeben wurden. Deswegen möchte ich halt vor dem Zeichnen ordnen.

[Klotzkopp]

Ich würde einen beliebigen Punkt innerhalb der Punktwolke wählen (z.B. den Mittelpunkt aller Punkte), und von dort aus reihum gehen, also nach Winkel sortieren.

[MartinSt]

Moin,

wenn ich jetzt nicht gerade auf der Leitung stehe, ist das sich ergebende Polygon und damit die zugrundeliegende Ordnung sowieso nicht eindeutig.

Gruß Martin

[Ezra]

Du musst lediglich nach dem x-Wert der Punkte sortieren. Nimm einfach einen der bekannten Sortieralgorithmen (Bubblesort oder Selectionsort wären sehr einfach umzusetzen).

[Crush]

@Ezra: Wieso sollte das Polygon richtig gezeichnet werden, wenn es die Koordinaten nach x sortiert sind? Dein Vorschlag scheint mir absolut unlogisch zu sein und paßt nur bei Darstellungen von Graphen mit fortschreitendem x- oder y-Verlauf.

@Klotzkopp: Deine Methode würde nur bei konvexen Polygonen zuverlässig funktionieren und bei Konkaven wär´s ein Spiel mit dem Glück, da das Funktionieren doch sehr von der Form abhängig ist. Bei einem Stern mit ungleich verteilten Zacken würde das schon nicht mehr funktionieren.

Ob folgende Methoden in jedem Fall funktionieren, da wäre ich vorsichtig das zu behaupten, allerdings sind diese sicherlich etwas zuverlässiger als die Vorhergehenden.

Wenn man ganz sicher gehen will, startet man bei den beiden naheliegendsten Punkten und scannt von dieser Linie aus wie Klotzkopp gesagt hat im oder gegen den Uhrzeigersinn bis der nächste Punkt auftaucht. Der Rotationspunkt wäre dann der zuletzt detektierte Punkt. Diese Punkte müssen aus der Gesamtheit der Punkte für die nächsten Prüfungen entfernt werden. Nun wird das die aktuelle Linie (also auch der Startwinkel) und der Vorgang wird bis zum Ende wiederholt. Das ist aber extrem rechenintensiv und langsam.

Schneller wäre es, von jedem Punkt zu jedem anderen Punkt eine Linie zu zeichnen und dabei minx/miny/maxx/maxy zu merken und um 1 Pixel zu vergößern. Nun verwendest Du ein Invertier-Bit, welches beim folgenden Durchlauf immer geswitched wird. Du prüfst im umgebenden Rechteck jede Zeile von links nach rechts Pixel für Pixel ab, ob der aktuelle Pixel und der nachfolgende Pixel die gleiche Farbe hat. Ist das nicht so, wird das Invertierbit gexort und der Inhalt des aktuellen Pixel falls das Invertierbit 1 ist auch gexort, ansonsten wird der Pixel übersprungen.

Man könnte mit einem Trick den Algorithmus noch mehr vereinfachen und beschleunigen, allerdings würde das eine eigene Linienzeichenroutine erfordern, deren Beschreibung allerdings etwas komplizierter ist als dieser Ablauf (Lineplot-Algorithmus gexort mit max 1 Pixel pro Linie in Zeichenrichtung). Danach müßte man aber nur noch das Recheck pixelweise mit dem Invertierbit xoren ohne vorhergehende oder nachfolgende Pixel miteinander zu vergleichen, sondern nur den aktuellen Punkt.

Fall die Polygone nur die außenliegenden Grenzflächen darstellen sollen, dann müßtest Du mit einem weiteren Vorgang mit fast der gleichen Routine die innenliegenden Pixel entfernen, nur wird dann geprüft, ob die Pixel gleich (gesetzt) sind und dann würde man eoren.

Bearbeitet 28. November 2009 von Crush

[Klotzkopp]

@Klotzkopp: Deine Methode würde nur bei konvexen Polygonen zuverlässig funktionieren und bei Konkaven wär´s ein Spiel mit dem Glück, da das Funktionieren doch sehr von der Form abhängig ist. Bei einem Stern mit ungleich verteilten Zacken würde das schon nicht mehr funktionieren.

Warum nicht? Wenn jeder Punkt einen anderen Winkel hat, klappt das problemlos, bei jeder Form. Nur wenn zwei oder mehr Punkte denselben Winkel haben (also mit dem gewählten auf einer Geraden liegen), dann muss man ein wenig aufpassen, dass man die richtige Reihenfolge wählt. Oder man wählt einfach einen anderen Punkt, der eben nicht mit zwei anderen auf einer Geraden liegt.

[Bubble]

Was ist mit Polygonen, die im Inneren ein oder mehrere Einbuchtungen haben? Beispielsweise welche, die eine U-Form oder eine Schneckenform haben?

Bearbeitet 28. November 2009 von Bubble

[Klotzkopp]

Was ist mit Polygonen, die im Inneren ein oder mehrere Einbuchtungen haben? Beispielsweise welche, die eine U-Form oder eine Schneckenform haben?

Es geht doch darum, aus einer Menge von Punkten ein überschneidungsfreies Polygon zu konstruieren. Die Ausgangslage ist eine Punktwolke, kein fertiges Polygon. Es gibt auch keine Anforderung, die Streckenlänge oder die Fläche zu minimieren. Mein Algorithmus erzeugt krakelige Sterne, aber er erfüllt die Aufgabenstellung.

[Bubble]

Es gibt auch keine Anforderung, die Streckenlänge oder die Fläche zu minimieren. Mein Algorithmus erzeugt krakelige Sterne, aber er erfüllt die Aufgabenstellung.

Wenn irgendeine beliebige Form ausreicht und der Ursprung innerhalb der Polygonfläche liegt, kann man natürlich so etwas machen. Ich frage mich aber, ob hinter der Frage nicht vielleicht doch eine etwas andere Problemstellung steckt, die nicht mitgeteilt wurde.

[Ezra]

Ach, ich hab da was verwechselt.

[wulfgang]

Hallo,

danke erstmal für die Antworten. Nein eine konkrete Aufgabenstellung habe ich nicht. Dachte auch es sei einfacher umzusetzen...