Controlla se un punto proiettato su un segmento di linea non è al di fuori di esso

illustrazione

Vedere l’immagine sopra; in pratica, voglio un semplice test per verificare se un punto rientra nell’intervallo del segmento di linea. Le informazioni (o input, se preferisci) che ho sono le coordinate del punto e le coordinate dei punti di terminazione del segmento di linea. L’output che voglio è un semplice booleano. Come posso controllare questo in un modo semplice?

Puoi avere un controllo semplice e uniforms se usi il prodotto interno. Il prodotto interno tra due vettori può essere visualizzato geometricamente come il prodotto delle lunghezze dei due vettori tempo il coseno dell’angolo tra i due, o il prodotto della lunghezza di uno dei vettori e la lunghezza della proiezione (ortogonale) dell’altro sulla linea determinata da quel vettore.

Nella tua situazione, se proietti il ​​vettore v da uno dei punti finali del segmento al punto preso in considerazione, il punto si trova all’interno dell’area consentita se e solo se la proiezione cade sul segmento s collega i due punti finali. E questo è equivalente a

 0 <= v·s <= s·s 

(rigorose disuguaglianze se si desidera escludere le linee perpendicolari al segmento attraverso gli endpoint)

 public static boolean inRange(double start_x, double start_y, double end_x, double end_y, double point_x, double point_y) { double dx = end_x - start_x; double dy = end_y - start_y; double innerProduct = (point_x - start_x)*dx + (point_y - start_y)*dy; return 0 <= innerProduct && innerProduct <= dx*dx + dy*dy; } 

Non è difficile determinare le equazioni di quelle linee tratteggiate perpendicolari che passano attraverso i punti finali della tua linea in grassetto.

Lascia che la linea in grassetto sia definita dai punti (x 1 , y 1 ) e (x 2 , y 2 ) . Quindi, ha una pendenza

 m = (y 2 - y 1 ) / (x 2 - x 1 )

Quindi tutte le linee perpendicolari saranno della forma

 y (x) = ( -1 / m ) x + c

Possiamo usarlo per determinare le equazioni delle linee perpendicolari che passano (x 1 , y 1 ) e (x 2 , y 2 ) (rispettivamente), che rappresentano essenzialmente il limite della regione in cui devono risiedere tutti i punti validi:

 y a (x) = (-1 / m) x + y 1 + x 1 / m
 y b (x) = (-1 / m) x + y 2 + x 2 / m

Quindi, per un punto arbitrario (x*, y*) , per determinare se si trova nella regione valida, è ansible verificare se

 y a (x *) <= y * <= y b (x *)

(o il contrario se y a (x*) è più grande)


Il seguente dovrebbe fare il trucco:

 public static boolean check(double x1, double y1, double x2, double y2, double x, double y) { if (x1 == x2) { // special case return y1 < y2 ? (y1 <= y && y <= y2) : (y2 <= y && y <= y1); } double m = (y2 - y1) / (x2 - x1); double r1 = x1 + m * y1; double r2 = x2 + m * y2; double r = x + m * y; return r1 < r2 ? (r1 <= r && r <= r2) : (r2 <= r && r <= r1); } 

Puoi farlo calcolando gli angoli.

Supponiamo che i tuoi endpoint siano (x1, y1) e (x2, y2) e che il tuo punto sia (x, y).

Quindi crei due vettori, da un endpoint all’altro e un endpoint al tuo punto:

 vec1 = (x - x1, y - y1); vec2 = (x2 - x1, y2 - y1); 

Calcola il prodotto punto:

 double dotp = (x-x1) * (x2-x1) + (y-y1) * (y2 - y1); 

Ora il prodotto punto diviso per la grandezza ti dà il coseno dell’angolo:

 double theta = Math.acos((dtop) / (Math.sqrt((x-x1) * (x-x1) + (y-y1) * (y-y1)) * Math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)))); 

Ora il trucco è che se il tuo angolo è maggiore di PI / 2 , sei “fuori”

 public static boolean check(double x, double y, double x1, double y1, double x2, double y2) { // vectors are (dx1, dy1) and (dx2, dy2) double dx1 = x - x1, dx2 = x2 - x1, dy1 = y - y1, dy2 = y2 - y1; double dotp = dx1 * dx2 + dy1 * dy2; double theta = Math.acos(dotp / (Math.sqrt(dx1 * dx1 + dy1 * dy1) * Math.sqrt(dx2 * dx2 + dy2 * dy2))); theta = Math.abs(theta); if (theta > (Math.PI / 2)) return false; dx1 = x - x2; dx2 = x1 - x2; dy1 = y - y2; dy2 = y1 - y2; dotp = dx1 * dx2 + dy1 * dy2; theta = Math.acos(dotp / (Math.sqrt(dx1 * dx1 + dy1 * dy1) * Math.sqrt(dx2 * dx2 + dy2 * dy2))); theta = Math.abs(theta); if (theta > (Math.PI / 2)) return false; return true; } 

Ho preso la risposta di Daniel Fischer che è fantastica e l’ho adattata per 3D e Unity:

 public bool InSegmentRange(Vector3 start, Vector3 end, Vector3 point) { Vector3 delta = end - start; float innerProduct = (point.x - start.x) * delta.x + (point.y - start.y) * delta.y + (point.z - start.z) * delta.z; return innerProduct >= 0 && innerProduct <= delta.x * delta.x + delta.y * delta.y + delta.z * delta.z; }