Kiểm tra xem điểm được chiếu trên đoạn đường không nằm ngoài nó

Question

Xem hình ảnh ở trên; về cơ bản, tôi muốn một thử nghiệm đơn giản để kiểm tra xem một điểm có nằm trong phạm vi của đoạn đường hay không. Thông tin (hoặc đầu vào, nếu bạn thích) Tôi có là tọa độ của điểm, và tọa độ điểm kết thúc của đoạn đường. Đầu ra tôi muốn là một boolean đơn giản. Làm thế nào tôi có thể kiểm tra điều này một cách đơn giản?

Answer 1

Bạn có thể kiểm tra đơn giản và đồng nhất nếu bạn sử dụng sản phẩm bên trong. Sản phẩm bên trong giữa hai vectơ có thể được hình dung trực quan như sản phẩm của độ dài của hai vectơ thời gian cosin của góc giữa hai vectơ, hoặc sản phẩm có độ dài của một trong các vec-tơ và chiều dài của phép chiếu trực giao (trực giao) của người khác vào dòng được xác định bởi vectơ đó.

Trong trường hợp của bạn, nếu bạn chiếu vector v từ một trong các điểm cuối của đoạn đó đến điểm được xem xét, điểm nằm trong vùng được phép nếu và chỉ khi chiếu rơi trên đoạn s kết nối hai điểm cuối . Và đó là tương đương với

0 <= v·s <= s·s 

(bất bình đẳng nghiêm ngặt nếu bạn muốn loại trừ các đường vuông góc với phân khúc này thông qua các thiết bị đầu cuối)

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

Thật khó để xác định phương trình của các đường chấm chấm vuông góc đó đi qua các điểm cuối của đường in đậm của bạn.

Để dòng in đậm được xác định theo các điểm (x1, y1) và (x2, y2). Sau đó, nó có một độ dốc

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

Vì vậy, tất cả các dòng vuông góc sẽ có dạng

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

Chúng ta có thể sử dụng để xác định các phương trình của các đường vuông góc đi qua (x1, y1) và (x2, y2) (tương ứng) , về cơ bản đại diện cho ranh giới của khu vực mà tất cả các điểm hợp lệ phải cư trú:

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

Vì vậy, cho một điểm tùy ý (x*, y*), để xác định xem nó nằm trong khu vực có giá trị, bạn có thể kiểm tra xem

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

(hoặc ngược lại nếu ya(x*) lớn)

---

Sau đây nên làm như lừa:

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

Bạn có thể làm điều này bằng cách tính toán các góc.

Giả sử điểm cuối của bạn là (x1, y1) và (x2, y2) và điểm của bạn là (x, y).

Sau đó, bạn tạo hai vectơ, từ một thiết bị đầu cuối để khác, và một thiết bị đầu cuối để quan điểm của bạn:

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

Tính chấm sản phẩm:

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

Bây giờ chấm sản phẩm chia cho cường độ cho phép bạn cosin của góc:

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

Bây giờ, mẹo là nếu góc của bạn là tuyệt vời er hơn PI/2, bạn đang 'ra'

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

tôi mất Daniel Fischer câu trả lời đó là rất tốt, và điều chỉnh nó cho 3D và 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; 
}