Come calcolare i punti di intersezione di una linea e una forma arbitraria?

Question

Esiste un modo per calcolare geometricamente i punti di intersezione di una linea e un percorso grafico arbitrario? So dove sono tutte le linee e le curve nel percorso, e sto usando l'elemento canvas HTML5 se questo è di aiuto. Fondamentalmente, ho accesso a tutti i comandi del disegno su tela e ai loro argomenti. Ad esempio, se l'API è stata chiamata con una lineTo, quindi un moveTo, quindi un arco ho tutte quelle informazioni. Ogni chiamata all'API è memorizzata in un array. Ho la definizione del percorso, voglio solo capire dove la linea interseca il percorso. Di seguito un'immagine che mostra un esempio dei punti che avrei bisogno di trovare.

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

Grazie per qualsiasi aiuto! Ancora una volta, preferirei farlo geometricamente piuttosto che basato sui pixel, se possibile.

Answer 1

Si potrebbe desiderare di avere uno sguardo a biblioteca geometria Javascript di Kevin Lindsey - Probabilmente contiene tutti gli algoritmi interesection che stai cercando: http://www.kevlindev.com/geometry/index.htm

Answer 2

Senza sapere come viene definito il percorso grafico, è impossibile rispondere alla domanda con un algoritmo concreto. C'è una soluzione in this book on algorithms per segmenti di linea retta.

Answer 3

Se si dispone delle equazioni per tutto, quindi è possibile farlo (in teoria). In pratica, non è così facile (soprattutto non nel caso generale). This discussion ha qualche buon consiglio su linee intersecanti e curve di bezier.

Answer 4

Si desidera intersecare una linea e una "spline" x (t), y (t) che dovrebbero essere al massimo polinomio di 4 ° grado per entrambi (x) e y (t). Hai risolto le equazioni, ma devi conoscere tutti i parametri. Se la soluzione non rientra in nessuno dei due intervalli (segmento di linea e segmento di spline hanno inizio e fine) - scartalo. q correlati:

The intersection point between a spline and a line