Controllare se un punto proiettato su un segmento di linea non è fuori di essa

Question

vedere l'immagine qui 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?

Answer 1

È possibile avere un controllo semplice e uniforme se si utilizza 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 si proietta il vettore v da uno dei punti finali del segmento al punto in esame, il punto si trova all'interno della regione consentita se e solo se la proiezione cade sul segmento s che collega i due punti finali . E questo è equivalente a

0 <= v·s <= s·s 

(disuguaglianze severe se si desidera escludere le linee perpendicolari al segmento attraverso i punti finali)

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; 
} 

Answer 2

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

Lascia che la linea in grassetto sia definita dai punti (x1, y1) e (x2, y2). Quindi, si ha una pendenza

 
m = (y2 - y1)/(x2 - x1) 

Quindi, tutte le linee perpendicolari sarà di forma

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

Possiamo usarlo per determinare (rispettivamente) le equazioni delle linee perpendicolari che attraversano (x1, y1) e (x2, y2) , che in sostanza rappresentano il confine della regione in cui tutti i punti validi devono risiedere:

 
ya(x) = (-1/m)x + y1 + x1/m 
yb(x) = (-1/m)x + y2 + x2/m 

Così, per un punto arbitrario 012., per determinare se si trova nella regione valida, è possibile verificare se

 
ya(x*) <= y* <= yb(x*) 

(o viceversa se ya(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); 
} 

Answer 3

È possibile farlo calcolando gli angoli.

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

Poi si creano due vettori, da un estremo all'altro, e un endpoint al punto:

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

Calcolare il prodotto scalare:

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

Ora il prodotto scalare diviso per grandezza dà tu 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 è grande er quanto PI/2, si sono '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; 
} 

Answer 4

ho preso Daniel Fischer risposta che è grande, e regolato 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; 
}