Hinzufügen eines neuen Punktes zur richtigen Position in einem Array von Punkten
Ich habe ein Polygon mit mehreren Punkten und es muss ein neuer Punkt hinzugefügt werden. Die vorhandenen Punkte werden in einem Array gespeichert:
%Vor% Wie ermitteln Sie die Position des Arrays, in das newPoint eingefügt werden soll?
Versuch: Ich habe alle vorhandenen Punkte iteriert und den Abstand von newPoint berechnet und die vorhandenen Punkte in ein Array mit dem Index dieser Punkte in der Reihenfolge der zunehmenden Entfernung sortiert von newPoint .
Nach der Methode meines aktuellen Versuchs wird als nächster Schritt geprüft, ob die 2 nächstgelegenen Punkte benachbart sind. Wenn dies der Fall ist, fügen Sie das newPoint zwischen ihnen im Array points hinzu. Wenn sie nicht benachbart sind, bin ich irgendwie hier stecken :) Wie überprüfen Sie, ob die 2 Punkte benachbart sind?
Jede Hilfe sehr geschätzt!
jsfiddle: Ссылка
Der Grund, warum die Reihenfolge wichtig ist, ist, dass Formen normalerweise im Uhrzeigersinn gezeichnet werden. Hier sehen Sie eine Datei, in der das blaue Polygon an der richtigen Stelle einen Punkt hinzugefügt hat, und ein rotes Polygon mit einem Punkt, der am Ende des Arrays points hinzugefügt wurde.
jsfiddle: Ссылка
4 Antworten
Okay, lassen Sie uns Polygone genauer betrachten.
Wir nennen ihn Ted. Wenn Ted (oder ein Vieleck im Allgemeinen) einen Punkt sieht, versucht er es in sich aufzunehmen. Und für die Assimilation beschließt er, einer seiner vielen
Da gehen wir, es gibt einen Punkt in Teds Nähe, glückselig nicht bewusst, dass es bald bösartig verzehrt werden wird. Also, wie entscheiden Teds Seiten, welcher den Punkt ergreift? Nun, es muss faires Spiel sein. Die Seite, die feststellt, dass die senkrechte Entfernung von ihr zum Punkt die kürzeste ist, wird derjenige sein, der es tut. Kürzeste . Senkrecht Entfernung .
Assimilation abgeschlossen!
Eine andere Sache, die man beachten sollte ist, dass Polygone wie Ted das Überleben gegenüber der Assimilation schätzen. Die Seite mit dem kürzesten senkrechten Abstand vom Punkt beginnt mit der Assimilation nur dann, wenn die anderen Seiten nicht schneidet . Also, Seiten mit nur valide Assimilation werden berücksichtigt. Sonst passieren schlimme Dinge .
Es gibt zwei wichtige Punkte in meinem unnötigen Spiel;
- Die Seite , zu der wir den Punkt hinzufügen, sollte den kürzesten senkrechten Abstand vom Punkt haben.
- Neben dem kürzesten senkrechten Abstand vom Punkt sollte der Punkt auf dieser Seite gültig sein. Das ist wichtig, schließlich wollen wir keinen Massenpolygonmord verüben.
Also, hier ist ein Pseudo-Code;
%Vor%Die senkrechte Entfernung von der Seite ist leicht zu finden;
%Vor%Sehen wir uns jetzt die Gültigkeit an. Wenn nach dem Hinzufügen des Punktes zum Polygon die neuen Seiten eine der anderen Seiten durchschneiden, ist es für den kleinen Kerl vorbei. Wir müssen sicherstellen, dass unser Algorithmus dies berücksichtigt.
Ich habe mir zwei Versionen ausgedacht; eine billig und eine teuer.
Methode 1 :
Wenn es im Polygon wenig bis keine Konkavität gibt, funktioniert diese Methode perfekt. Diese Methode überprüft nur, dass die neuen Seiten die Seiten neben der alten Seite nicht schneiden.
Sagen wir, wir haben eine Seite S . Es ist zwei benachbarte Seiten sind Sprev und Snext . Die zwei neuen Seiten sind S1p und S2p . S1p und Sprev haben den Punkt S.p1 gemeinsam. S2p und Snext haben den Punkt S.p2 gemeinsam.
Nach dieser Methode ist die Addition genau dann gültig, wenn es keinen Schnittpunkt zwischen:
gibt-
SprevundS2p -
SnextundS1p
Diese Methode funktioniert also bei Ablehnung. Wenn wir keinen Schnittpunkt finden können, kann die Seite S den Punkt gültig hinzufügen.
Methode 2 :
Methode 1 schlägt fehl, da die Konkavität des Polygons zunimmt. Also müssen wir weitere Prüfungen durchführen, um eine gültige Punkthinzufügung sicherzustellen.
Diese Methode ist wirklich eine Erweiterung von Methode 1. Nachdem festgestellt wurde, dass sich die Paare Sprev und S2p und Snext und S1p nicht schneiden, prüfen wir, ob die neuen Seiten sich mit den anderen schneiden Seiten des Polygons (abgesehen von Sprev und Snext , natürlich).
Wenn der Zusatz nicht zurückgewiesen wird, nachdem alle Seiten geprüft wurden, sind wir absolut sicher, dass dieser Zusatz gültig ist.
Das Problem ist, dass während die Zurückweisung schnell genug ist, die Akzeptanz sehr lange dauert, was diese Methode ziemlich teuer macht.
Außerdem hängt die Komplexität von der Anzahl der Seiten des Polygons ab. Wenn die Komplexität des Polygons zunimmt, wird die Gültigkeitsprüfung immer länger dauern.
Ich muss anmerken, dass der Algorithmus, den ich für die Überprüfung der Liniensegmentüberschneidung verwendet hat, aus Rikonator 25.12.2012, 17:08
Wie ich bereits gesagt habe, müssen Sie die Komplexität des Programms nicht wirklich mit sort erhöhen: Sie haben einfach zwei Anfangspunkte gespeichert, die am nächsten liegen, und sie dann ersetzen, wenn Sie den anderen Punkt durchlaufen.
Allerdings hat Ihr Problem mehr als eine mögliche Lösung. Sie müssen weitere Einschränkungen definieren.
Stellen Sie sich zum Beispiel vier Punkte vor, die ein Quadrat bilden:
%Vor%Fügen Sie nun einen Punkt zu einer zufälligen Position innerhalb des Polygons hinzu:
%Vor%Es gibt mehr als zwei mögliche Ordnungen, die Ihr Polygon konvex beibehalten:
%Vor%Ich glaube, dass Ihre Berechnung das Problem, das Sie erleben, nicht löst. Nehmen Sie beispielsweise die folgenden zwei Polygone:
%Vor%Der nächste Punkt ist nicht unbedingt derjenige, der als nächstes gezeichnet werden sollte.
The reason why the order matters is because Shapes are usually drawn in a clockwise manner.
Sie haben gerade Ihre Frage beantwortet. Wo Sie den neuen Punkt hinzufügen, hängt davon ab, welche Form Sie wollen und hat daher nichts mit Entfernung zu tun. Sie fügen einfach den Punkt an der Stelle hinzu, an der er gezeichnet werden soll.
Sagen Sie, wissen Sie bereits, wie die Form sein soll, oder müssen Sie die Form anhand des Klicks eines Benutzers erraten? Wenn Sie raten müssen, müssen Sie möglicherweise ein Standardverhalten festlegen. Andernfalls geben Sie Ihrem Benutzer einen zusätzlichen Parameter.
Tags und Links javascript algorithm jquery canvas graphics