Tôi đang cố gắng tìm một hình chữ nhật có giao nhau với đa giác lõm hay không. Thuật toán này có thực hiện được điều đó không?

Question

Tôi đang cố gắng tìm xem một hình chữ nhật có giao nhau với đa giác lõm hay không. Tôi tìm thấy thuật toán này:

double determinant(Vector2D vec1, Vector2D vec2){ 
    return vec1.x*vec2.y-vec1.y*vec2.x; 
} 

//one edge is a-b, the other is c-d 
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){ 
    double det=determinant(b-a,c-d); 
    double t=determinant(c-a,c-d)/det; 
    double u=determinant(b-a,c-a)/det; 
    if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION; 
    return a*(1-t)+t*b; 
} 

Nếu tôi thực hiện điều này 4 lần (Top Right, Trên xuống dưới bên trái, trên xuống dưới bên phải, phía dưới bên phải) * (tất cả các cạnh của đa giác của tôi) sẽ này một cách hiệu quả và chính xác cho tôi biết nếu hình chữ nhật có một phần hoặc toàn bộ đa giác lõm bên trong? Nếu không phải những gì sẽ bị thiếu?

Cảm ơn

Answer 1

Mã cố gắng tìm điểm giao nhau của hai đoạn - AB và CD.

Có nhiều cách khác nhau để giải thích cách hoạt động của nó, tùy thuộc vào cách bạn giải thích các hoạt động này.

Giả sử điểm A có tọa độ (xa, ya), B - (xb, yb) v.v. Hãy nói rằng

dxAB = xb - xa 
dyAB = yb - ya 
dxCD = xd - xc 
dyCD = yd - yc 

Các hệ thống sau đây của hai phương trình tuyến tính

| dxAB dxCD | | t | | xc-xa | 
|   | * | | = |  | 
| dyAB dyCD | | u | | yc-ya | 

nếu giải quyết cho t và u, sẽ cung cấp cho bạn các vị trí tương ứng của điểm giao nhau trên đường dây AB (giá trị t) và trên dòng CD (giá trị u). Các giá trị này sẽ nằm trong phạm vi [0, 1] nếu điểm thuộc về phân đoạn tương ứng và nằm ngoài phạm vi đó nếu điểm nằm ngoài phân đoạn (trên dòng chứa phân đoạn).

Để giải quyết hệ phương trình tuyến tính này, chúng tôi có thể sử dụng Cramer's rule nổi tiếng. Cho rằng chúng ta sẽ cần những yếu tố quyết định của

| dxAB dxCD | 
|   | 
| dyAB dyCD | 

đó là chính xác determinant(b - a, c - d) từ mã của bạn. (Trên thực tế, những gì tôi có ở đây là determinant(b - a, d - c), nhưng nó không thực sự quan trọng cho các mục đích của giải thích này. Mã bạn đăng vì một lý do hoán đổi C và D, xem P.S. lưu ý bên dưới).

Và chúng tôi cũng sẽ cần phải yếu tố quyết định của

| xc-xa dxCD | 
|   | 
| yc-ya dyCD | 

đó là chính xác determinant(c-a,c-d) từ mã của bạn, và yếu tố quyết định của

| dxAB xc-xa | 
|   | 
| dyAB yc-ya | 

đó là chính xác determinant(b-a,c-a).

Chia các yếu tố quyết định này theo quy tắc của Cramer sẽ cung cấp cho chúng tôi các giá trị t và u, chính xác là những gì được thực hiện trong mã bạn đã đăng.

Mã này sau đó tiến hành kiểm tra các giá trị của t và u để kiểm tra xem các phân đoạn thực sự giao nhau, ví dụ: cho dù cả hai t và u thuộc về [0, 1] phạm vi. Và nếu có, tính toán điểm giao nhau thực tế bằng cách đánh giá a*t+b*(1-t) (tương đương, nó có thể đánh giá c*u+d*(1-u)). (Một lần nữa, xem lưu ý P.S. dưới đây).

P.S. Trong mã ban đầu, các điểm D và C được "đổi chỗ" theo nghĩa là mã số c - d, nơi tôi làm d - c trong phần giải thích của tôi. Nhưng điều này làm cho không có sự khác biệt cho ý tưởng chung của thuật toán, miễn là một người cẩn thận với các dấu hiệu.

Sự hoán đổi điểm C và D này cũng là lý do cho biểu thức a*(1-t)+t*b được sử dụng khi đánh giá điểm giao nhau. Thông thường, như trong lời giải thích của tôi, người ta mong muốn thấy một cái gì đó như a*t+b*(1-t) ở đó. (Tôi có nghi ngờ của tôi về điều này mặc dù. Tôi mong đợi để xem a*t+b*(1-t) có ngay cả trong phiên bản của bạn. Có thể là một lỗi.)

P.P.S. Tác giả nếu mã đã quên kiểm tra det == 0 (hoặc rất gần 0), điều này sẽ xảy ra trong trường hợp các phân đoạn song song.

Answer 2

Tôi nghĩ rằng những điều sau đây nên làm việc:

(1) for each e1 in rectangle_edges, e2 in polygon_edges 
    (1.1) if edgeIntersection(e1,e2) != NO_INTERSECTION 
     (1.1.1) return true 
(2) if (max_polygon_x < max_rectangle_x) and (min_polygon_x > min_rectangle_x) and (max_polygon_y < max_rectangle_y) and (min_polygon_y > min_rectangle_y) 
    (2.1) return true 
(2) return false 

Sửa: Thêm kiểm tra cho dù đa giác là bên trong hình chữ nhật.

Answer 3

Theo như tôi có thể nói sau một nháy mắt, nó cố gắng xác định xem 2 đoạn đường có cắt nhau hay không, và nếu có, tọa độ của điểm giao nhau là gì.

Không, nó không đủ tốt để xác định xem hình chữ nhật và đa giác của bạn có giao nhau không, bởi vì bạn vẫn bỏ lỡ trường hợp đa giác nằm hoàn toàn bên trong hình chữ nhật hoặc ngược lại.