Sprawdź, czy punkt rzucony na segment linii nie jest poza nim.

Question

Zobacz powyższy obrazek; w zasadzie chcę prosty test, aby sprawdzić, czy punkt znajduje się w zasięgu linii. Informacje (lub dane wejściowe, jeśli wolisz), które mam, to współrzędne punktu i współrzędne punktów zakończenia linii. Wyjście, które chcę, jest proste boolean. Jak mogę to sprawdzić w prosty sposób?

Answer 1

Można mieć prostą i jednolitą kontrolę w przypadku korzystania z produktu wewnętrzną. Wewnętrzny produkt między dwoma wektorami może być wizualizowany geometrycznie jako iloczyn długości dwóch wektorów czasu cosinusów kąta między nimi lub iloczynu długości jednego z wektorów i długości (ortogonalnego) rzutu drugiej linii na linii wyznaczonej przez ten wektor.

W twojej sytuacji, jeśli wektor v wyświetlasz z jednego z punktów końcowych segmentu do rozważanego punktu, punkt leży wewnątrz dozwolonego regionu wtedy i tylko wtedy, gdy projekcja spada na segment s łączący dwa punkty końcowe . I to jest równoważne

0 <= v·s <= s·s 

(ścisła nierówności jeśli chcesz wykluczyć linie prostopadłe do segmentu za pośrednictwem punktów końcowych)

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

Nie trudno jest określić równania prostopadłych linii przerywanych przechodzących przez punkty końcowe pogrubionej linii.

Niech pogrubiona linia zostanie zdefiniowana przez punkty (x1, y1) i (x2, y2). Wtedy to ma nachylenie

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

Więc wszystkie prostopadłe linie będą formy

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

Możemy używać, aby określić równania prostopadłych linii, które przechodzą przez (x1, y1) i (x2, y2) (odpowiednio) , które w zasadzie reprezentują granicę regionu, w którym muszą znajdować się wszystkie ważne punkty:

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

Tak, dla dowolnego punktu (x*, y*), aby ustalić, czy leży w ważnym regionie, można sprawdzić, czy

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

(lub na odwrót jeśli ya(x*) jest większa)

---

Poniższy powinno załatwić sprawę:

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

Możesz to zrobić, obliczając kąty.

Załóżmy, że Twoje punkty końcowe to (x1, y1) i (x2, y2), a twój punkt to (x, y).

Następnie należy utworzyć dwa wektory, z jednego punktu końcowego do drugiego i jednego punktu końcowego do punktu:

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

obliczyć iloczyn skalarny:

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

Teraz produkt kropka podzielona przez wielkość daje Ci cosinus kąta:

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

Teraz lewa jest tak, że jeśli kąt jest wielki er niż PI/2, jesteś „out”

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

wziąłem Daniel Fischer odpowiedź, która jest świetna, i dostosować go do 3D i jedność:

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