Wie berechnet man die Schnittpunkte einer Linie und einer beliebigen Form?

Question

Gibt es eine Möglichkeit, die Schnittpunkte einer Linie und eines beliebigen Grafikpfades geometrisch zu berechnen? Ich weiß, wo alle Linien und Kurven in dem Pfad sind, und ich verwende das HTML5-Canvas-Element, wenn das hilft. Grundsätzlich habe ich Zugriff auf alle Zeichenbefehle und ihre Argumente. Zum Beispiel, wenn die API mit einem lineTo, dann einem moveTo, dann einem Bogen aufgerufen wurde, habe ich alle diese Informationen. Jeder Aufruf der API wird in einem Array gespeichert. Ich habe die Pfaddefinition, ich möchte nur herausfinden, wo die Linie den Pfad schneidet. Unten ist ein Bild, das ein Beispiel der Punkte zeigt, die ich finden müsste.

alt text http://cl.ly/3228b0e7ea32b172e960/content

Vielen Dank für jede Hilfe! Auch dies würde ich lieber geometrisch als pixelbasiert machen.

Answer 1

Sie vielleicht einen Blick auf Kevin Lindsey Javascript Geometrie Bibliothek haben wollen - es enthält wahrscheinlich alle interesection Algorithmen Sie suchen: http://www.kevlindev.com/geometry/index.htm

Answer 2

Ohne zu wissen, wie Ihr Grafikpfad definiert ist, ist es unmöglich, Ihre Frage mit einem konkreten Algorithmus zu beantworten. Es gibt eine Lösung in this book on algorithms für gerade Liniensegmente.

Answer 3

Wenn Sie die Gleichungen für alles haben, dann können Sie es (in der Theorie) tun. In der Praxis ist es nicht so einfach (besonders nicht im allgemeinen Fall). This discussion hat einige gute Ratschläge zu sich kreuzenden Linien und Bezierkurven.

Answer 4

Sie möchten eine Linie und einen "Spline" x (t), y (t) schneiden, der sowohl für x (t) als auch für y (t) das Polynom vierten Grades sein sollte. Sie haben Gleichungen gelöst, aber Sie müssen alle Parameter kennen. Wenn die Lösung außerhalb eines Bereichs liegt (Liniensegment und Spline-Segment haben Anfang und Ende), verwerfen Sie sie. Verwandte q:

The intersection point between a spline and a line