algorithmus
-
hallo,
ich hab da ein kleines problem, ich weiss nicht in welchem forum ich den thread ablegen soll. und zwar benoetige ich in c/c++ einen algoritmus, der ueberpruefen soll, ob punkte eines polygons (z.b einers rechtecks, vielecks...) beim erstellen (digitalisierung) im uhrezeigersinn oder gegen den uhrzeigersinn abgelegt wurden. sie duerfen naemlich nur im uhrzeigersinn abgelegt werden.
hat jemand eine ahnung wen ich da fragen kann oder wer kann mir weiterhelfen?
-
Die Rubrik ist schon richtig.
Ich hätte eine Idee dazu - weiß aber nicht, ob das den Zweck erfüllt:
Konvertiere alle Koordinaten in ihre Polardarstellung (also aus x,y machst Du Länge,Winkel mit Hilfe von Pythagoras und Arcustangens).
Wenn Du nun die Liste der Punkte durchläufst, so wird beim Durchlauf im Uhrzeigersinn der Wert des Winkels immer größer - gegen den Uhrzeigersinn wird der Wert des Winkels immer kleiner.
Du mußt Dir allerdings was ausdenken, wie Du den Sprung von 0 auf 360 abfängst.
Aber so als Ansatz ist das doch schon mal ein Vorschlag.
-
Bitte ins Mathe-/Physikforum verschieben!
-
mir sieht es fast danach aus, als würde das vorzeichen des vektorprodukts von a[1]-a[0] und a[2]-a[0] stark mit dem umlaufsinn korrelieren.
-
Wenn die 2D Punkte als Liste gegeben sind, die entweder links- oder rechtsrum gegeben sind:
Suche den tiefsten Punkt (y = max) (wenn mehrere dann davon den rechtesten), und hole davon den Vorgaenger und den Nachfolger. Aus den Segmenten dazwischen erstellst du 2 Vektoren. Biegen die Vektoren "nach links ab" => Uhrzeigersinn, sonst gegen den Uhrzeigersinn. Wie volkard schon sagte stellt man das mit dem Vektorprodukt fest.
-Gunnar
-
es gibt auch nichtkonvexe Polygone, die durch die ganannten algos nicht abgedeckt sind.
-
Wieso? Der in meinem Algo gesuchte Punkt ist notwendigerweise konvex, weil es der tiefste Punkt ist. Also funktioniert es auch mit konkaven Polygonen, sogar mit komplexen wo sich die Segmente ueberschneiden, wenn ich es mir so ueberlege.
-Gunnar
-
schau dir mal das "S" an und fahr mal die kontur ab. wie oft bigt man rechts ab? und wie oft links?
-
Wenn ich das S-Polygon im Uhrzeigersinn umwandere, genau einmal linksrum, andersherum rechtsrum. Wo ist das Problem? Ich schau mir ja nur die Orientierung am tiefsten Punkt an.
-Gunnar
-
________
.........___|
......./
......|___
.............\
.............|
______/grad-grad-grad-grad-rechts-rechts- grad - grad-LINKS!!! usw....
-
Hast Du ueberhaupt gelesen was ich geschrieben habe?
-Gunnar