Abstand zwischen zwei Kurven |
| 30.04.2026, 14:21 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
| Abstand zwischen zwei Kurven Ich sitze an einem Projekt bei dem ich eine Ellipse durch Kreissegmente annähern will. Ich will einen Algorithmus basteln, der mir einen Satz mit möglichst wenig Segmenten liefert, welcher einen vordefinierten Maximalabstand nicht überschreitet. Das erste Problem, dass ich dabei habe ist erstmal einen Abstand sinnvoll zu definieren. Da es mir nur um den Maximalabstand geht hab ich nun meine erste Idee und wollte fragen, ob das so richtig ist. Meine Ideen: Seien f und g zwei differenzierbare Funktionen. Nimmt man D(x) = f(x)-g(x) als Abstand, dann ist der Maximalabstand der Betrag eines Extremums von D. Für das Extremum gilt 0 = D'(x_0) = f'(x_0)-g'(x_0) Daraus folgt f'(x_0) = g'(x_0) f' und g' an der Extremstelle sind per Definiton die Steigungen der Tangenten an dieser Extremstelle. Das heißt die Normalen durch diese Stelle sind gleich. Heißt das nun deswegen, dass wenn ich den Abstand entlang der Normalen einer Kurve an einer Stelle ermittele dieser niemals größer als der Maximalabstand sein kann? Dann wäre es relativ simpel. Vom Ursprung des Kreissegment im Winkel phi eine Strecke mit der Ellipse schneiden und der Abstand zwischen Segmentursprung und Schnittpunkt ist f(phi) und der Segmentradius ist g(phi) Das ist für mich nciht ganz klar weil es ja eben Winkel phi gibt wo die Normale durch das Kreissegment nicht die Normale durch die Ellipse ist die durch den Schnittpunkt führt, das gilt eben nur dort wo es Maximal ist, aber wenn eine andere Stelle größer wäre, müsste die ja maximal sein und dementsprechend wieder gelten, irgendwie ist das doch ein Zirkelschluss... |
||||||||||||
| 30.04.2026, 18:41 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Wenn ich mal davon ausgehe, dass man nur den ersten Quadranten einer Ellipse betrachtet (wegen der Symmetrieeigenschaften) und die Ellipse stückweise mit mehr als 2 Kreisradien angenähert werden soll, dann werden die Übergänge von Radius zu Radius sicherlich unstetig sein. Wenn man sich nur 2 Radien zur Aufgabe macht, dann kommt man in die Richtung einer „Korbbogen-Konstruktion“, hat dann aber keinen Einfluss auf die Abstandsgüte mehr, weil durch die Stetigkeit an der „Nahstelle“ der beiden Radien eine berechenbare Ungenauigkeit festgelegt ist. siehe dazu auch die alte Aufgabe … Korbbogen als Näherung zur Ellipse Das Kriterium für die maximale Abweichung soll ja durch den betragsmäßigen Abstand beschrieben werden. Das verstehe ich dann so, dass sobald diese max. Abweichung erreicht ist, ein neuer Radius beginnt bis dieser auch wieder an die Grenze der max. Abweichung stößt usw. – Frage wäre dann: Dürfen diese Abweichungen dann die Ellipse sowohl unterschreiten als auch überschreiten? Dann hat man relativ viele Möglichkeiten, dieses zu realisieren, jedoch keine Eindeutigkeit. Das Kriterium scheint mir da zu schwach. Ich würde da vielleicht noch die Minimierung der Abstandsquadrate je Radien-Segment mit hineinnehmen oder eine andere Überprüfung, um ein Optimum (z.B. annähernde Flächengleichheit???) zu erreichen. Gruß Conny |
||||||||||||
| 30.04.2026, 22:02 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Danke für deine erste Einschätzung. Leider geht es etwas an meiner Frage vorbei. Ich interessiere mich dafür wie man den Abstand zweier Kurven beurteilen kann. Eine erste Überlegung hatte ich dazu, dir mir aber einen Knoten im Kopf macht und unsinnig erscheint. Du geht schon Richtung Konstruktion/Vorgehensweise/Algorithmus Ich mag nebenläufig dazu mehrere Einwände vorbringen.
Aber bitte das führt alles schon viel zu weit.
Bei dem Abstand eines Punktes zu einer Kurve ist es so man arbeitet mit der Normalen durch die Kurve und schaut wo sie den Punkt trifft und an dieser Stelle berechnet man den Punkt zu Punkt Abstand. Aber wie ist es bei zwei Linien, wie bei zwei kurvigen Linien, gibt es ein Rezept? |
||||||||||||
| 01.05.2026, 08:36 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Darin sehe ich das Problem, weil die Ellipse selbst nur die Anforderung der Stetigkeit an allen Punkten bzw. Übergängen erfüllen wird. Sobald man in eine Segmentierung übergeht, wird das Konstrukt aus mehreren Radien (n>2) keine stetigen Übergänge mehr liefern können mit gleichzeitiger Einhaltung eines Maximalabstandes. Zumindest kann ich mir nicht so recht vorstellen, wie das Ergebnis dann aussehen sollte. (Bild/Skizze?) Nur mal angenommen, dass es wirklich möglich wäre und eine Segmentierung mit einer riesigen Anzahl von Radien erfolgt, dann würde quasi eine gestückelte Parallelkontur (also ein konstruktiver Offset) zur Original-Ellipse mit dem Maximalabstand-Wert eine gültige Lösung für die Annäherung sein. Es gäbe dann sogar zwei Extremal-Lösungen, nämlich mit einem max. positiven und einem max. negativen Offset, und es gäbe unendlich viele Parallelkonturen, die dazwischen liegen könnten. - Ich befürchte, dass man den Stetigkeitsanspruch leider über Bord werfen muss und auch mit bestimmten Kriterien/Bedingungen/Restriktionen arbeiten wird müssen, um zu einer eindeutigen Näherungskontur zu gelangen (?). Ansonsten würde ich bei der Abstandsbestimmung vorschlagen, die Normalen von der beschriebenen Original-Ellipse zu nutzen, um einen Schnittpunkt zur der Näherungskontur zu erhalten. Die Abweichung wäre dann der Abstand zwischen dem Ellipsen-Schnittpunkt dieser Normalen und dem Schnittpunkt der Näherung. Dann wünsche ich noch einen erfüllten 1.Mai!!! Gruß Conny |
||||||||||||
| 01.05.2026, 10:06 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Als Konstruktionsstrategie kann ich mir momentan nur folgende Idee vorstellen ... Hat dann aber Unstetigkeiten bei den Übergangspunkten B, C, ... Gruß Conny . |
||||||||||||
| 03.05.2026, 05:43 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Verstehe glaube ich nicht ganz was du mit Unstetigkeit meinst, nach meinem Verständnis wären das Lücken. Du schreibst doch selbst bei B konstruierst so, dass es stetig und einfach differenzierbar ist. Passt doch alles. Ok, du nimmst also auch den Normalenansatz, aber steht dahinter eine Begründung? Vielleicht vergessen wir mal den Hintergrund und kommen zu meiner Frage zurück. |
||||||||||||
| Anzeige | ||||||||||||
|
|
||||||||||||
| 03.05.2026, 21:14 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Sorry, ich war da völlig auf dem falschen Dampfer und am falschen Kurs, weil ich irrigerweise davon ausgegangen bin, dass bei den Stützpunkten (A, B, C , …) eine Tangentenstetigkeit gegeben sein sollte. Da habe ich was hineininterpretiert, was gar nicht benötigt wird. Einfach vergessen!!! Was die Bestimmung des Maximalabstandes anbelangt, würde ich weiterhin die Überprüfung über die Normalen an der Referenzkurve vorschlagen/favorisieren (siehe Skizze). Die pauschale Differenzbildung zwischen 2 Kurven würde nicht den (am nächsten gelegenen) Maximalabstand ergeben. Gruß Conny . |
||||||||||||
| 04.05.2026, 09:58 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Ich habe mir gedanklich mal Schrittfolgen überlegt, die ich beispielsweise bei einer Suche/Überprüfung der Abstände durchführen würde. Der Startpunkt A (z.B. Scheitelpunkt oben) sei gesetzt und der Punkt B ein variabler Ort auf der Ellipse. Dann würde ich den Radius r(A,B) variieren bis ein kleinster Maximalabstand PQ erreicht ist. Diesen Abstand PQ checke ich gegen meinen geforderten Abstands-Sollwert D gegen und entscheide dann, ob links/rechts von Punkt B eine neue Berechnung zu erfolgen hat. Dieses wird solange wiederholt bis PQ = D eintritt. Das wäre dann das erste Segment und die weiteren folgen dann nach demselben Schema bis der Scheitelpunkt ganz rechts erreicht wird und der 1.Quadrant komplett segmentiert ist. (das wäre dann aber nur eine rein individuelle Idee meinerseits) - Sicherlich kann man auch ganz andere Strategien verfolgen. Gruß Conny . |
||||||||||||
| 04.05.2026, 10:34 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Ok, danke, dann werde ich mal damit rumprobieren. Allerdings nehme ich lieber die Normale durch die Näherung. Da das ja immer ein Kreissegment ist, ist das einfacher zu berechnen: Für das Zentrum des Kreissegments (x_0, y_0) ist die Normale (x_0, y_0) + t*(cos(phi), sin(phi)) Ein Schnittpunkt mit der Ellipse erfüllt die Ellipsengleichung Also (x_0+t*cos(phi))^2/A^2 + (y_0+t*sin(phi))^2/B^2 = 1 Dabei ist das lösende t der Abstand des Schnittpunkts zum Kreissegmentzentrum mit |
||||||||||||
| 04.05.2026, 14:03 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Ich habe den Eindruck, dass hier mit t der Krümmungsradius an einem bestimmten Ellipsenpunkt berechnet wird, weil sowohl durch die Gleichsetzung der Punkte als auch der Normalen der Kreis und die Ellipse tangential anliegen. Ließe sich kontrollieren mit ... Krümmungsradien Ellipse Gruß Conny |
||||||||||||
| 06.05.2026, 09:08 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Subtrahiert man den Kreisradius erhält man die Normalendistanz. Kreis und Ellipse müssen sich nicht berühren bei phi. Tangentensteigung ist dort allerdings gleich, muss sie auch sein, da Maximum vorliegt. |
||||||||||||
| 06.05.2026, 11:17 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Wenn ein beliebiger Kreismittelpunkt innerhalb der Ellipse gegeben ist und von dort unter einem Winkel (hier soll sowohl die Normale vom Kreis als auch die von der Ellipse gleich sein) ein Schnittpunkt P mit der Ellipse konstruiert wird, dann hat der sich ergebende Abstandsradius den Wert , der zugleich der Krümmungsradius der Ellipse am Schnittpunkt P ist. Oder? Man kann jetzt natürlich eine Normalen-Distanzberechnung daraus basteln mit der Differenz , wobei A und B die Segmentierungs-Schnittpunkte links und rechts vom Punkt P sind. wäre dann der Kreisradius von diesem Segment. Das hieße aber dann, ich müsste als Parameter den Kreismittelpunkt bzw. Krümmungskreismittelpunkt der Ellipse vorgeben, sprich die Evolute der Ellipse mit einbeziehen. Gruß Conny |
||||||||||||
| 06.05.2026, 12:10 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Aah, ich sehe meinen Fehler ein! Nur wenn Punkte der Evolute sind, dann haben wir den Krümmungsradius!!! Aber über das Hilfsmittel der Evolute hat man durchaus eine weitere Strategie zur Distanzmessung gewonnen. Ich versuche mal daraus meinen Gedanken zu skizzieren. Gruß Conny |
||||||||||||
| 06.05.2026, 15:50 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Hier mal eine Skizze, wie ich das bisher verstanden habe. Wenn man sich ein Kreismittelpunkt wählt, dann muss bzgl. des Punktes P (dort wo die Distanz PQ gemessen werden soll) die Normale des Kreises die Evolute der Ellipse bei tangieren. Wird hinzukommend ein Punkt A vorgegeben, dann ergeben sich der Radius R und auch der Schnittpunkt B. Wird hingegen R vorgegeben, dann ergeben sich die Schnittpunkte A und B. Das funktioniert dann auch nur, wenn zwischen A und B kein weiterer Schnittpunkt mit dem Radius R erzeugt wird. Gruß Conny . |
||||||||||||
| 09.05.2026, 22:11 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Hm, da weiß ich noch nicht ganz, was das für mich bedeuten könnte. Ich schildere mal mein angestrebtes Verfahren. Ellipse in schwarz, Approximationssegment in rot. (Nebenüberlegungen in anderen Farben) Dabei ist für mich ja wichtig, dass möglichst wenig Segmente benötigt werden. Daher liegt es nahe nach Möglichkeiten zu suchen, die möglichst lange ein Segment nahe an der Ellipse entlangführen. Schritt 1: Ellipse wird vorgegeben als große und kleine Halbachsenwerte A, B, Delta_Max als Maximalabweichung. Schritt 2: Wähle erstes Segmentzentrum (aus Symmetrieüberlegung und Erweiterbarkeit von einem Viertelzu ganzen Ellipse, muss dieses Zentrum auf einer Halbachse liegen) O.B.d.A starten wir auf der großen Halbachse. Daraus folgt y_0=0. Für x_0 betrachte den Scheitelkrümmungskreis (grün). Dieser berührt die Ellipse auf der Achse, liegt ansonsten vollständig innerhalb -> Verschenkt damit also die erlaubte Abweichung nach außerhalb. Zum Einen könnte man also den Scheitelkrümmungskreis in positive x-Richtung verschieben, um die Abweichung mehr auszunutzen (orange). Eine deutlich bessere Strategie ist es hingegen den Scheitelkrümmungskreis stattdessen in negative x-Richtung zu verschieben um genau Delta_Max, dann den Radius r_0 zu erhöhen bis dieser Kreis die äußere Abweichung ausreizt. (Ist Delta_Max sehr groß gewählt, kann es besser darstellen, aber die Approximation wird zu einfach für die weiteren Überlegungen) Schritt 3: Wähle einen Winkel phi_0 auf dem ersten Kreissegment und einen Radius r_1 > r_0. Betrachte den Winkel a, eine tangentiale Erweiterung (r_1 = unendlich) überschreitet sofort Delta_Max innerhalb, jeder kleinere Radius also auch => phi_0 < a. Generell möchte man phi jedoch möglichst groß wählen. Aufgrund der geforderten Differenzierbarkeit der Übergänge muss das Zentrum des zweiten Kreissegments in einer Linie mit dem Endpunkt des ersten Segments und dessen Zentrum liegen. x_1 = x_0 - (r_1-r_0)*cos(phi_0), y_1 = (r_0-r_1)*sin(phi_0) Während des gesamten Vorgangs muss man immer daran denken, dass das Zentrum des letzten Segments analog zum ersten Segment auf der y-Achse liegen muss. Es gilt also x_{n-1} = 0, was widerum den letzten Radius r_{n-1} festlegt und damit wenig Spielraum für die maximale Abweichung des letzten Segments lässt, dies wirkt sich in der Regel auf phi_{n-2} so aus, das dieser Winkel klein genug gewählt werden muss, steht also der Minimierung Anzahl der Segmente direkt entgegen. Der Algorithmus wird dadurch recht kompliziert, der Trick ist immer wieder einen Winkel und Radius zu finden, sodass das ähnlich wie beim ersten Segment, das nächste Segement zunächst innerhalb einen maximalen Abstand und dann außerhalb einen maximalen Abstand ausbildet. Experimentiert man mit verschiednen Winkeln zwischen a und b sieht man das ganz gut. Um die Konstruktion genauer darzustellen fehlen mir momentan die Möglichkeiten, mit dem Normalenabstand sieht es aber momentan nicht schlecht aus. Schritt 3 wiederholt sich bis zum Abschluss. Für jedes neues Segment mit eventuellen Backtracking, weil keine gültige Lösung mehr für einen vorigen Ansatzpunkt gefunden werden kann. Schritt 1 [attach]58458[/attach] Schritt 2 [attach]58459[/attach] Schritt 3 [attach]58460[/attach] |
||||||||||||
| 11.05.2026, 09:00 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Ich denke auch, da für jeden Punkt der definierten Ellipse die Normalen-Richtung bekannt ist, oder umgekehrt für jeden konstruierten Kreis, hätte man damit das richtige Instrument zur Distanzmessung. Das war ja auch der Ausgangspunkt der Betrachtung. Für jedes Segment separat betrachtet sehe ich das Problem so: Es gibt einen festen Startpunkt A und einen noch offenen Zielpunkt B (beide auf der Ellipse). Zwischen AB gibt es dann die Mittelsenkrechte, auf der sich die Mittelpunkte der noch unbekannten Kreisradien befinden. Mit dem Variieren dieser Kreisradien findet man den Radius, bei der sich der kleinste Maximalabstand einstellt (Optimierungsschleife für Radius R). Dann vergleicht man diesen kleinsten Maximalabstand mit dem gewünschten Maximalabstand und entscheidet, wohin der Zielpunkt B wandern soll. Dann wiederholt sich die Optimierungsschleife für R so lange bis schließlich der Soll-Maximalabstand erreicht ist (=> Näherungsverfahren für den Punkt B erreicht). Das erste Segment ist abgeschlossen. Dann schließt sich das nächste Segment an, wobei der berechnete Punkt B zum neuen Startpunkt wird und der neue Punkt C berechnet wird, etc. Auf diese Weise ergeben sich dann die fortlaufenden Punkte auf dem Bogen der Ellipse mit den errechneten Radien. Aber das ist jetzt wieder zu sehr in meiner eigenen individuellen Welt der Lösungsfindung angesiedelt. Die Vorgehensweise ist ja nicht vorgeschrieben und bleibt letztendlich immer dem Programmierer überlassen. Prinzipiell bist du ja mit deiner Vorgehensweise schon im Zielkorridor. Wahrscheinlich geht es jetzt nur noch darum, den Algorithmus immer weiter anzupassen und mit den Ergebnissen zu experimentieren, damit am Ende (im Sinne der Aufgabenstellung) eine optimierte Lösung ausgegeben wird. Gruß Conny |
||||||||||||
| 11.05.2026, 21:27 | MitVorsprungLetzter | Auf diesen Beitrag antworten » | ||||||||||
RE: Abstand zwischen zwei Kurven
Mit dem Algorithmus bin ich bereits weit genug, um zu wissen, dass es problematisch ist die Übergänge auf der Ellipse zu fixieren. Oder zumindest damit nicht das beste Ergebnis gefunden wird. Da man eine minimale Anzahl an Segmente möchte, versucht man den Erlaubten Fehler maximal auszureizen. Dies wirkt wie eine Zange auf die maximalen Abstände einmal innerhalb einmal außerhalb der Ellipse. Dadurch sind meiner Meinung nach die Freiheitsgrade erschöpft und die Übergangspunkte werden nur bei bestimmten Ellipsen auf der Ellipse liegen. Beispielsweise sieht man das Problem wenn man eine Ellipse annimmt, die in 3 Segmente minimal gelöst wird. Man wende dann Schritt 2 sowohl von der großen Halbachse als auch der kleinen Halbachse aus an, damit sind 2 von 3 Segmente festgelegt. Fixiert man nun die Übergangspunkte beider Segmente auf der Ellipse, so muss der Schnittpunkt beider Normalen das Zentrum des mittleren verbleibenden Segments sein. Aber nur wenn der Abstand dieses Zentrums zu beiden Übergangspunkten gleich ist, kann ein Kreis von diesem Zentrum aus die ersten beiden Segmente verbinden. Ich will neben der Programmierung den Algorithmus auch mathematisch herleiten. Für eine allgemeine Distanzfunktion, wird das vermutlich nahezu unmöglich. Für eine spezielle Distanzfunktion, wie wir sie nun nutzen, fehlt mir die Motivation, außer dass es "gut zu funktionieren scheint". |
||||||||||||
| 12.05.2026, 13:15 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Bei einer Ellipse mit den Parametern a=5 , b=3 und mit einem definierten Maximalabstand von D=0.02 habe ich mal versucht, mit möglichst wenigen Segmenten auszukommen. Es ist mir nicht gelungen, die sehr kleine Lücke (Segment 3) zu schließen, womit die gesamte Ellipse in 8 Segmente unterteilt werden müsste anstatt mit 6. Zur Info: Die Punkte P_1 und P_2 liegen außerhalb der Ellipse mit dem Maximalabstand D=0.02. Vielleicht schafft ja dein Algorithmus, dass hier die Segmente-Anzahl doch noch geringer ausfällt? Immerhin kann ich nachempfinden, dass das schon eine sehr knifflige Angelegenheit ist. Viel Erfolg bei der Suche nach dem optimalen Algorithmus!!! Gruß Conny . |
||||||||||||
| 12.05.2026, 16:13 | Conny_1729 | Auf diesen Beitrag antworten » | ||||||||||
| RE: Abstand zwischen zwei Kurven Da ich anfangs ja schon mal die Offset-Kurven der Ellipse ins Spiel gebracht habe, so bietet sich mit dem positiven und negativen Offset auch eine Möglichkeit, die Kreiskurven zu ermitteln. Denn es liegen als Parameterkurven vor: Offset-Ellipse + : Offset-Ellipse - : Man sucht sich dann 2 Punkte auf der äußeren Kurve (+) und berechnet sich einen Radius, der dann die innere Kurve (-) tangiert. Damit hat man ein möglichst langes Bogenstück innerhalb der gesetzten Schranken. Gruß Conny . |
||||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
Verschoben!