Geometrie : Kanten-Linen- Koordinaten "vereinfachen"
-
Guten Abend,
ich habe Geometrie Koordinaten, wobei die Kanten der Geometrien aus einer Vielzahl aus Punkten (Koordinaten) bestehen. Nun will ich daraus nur die "Eck" Koordinaten simplifizieren.
Gibt es dafür einen Algorithmus.. ich suche einen Stichwort^^
Vielen Dank, und schönen Abend
-
Meinst du eine normale Boundingbox? Für die musst du einfach alle Maxima bestimmen.
Wahrscheinlich meinst du aber eine konvexe Hülle, dafür gibt es zum Beispiel
https://de.wikipedia.org/wiki/Graham_Scan
https://de.wikipedia.org/wiki/QuickHull
https://de.wikipedia.org/wiki/Chans_AlgorithmusAber dafür findest du auch zigfach fertigen Code im Netz, einfach mal nach convex hull suchen.
-
@yahendrik sagte in Geometrie : Kanten-Linen- Koordinaten "vereinfachen":
konvexe Hülle
hab gerade geschaut "glaube" das meine ich:) Vielen Dank Dir.
Nehmen wir an ich habe einfache Geometrie bspw. ein Rechteck. Um dieses zu beschreiben reichen ja 4 Eckpunkte. Aber ich habe n-Punkte interpolierte Punkte pro Kante zwischen den Eckpunkten, und diese will ich eben rausfiltern...
-
Da gehören eben nur die Eckpunkte rein.
Ich habe auf die Schnelle kein Bild im Netz gefunden, daher habe ich es mal kurz selber hochgeladen:
https://i.imgur.com/iPC54aC.pngDas Polygon ist dunkel, die BBox rosa und die rote Linie ist die konvexe Hülle.
-
@yahendrik Ich habe @SoIntMan da anders verstanden. Er hat eine Menge an Koordinaten die nicht nur die Eckpunkte darstellen sondern teilweise auch zwischen den Eckpunkten auf den Kanten liegen und letztere will er loswerden.
-
@Swordfish exakt, genau das meine ich
.. aber die Konvexe Hülle müsste das Problem lösen @yahendrik da hast du recht..
-
@SoIntMan in dem Fall habe ich nicht geschnallt, daß Dir nicht alle Ecken wichtig sind.
-
@Swordfish doch die sind mir wichtig, dann habe ich das falsch beschrieben
-
@SoIntMan
Oh Mann, du drückst dich wirklich nicht klar aus. Mal meint man du kannst nur das eine meinen und dann wieder nur das andere.Also nochmal:
Wenn der Input ein 5-zackiger Seestern ist, mit vielen zusätzlichen Vertices auf den "Linien". Was willst du dann als Output haben: Einen Seestern ("die Ecken sind wichtig") oder ein 5-Eck (Konvexe Hülle)?
-
@hustbaer Sorry
ich will dann einen Seestern haben (der genaugenommen dann aus 10 "Vertices" besteht
-
@SoIntMan sagte in Geometrie : Kanten-Linen- Koordinaten "vereinfachen":
@hustbaer Sorry
ich will dann einen Seestern haben (der genaugenommen dann aus 10 "Vertices" besteht Was ist die Eigenschaft von 3 Punkten, die auf einer Kante sind? Sie sind auf der selben Gerade.
Dann betrachte einfach immer drei hintereinander stehende Punkte. Wenn die Steigung zwischen A und B identisch mit der Steigung zwischen B und C ist, kannst Du B löschen. Das machst Du so lange, bis es nichts mehr zu löschen gibt.
VG
-
Boah, Steigung ... Division durch Null .... huiiiiiiiii. Ich würd das lieber anders Rechnen
Also vom Prinzip her schon gleich, aber halt ohne Steigung. Winkel zwischen AB und BC oder sowas. Und natürlich net wirklich über den Winkel sondern über eines der Vektorprodukte.
Oder AB und BC erst normalisieren und dann vergleichen. Wobei man beim Normalisieren natürlich wieder aufpassen muss dass man nicht durch 0 dividiert.Und vermutlich wird man beim Vergleichen einen gewissen Fehler erlauben wollen.
-
Bei floting point values muss man sowieso Fehler erlauben. Nur, die Konvexe Hülle tut's nicht. Deswegen meine Nachfrage auf
@SoIntMan sagte in Geometrie : Kanten-Linen- Koordinaten "vereinfachen":
aber die Konvexe Hülle müsste das Problem lösen @yahendrik da hast du recht..
