Schnittpunkte von Kurven

30/06/2014 - 13:51 von Hans-Peter Diettrich | Report spam
Ich habe gerade (nicht nur einen) Knoten im Kopf: wie bestimmt man den
Schnittpunkt von zwei (kubischen) Splines?

Existenz und Eindeutigkeit des Schnittpunkts ist konstruktiv gegeben, es
geht um das Zerschneiden eines Rechtecks in Puzzle-Teile, mittels H*V
Splines (für Schnitte in horizontaler bzw. vertikaler Richtung). Die zu
ermittelnden Schnittstellen liegen typischerweise nicht auf Stützstellen
(Knoten) für die horizontalen und vertikalen Schnitte. Gesucht werden
also Paare (X,Y), so daß sowas gilt wie:
SplineX.f(x) = y
SplineY.f(y) = x
Dazu müßte jeweils zuerst das Intervall des Splines gefunden werden, in
dem der Schnittpunkt liegt, damit die richtigen f(x) und f(y) bekannt sind.

Wie geht das, und wie geht es dann weiter?

Als Anhaltspunkt ist die Position des Teils (h,v) im Raster bekannt, was
eine Suche auf das jeweils zugehörige Spline-Intervall und dessen
unmittelbare Nachbarn beschrànkt. Als erste Nàherung kann x=h und y=v
für die erste gesuchte Ecke des Teils angenommen werden.

Wem das zu einfach ist: Danach geht es weiter mit der Ermittlung eines
neuen Splines für jede Seite eines Teils, in den dann noch
Ein-/Ausstülpungen eingefügt werden sollen. Da machen mir die
Anschlußbedingungen für die benachbarten Teile Kopfzerbrechen, die durch
das Einschieben der Ein-/Ausstülpungen nicht geàndert werden dürfen.
Oder wàre auch dafür ein ganz anderer Ansatz einfacher zu behandeln?


Nachtrag:

Kann das konkrete Problem vereinfacht (eliminiert) werden, wenn man
zuerst die Ecken der Teile vorgibt, und die Knoten der Splines da
drauflegt? Die Frage wàre dann, welche Einschrànkungen bzgl. der
möglichen Formen der Teile sich daraus ergeben. Reale Puzzles werden ja
nicht unbedingt nach diesem Verfahren geschnitten, und ich möchte erst
einmal herausfinden, welche Verlàufe die Kanten eines Teils haben
können, die von dem noch zu entwickelnden Algorithmus ausgemessen und
für eine systematische Suche klassiert werden mössen.

DoDi
 

Lesen sie die antworten

#1 Ernst Sauer
01/07/2014 - 19:02 | Warnen spam
Am 30.06.2014 13:51, schrieb Hans-Peter Diettrich:
Ich habe gerade (nicht nur einen) Knoten im Kopf: wie bestimmt man den
Schnittpunkt von zwei (kubischen) Splines?




Wenn doch die Funktionen der Splines bekannt sind

y¡+b1*x+c1*x²+d1*x³
y¢+b2*x+c2*x²+d2*x³

dann bekommt man eine kubische Gleichung, die es zu lösen gilt:
(a2-a1)+(b2-b1)*x+(c2-c1)*x²+(d2-d1)*x³ = 0

Ist (x,y) bekannt,ist noch zu prüfen, ob der Punkt
innerhalb der Endpunkte beider Splines liegt.

Natürlich sollte man vorab prüfen welche Puzzle-Teile
überhaupt für Schnittpunkte in Frage kommen (Rechteckraster oder so).

E.S.

www.prostab.de
Meine Android-App: IngCalc

Ähnliche fragen