Algorithmus zur Umwandlung eines Polygonzuges in einen äquidistanten Polygonzug

23.03.2023, 14:24	SusieSu	Auf diesen Beitrag antworten »
Algorithmus zur Umwandlung eines Polygonzuges in einen äquidistanten Polygonzug Meine Frage: Ich habe eine Reihe von Punkten im 3D-Raum. Diese Punkte stellen die Positionen (den Verfahrweg) für einen Industrieroboter oder eine CNC-Maschine dar. Die Punkte werden von einem Softwareprogramm berechnet. Es können bis zu 10.000 Punkte sein. In den meisten Fällen (aber nicht immer) ist der erste Punkt der Verfahrweges identisch mit dem letzten Punkt, was einen geschlossenen Polygonzug ergibt. Die Abstände zwischen benachbarten Punkten sind nicht gleich. Das Bild zeigt ein Beispiel für einen Teil (einen Ausschnitt) eines solchen Verfahrweges (in diesem Fall in 2D). Für die Weiterverarbeitung der Positionen muss ich einen Algorithmus programmieren, der dafür sorgt, dass die Abstände zwischen benachbarten Punkten gleich sind. Der nicht-äquidistante Polygonzug soll also in einen äquidistanten Polygonzug umgewandelt werden. Eine weitere nützliche Funktion wäre die Möglichkeit, den Abstand zwischen zwei benachbarten Punkten als Parameter einzugeben, um die Gesamtzahl der Ausgabepunkte (oder die Dichte der Punkte) zu steuern. Meine Ideen: Wenn ich es richtig verstanden habe, könnte ich dies mit Catmull-Rom-Splines erreichen. 1. Wären Catmull-Rom-Splines der beste Ansatz hierfür? Oder gibt es andere / bessere / einfachere / effizientere Möglichkeiten, dies zu erreichen? 2. Ich habe viele Online- und Offline-Dokumente zu Catmull-Rom studiert. Es ist mir jedoch nicht klar, was der effizienteste Algorithmus wäre, um mein Problem mit Catmull-Rom zu lösen. Wo kann ich eine Beschreibung einer effizienten Implementierung hierfür finden?
23.03.2023, 14:43	Steffen Bühler	Auf diesen Beitrag antworten »
RE: Algorithmus zur Umwandlung eines Polygonzuges in einen äquidistanten Polygonzug Willkommen im Matheboard! Mit Splines würde ich hier nicht anfangen, das sollte einfacher gehen. Du hast eine Anzahl von Punkten mit xyz-Koordinaten, wenn Du die einzelnen Abstände berechnest, bekommst Du den gesamten Verfahrweg. Den kannst Du durch die Anzahl der Punkte dividieren, dann hast Du die gewünschte Äquidistanz. Damit fährst Du nun das Polygon ab und setzt die Punkte neu. Viele Grüße Steffen
23.03.2023, 15:01	HAL 9000	Auf diesen Beitrag antworten »
Ich verstehe SusieSu so, dass sie den bereits vorhandenen "eckigen" Polygonzug nur als Approximation eines dahinter stehenden "glatteren" krummlinigen Gesamtwegs ansieht. D.h., der Ablauf soll irgendwie so sein. a) Ermittlung eines Splines aus den vorhandenen Punkten. b) Festlegung der neuen äquidistanten Punkte auf diesem Spline. Das nur, wie ich den Beitrag verstanden habe. Wirkliche Hilfe kann ich nicht bieten, da ich von Catmull-Rom-Splines noch nie etwas gehört habe.
23.03.2023, 15:15	SusieSu	Auf diesen Beitrag antworten »
Vielen Dank! Ja, Ziel ist es eine möglichst "glatten" Verlauf hinzubekommen. Daher dachte ich an Splines (wie HAL 9000 beschrieben hat). Nach einigem Lesen, habe ich an Catmull-Rom-Splines gedacht. de.wikipedia.org/wiki/Kubisch_Hermitescher_Spline#Catmull-Rom-Spline Da ich kein Experte auf diesem Gebiet bin, frage ich mich ob dies der "beste" Spline / die "beste" Vorgehensweise für diese Anwendung ist.
23.03.2023, 15:35	Steffen Bühler	Auf diesen Beitrag antworten »
Ob Catmull-Rom, den ich ebenfalls nicht kenne, hier die beste Wahl ist, kann ich auch nicht beantworten. Aber 10000 Punkte mit Splines zu verbinden und dann noch in 3D, das wird ein ziemlicher Rechenaufwand. Ich kann mir auch nicht vorstellen, dass es zu einem großen Fehler führt, wenn man den ursprünglichen Polygonzug als "wahren" Verfahrweg ansieht und auf diesem die Punkte verteilt. Es kommt natürlich auf die geforderte CNC-Genauigkeit an. Wenn hier ein Kreisbogen gefräst werden soll, kann der Ecken bekommen, die außerhalb der Toleranz liegen, wenn die gewählte Punktdichte zu klein ist. Das müsste man vorher prüfen.
23.03.2023, 18:19	Finn_	Auf diesen Beitrag antworten »
Ich mag mal auf das YouTube-Video The Continuity of Splines hinweisen, eine vor kurzem von der Game-Designerin Freya Holmér veröffentliche, ziemlich hochwertig gemachte Einführung. Catmull-Rom-Splines werden bei 48:20 aufgeführt.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »