Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Schnittpunkt auf Bezierkurve
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Schnittpunkt auf Bezierkurve
 
Autor Nachricht
sHo
Gast






BeitragVerfasst am: 11 Apr 2005 - 23:49:30    Titel: Schnittpunkt auf Bezierkurve

Ist es möglich den Schnittpunkt einer kubischen bzw. quadratischen
Bezierkurve zu berechnen? Wenn ja - wie? Wink Ich hab schon das Netz
durchstöbert aber nichts brauchbares gefunden. Ich bräuchte es für ein
Computerprogramm - möcht aber außschließen, dass es eine einfachere
und resourcensparendere Variante als das Berechnen der einzelnen Linien
zwischen den berechneten Bezier-Punkten. Vielleicht eine Formel oder eine
andere Variante ?! Allerherzlichsten Dank!
DMoshage
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 31.03.2005
Beiträge: 691

BeitragVerfasst am: 12 Apr 2005 - 08:34:03    Titel:

Hallo sHo,

ich glaube ich kann dir da wenig Hoffnung machen. Es wird wohl auf ein Iterationsverfahren hinauslaufen. Vielleicht hat algebrafreak mithilfe einer Approximation der Bezierkurve einen geschickten Ansatz.

In folgendem Dokument wird unter anderem auf die Berechnung eines Schnittpunktes von Bezierkurven aingegangen.
http://www.uni-weimar.de/~bauinf/Publikationen/SA/SABock.pdf

Gruß
Dirk
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 12 Apr 2005 - 12:23:32    Titel:

Ich kann obige Datei nicht öffnen. Vermutlich liegt es an einer fortschrittlichen PDF-Formatierung. Ich benutze nur GhostScript zum Anzeigen von PDF's.

Zum Thema. Eine Bezierkurve B(u) : [0,1] -> R^n ist ja eine vektorwertige Polynomenfunktion. Bei der kubischen sind die Polynome vom Grad 3 und bei der Quadratischen vom Grad 2. Die Suche nach Schnittpunkten ist, wie auch immer, die Bildung der Differenz der Termvektoren und das Gleichsetzen davon mit 0. Rauskommen tut ein univariates System von Polynomgleichungen vom höchstens Grad 3. Die Lösungsmenge ist die Schnittmenge der Lösungen einzelner Gleichungen. Z.B.

Das System

0 = u^2
0 = u^3-2*u-3*u
0 = u

hat eine einzige gemeinsame Nullstelle 0. Die einzelnen Nullstellen sind einfach mit Cardanschen Formeln berechenbar. Die Schnittmengenberechnung ist ein Algorithmus, der in O(1) läuft, denn
Du kannst die Laufzeit durch eine Konstante abschätzen (natürlich wenn Du nicht vorhast die Dimension deiner Bezierkurve zur Laufzeit zu ändern Smile ):

Code:

l ist eine Liste von paaren.
setze l = {(-ninf,+pinf)}

while(noch gleichungen da) {

   löse die nächste Gleichung. Ergebnis ist von einer der Form:
   a) leer : Brich ab mit Ausgabe leer
   b) {a} : Suche in l nach a. Wenn a in (c,d) füge (c,a) und (a,d) statt (c,d) in l ein.
   c) {a,b} : Analog zu b) für a und b
   d) {a,b,c} : Analog zu b) für a,b und c
   e) R : mache nichts

}


Den Code für Cardansche Formeln findest Du hier

http://www.uni-protokolle.de/foren/viewtopic.php?t=17503&start=30

Alles läuft in konstanter Zeit !!!

Falls ich mich ein wenig unverständlich ausgedrückt habe, so kannst Du gerna nachhacken.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Schnittpunkt auf Bezierkurve
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum