Algoritmo per il rilevamento della sovrapposizione tra i vettori

Terminologia nitpick: quelli non sono vettori: i vettori hanno una direzione e una dimensione, ma non c'è un "punto di partenza" in uno spazio vettoriale. invece, stai definendo un segmento di linea tramite il punto iniziale e finale di questo segmento di linea.

Dati questi due punti A e B sulla linea, possiamo calcolare la direzione D = B - A della linea. Il segmento di linea a cui siamo interessati consiste di tutti i punti P che soddisfano la seguente equazione :

P = A + k·D,

dove k è un valore scalare in [0, 1] . Quando hai trasformato tutti i tuoi input in questo modulo, è abbastanza semplice trovare soluzioni in cui le linee si sovrappongono:

           P1 = P2
=> A1 + k1·D1 = A2 + k2·D2
=>         0 = (A2 - A1) + (-k1·D1 ) + k2·D2

Questo è essenzialmente un sistema di equazioni lineari , che può essere risolto se abbiamo due o più dimensioni. (Dobbiamo risolvere per le due variabili k1 e k2 ). Ci sono tre possibili risultati:

• non esistono soluzioni (ricorda anche il vincolo 0 <= k <= 1 ), cioè i segmenti di linea non si sovrappongono.
• esiste esattamente una soluzione, cioè le linee si toccano in un punto (ad esempio intersecando l'una con l'altra)
• c'è un numero infinito di soluzioni. Ciò significa che le linee sono parallele e si trovano l'una nell'altra per più di un punto.

Un altro algoritmo è descritto qui , che è basato su queste diapositive.

Dati segmenti di linea p1 - > q1 e p2 - > q2, i segmenti di linea si intersecano se:

1. Caso generale:

   • if (p1, q1, p2) e (p1, q1, q2) hanno orientamenti diversi e
   • (p2, q2, p1) e (p2, q2, q1) hanno orientamenti diversi

2. Caso speciale

   • if (p1, q1, p2), (p1, q1, q2), (p2, q2, p1) e (p2, q2, q1) sono tutti collineari e
   • le x-proiezioni di (p1, q1) e (p2, q2) si intersecano e
   • le proiezioni y di (p1, q1) e (p2, q2) si intersecano

dove "l'orientamento" può essere "in senso orario", "in senso antiorario" o "collineare".

Intuitivamente: se un segmento di linea non attraversa un altro segmento di linea, è interamente "su un lato" dell'altro segmento. Solo allora il tracciamento (p1, q1, p2) e (p1, q1, q2) o (p2, q2, p1) e (p2, q2, q1) risulterà nel tracciamento del triangolo nella stessa direzione.