Tính đường biên giữa các đa giác không tự cắt

#1

Chào mọi người,
Mình có bài toàn như sau:

Cho n hình polygon có sẵn, (được định nghĩa bằng cái bảng n phần tử {x, y})
Vẽ 1 hình polygon “nằm sát” với các hình polygon đang có với các điểm mới được tính toán bởi các điểm trên đường biên giao giữa polygon mới này và các polygon đang có
Vd trong hình,
cho sẵn 2 polygon màu xanh lam và xanh lục
vẽ polygon thứ 3 màu cam, bằng cách chấm 5 điểm ABCDE
app sẽ tự tính và output polygon cam bằng A-p1…p9-DE

image
image718×450 22.5 KB

mình đã làm được phần “đổ màu” bằng cách XOR dữ liệu điểm trong polygon, nhưng khi tới phần output ra cái danh sách tọa độ điểm của polygon thì bí.

bạn nào có ý tưởng có thể chia sẻ với mình chút không?

#2

Phần Ap_1...p_9DE là nằm ngoài 2 polygon màu xanh lam và xanh lục phải không nhỉ? Tức là chỉ tính những phần nằm trong polygon cuối cùng mà không nằm trong các polygon còn lại?

6 Likes
#3

C++ có thư viện Boost.Geometry hàm difference tính polygon1 - polygon2 :V https://www.boost.org/doc/libs/1_74_0/libs/geometry/doc/html/geometry/reference/algorithms/difference/difference_3.html

5 Likes
#4

đúng rồi bạn, mình đang tìm cách tính toán cái đường polygon này

1 Like
#5

hehe, mình thì đang làm bằng C#, cũng có tìm thấy thuật toán Weiler-Atherton với lại thư viện mà chạy chưa đúng, đang nghiên cứu cách sửa

3 Likes
#6

Gọi polygon vẽ cuối cùng (như trong ví dụ của bạn là ABCDE) là P_a, tập các polygon còn lại là polygons.

Toạ độ của các điểm p_i chắc chắn là nằm trên các cạnh của n Polygon hoặc chính là điểm của 1 trong n Polygon đó. Bạn thử lấy 1 danh sách các điểm “khả nghi”, gọi là interpoint. Định nghĩa:

interpoint = \{v\ |\ v \in vertices(P)\ \forall P \in (polygons \ \cap \{P_a\})\}\ \cup \\ \bigcup _{P\ \in\ polygons} \bigcup _{e_a\ \in\ P_a} \bigcup _{e\ \in\ P} (e_a\ \cap\ e)

Chọn 1 đỉnh của P_a nằm ngoài polygons, gọi là đỉnh A, “quét” các điểm:

result_polygon = {}

for p in interpoint:
    if p ∈ A and đoạn thẳng A-p nằm trong miền P_a:
        # ghi nhận p là 1 điểm của đa giác cần tìm
        result_polygon.add(p)

Sắp xếp các đỉnh trong result_polygon theo chiều CW/CCW. Ta có đa giác cần tìm.

8 Likes
#7

hehe báo lại vào đây để sau này ai có tìm,
về cơ bản thì thuật toán và thư viện này sẽ giải quyết được vấn đề, quan trọng là sau khi debug sml 1 tuần (bao gồm 2 ngày cuối tuần) thì khách hàng bảo “để đấy tao làm cho” nên mình không có output cuối cùng của nó :smile: giờ thì bị dí sang module khác :smile:

3 Likes
#8

Tức là bạn được cung cấp tất cả các điểm rồi giờ highlight đường p1-p9?

#9 
// input: 
{A;B;C;D;E}
{P2;P3;P4;P5;BLUE-1,BLUE-2;BLUE-3;BLUE-4;BLUE-5;BLUE-6;BLUE-7} // 7 điểm còn lại của hình blue, không có P1, 
{p5;p6;p7;p8;green-1;green-2;green-3} // 3 điểm còn lại của hình green, không có p9 
// output 
{p1; p2; p3; p4; p5; p6; p7; p8; p9}
#10

BSP

Gọi 3 hình là X, Y, Z
R = (X - Y) - Z;
Lấy mọi điểm v thuộc R sao cho v nằm trong (thuộc vùng +) hoặc trên biên của X sao v không phải là đỉnh X.

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?