Thuật toán tìm phần giao và phần hợp của một số đối tượng trong hình học phẳng

Nguồn: [You must be registered and logged in to see this link.]
Các bài toán liên quan đến việc tìm phần giao và hợp của các đối tượng hình học phẳng như đa giác, đường tròn... thường là các bài toán khá hay và để tìm ra lời giải tối ưu thì đòi hỏi người lập trình phải có tư duy tốt về toán học. Đặc biệt, tìm giao hai đa giác là một trong những bài toán cơ sở của hình học tính toán và có nhiều ứng dụng trong các lĩnh vực khác nhau của đồ hoạ máy tính, CAD, GIS,...Chúng ta sẽ nghiên cứu một vài thuật toán qua các ví dụ dưới đây.

Bài toán 1.Trong mặt phẳng toạ độ cho trước toạ độ tâm và độ dài bán kính của hai đường tròn. Hãy tìm diện tích phần giao và diện tích phần hợp của chúng. Dữ liệu vào cho trong file CIRCLE.INP gồm hai dòng, mỗi dòng chứa 3 số theo thứ tự là hoành độ, tung độ và bán kính của đường tròn. Dữ liệu ra ghi vào file CIRCLE.OUT gồm hai dòng, dòng đầu tiên ghi một số thực là diện tích phần giao, dòng tiếp theo ghi diện tích phần hợp (các số thực được lấy chính xác đến hai chữ số thập phân). Ví dụ:

CIRCLE.INP

0 0 1

0 0 3

CIRCLE.OUT

3.12

28.30

Thuật toán tìm diện tích phần giao (hay còn gọi là phương pháp chia lưới): Chia mặt phẳng ra thành một lưới các ô vuông bởi các đường thẳng song song với các trục toạ độ. Kiểm tra từng ô vuông, nếu nó nằm trong cả hai đường tròn (thuộc phần giao của hai đường tròn) thì ta cộng thêm vào giá trị diện tích cần tìm một lượng bằng diện tích của ô vuông đó.

Một số lưu ý với phương pháp này:

- Phương pháp này có thể mở rộng để tìm diện tích phần giao và phần hợp của tập gồm nhiều đối tượng bất kỳ như đa giác, đường tròn, elíp...Điểm quan trọng là ta phải xác định được điều kiện để kiểm tra một ô vuông có thuộc miền trong của đối tượng không.

- Phương pháp này chỉ cho kết quả gần đúng. Kích thước các ô vuông của lưới càng nhỏ thì độ chính xác càng cao nhưng tốc độ thực hiện lại chậm đi.

- Cần có kỹ thuật duyệt để hạn chế số lượng hay khoanh vùng các ô vuông nhỏ cần kiểm tra. Chẳng hạn, với bài toán trên thì rõ ràng ta chỉ cần duyệt các ô vuông nằm trong một hình vuông ngoại tiếp một trong hai đường tròn.

Thuật toán tìm phần hợp của hai đường tròn rất đơn giản là ta chỉ việc lấy diện tích của tổng hai đường tròn rồi trừ đi phần diện tích giao nhau (hoặc cũng có thể thay vì kiểm tra điều kiện ô vuông phải nằm trong cả hai đường tròn thì ta chỉ cần kiểm tra nó có thuộc một đường tròn nào đó không).Để thực hiện thao tác chia mặt phẳng thành lưới ô vuông, ta dùng hai vòng lặp lồng nhau với hai biến điều khiển để duyệt trên các cạnh của lưới. Dưới đây là chương trình minh hoạ cho thuật toán tìm diện tích phần giao của hai dường tròn (để đơn giản, ta coi một ô vuông là thuộc đường tròn nếu đỉnh trên bên trái của nó thuộc đường tròn đó).

Code:



Program tinh_dien_tich_phan_giao_hai_duong_tron;var x1,y1,x2,y2,i,j,r1,r2,k,h,s:real7;function dist(x,y,u,v:real):real;

{distance between (x,y) and (u,v)}

begin

dist:=sqrt(sqr(x-u)+sqr(y-v));

end;

procedure init;

var f :text;

begin

assign(f,'circle.inp');

reset(f);

read(f,x1,y1,r1);

read(f,x2,y2,r2);

close(f);

s:=0

end;

procedure result;

var f :text;

begin

assign(f,'circle.out');

rewrite(f);

writeln(f,s:5:2);

writeln(f,pi*(r1*r1+r2*r2)-s:5:2);

close(f);

end;

procedure solve;

begin

init;

if dist(x1,y1,x2,y2)

i:=x1-r1;k:=x1+r1;

h:=y1+r1;

while i

begin

j:=y1-r1;

while j

begin

if dist(i,j,x1,y1)

if dist(i,j,x2,y2)

j:=j+0.05;

end;

i:=i+0.05;

end;

result;

end;

begin

solve;

end.


Chương trình trên có thể cải thiện tốc độ bằng cách kiểm tra các ô vuông nằm trong hình vuông ngoại tiếp đường tròn có bán kính bé hơn. Đến đây bạn đọc có thể giải được nhiều bài toán tương tự với các đối tượng hình học khác như giữa hai (hay nhiều) tam giác, giữa hai (hay nhiều) hình chữ nhật... hay hỗn hợp nhiều loại đối tượng với nhau, chẳng hạn tìm giao của đường tròn và tam giác...Tuy nhiên, với một số bài toán dạng này (bao gồm cả bài 1 ở trên) có thể giải bằng nhiều cách khác như các kỹ thuật xử lý ảnh hay chỉ thuần tuý đại số: tìm giao điểm của các đối tượng và dùng các công thức đại số để tính diện tích.
Bài toán 2. Hãy tìm phần giao của hai đa giác phẳng không tự cắt A và B (lồi hoặc lõm). Cho biết A=a1a2…anvà B=b1b2...bm, với ai và bjlần lượt là các đỉnh của đa giác A và B. Dữ liệu vào cho trong file DAGIAC.INP: dòng đầu tiên là một số nguyên n >3 là số cạnh của đa giác A, tiếp đó là n dòng, mỗi dòng theo thứ tự ghi hai số thực cách nhau một dấu cách là toạ độ của các đỉnh của đa giác; dòng tiếp theo là một số nguyên m >3 là số cạnh của đa B, tiếp đó là m dòng, mỗi dòng theo thứ tự ghi hai số thực cách nhau một dấu cách là toạ độ của các đỉnh của đa giác B. Dữ liệu ra ghi vào file DAGIAC.OUT gồm nhiều nhóm dòng. Nhóm thứ i mô tả về một đa giác là giao của A và B và có cấu trúc như sau: dòng đầu ghi một số nguyên dương k là số cạnh của đa giác, tiếp đó là một số thực là diện tích của đa giác, và k dòng tiếp theo mỗi dòng theo thứ tự ghi hai số là toạ độ đỉnh của đa giác thứ i. Nếu A và B không có giao điểm thì ghi một số 0.

DAGIAC.INP

4

0 1

5 1

5 3

0 3

8

1 0

4 0

4 1

3 1

3 22 22 11 1

DAGIAC.OUT

4

1.000

3.001.00

3.002.00

2.002.00

2.001.00

Phân tích đầu bài: Dễ thấy rằng bài toán này khó hơn bài trên vì ngoài việc phải tìm diện tích, ta còn phải chỉ ra đa giác tạo nên phần giao của A và B. Phần giao này có thể là tập rỗng hay là tập các đa giác không giao nhau. Để đơn giản ta gọi phần giao của A và B là tập đa giác giao, và gọi một cạnh là cạnh của tập đa giác giao với ý nghĩa nó là cạnh của một đa giác trong tập đa giác giao. Với P là một đa giác thì ta gọi I(P) và O(P) lần lượt là miền trong và miền ngoài của P.

Tư tưởng của thuật toán là tìm tất cả các cạnh của tập đa giác giao, nếu tập cạnh này khác rỗng thìbằng cách ghép chúng lại sẽ được tập các đa giác là giao của A và B.Thuật toán bao gồm hai bước chính như sau:
1.Trườnghợp hai đa giác không có cặp cạnh nào song song và giao nhau
Với mỗi cạnh v=aiai+1 ÎA (i=1,2,..,n), ta tìm mọi giao điểm của v với tất cả các cạnh u=bkbk+1ÎB (k=1,2,..,m), trong đó an+1 và bm+1 tương ứng được gán là a1 và b1.

Đặt Xv= {x| x là giao điểm của cạnh v với các cạnh u ÎB} È {ai,ai+1}(nếu trong Xv có nhiều điểm trùng nhau thì chỉ giữ lại một điểm trong số các điểm trùng nhau đó).

Sắp xếp các điểm trong Xv theo chiều tăng dần về khoảng cách từ mỗi điểm đến ai, ta được Xv ={x1=ai,x2,..,xlv-1,xlv=ai+1}, với |Xv|=lv. Khi đó, cạnh xixi+1(i=1,2,..,lv-1) là một cạnh của tập đa giác giao nếu trung điểm của nó thuộc I(B).

Xử lý tương tự cho các cạnh của đa giác B.

2.Xử lý trườnghợp hai đa giác có cặp cạnh song song và giao nhau

Trước hết, ta chèn thêm những điểm mới vào các đa giác để nếu có trường hợp tồn tại cặp cạnh song song và giao nhau thì tạo ra cặp cạnhtrùng nhau.

Giả sử cạnh aiai+1và cạnh bkbk+1 song song và giao nhau (nhưng không trùng nhau). Ta xử lý như sau:

-Nếu ai Îbkbk+1(ainằm trong đoạn bkbk+1), thì chèn ai vào giữa bkvà bk+1, tức là coi bkai và aibk+1là hai cạnh mới của đa giác B.

-Xử lý tương tự cho ba đỉnh: ai+1, bk và bk+1.

Sau đó, xét mỗi cặp cạnhtrùng nhau v=aiai+1ÎA và u=bkbk+1ÎB (giả sử aiºbkvà ai+1ºbk+1),thực hiện thao tác tìm giao điểm và sắp xếp như bước 1 ở trên với hai cạnh ai+1ai+2 và bk+1bk+2 ta được hai tập hợp:

Xv={x1=ai+1,x2,..,xlv-1,xlv=ai+2},

Yu={y1=bk+1,y2,..,ylu-1,ylu=bk+2}.

Để kiểm tra xem cạnh aiai+1 (hoặc bkbk+1) có là một cạnh của tập đa giác giao hay không, ta dựa vào tính chấtsau:

Gọi N và M lần lượt là trung điểm các cạnh x1x2 và y1y2. Khi đó, cạnh aiai+1(hoặc bkbk+1) là một cạnh của tập đa giác giao nếu một trong hai điều kiện sau thoả mãn:

1.N Î I(B) và M ÎO(A).

2.N Î O(B) và M Î I(A).

Tính chất trên có thể chứng minh dễ dàng thông qua hai kết quả sau:

1.Nếu đi theo chiều thuận (chiều ngược với chiều kim đồng hồ) theo các cạnh của đa giác P thì I(P) và O(P) tương ứng nằm về phía bên trái và phía bên phải dọc theo hướng đi .

2. Nếu biết trước một điểm MÎI(P) (O(P)), thì I(P) (O(P)) sẽ nằm cùng phía so với M và O(P) (I(P)) sẽ nằm khác phía so với M, theo một hướng đi trên một cạnh nào đó thuộc đa giác P.

Tóm tắt thuật toán:
-Xử lý hai đa giác theo như bước 2.

-Đánh dấu những cạnh trùng nhau (đã được xử lý).-Với các cạnh còn lại(chưa đánh dấu) thì thực hiện như bước 1.

- Ghép các cạnh tìm được để được các đa giác giao.

Chú ý:Trong thuật toán đã trình bày ở trên, để kiểm tra một điểm có nằm trong đa giác hay không ta có thể sử dụngthuật toán Jordan:

Cho trước điểm M(x,y) và một đa giác P, M không nằm trên cạnh của P. Xét nửa đường thẳng có gốc tại M, song song với trục tung Oy và hướng theo chiều dương. Tính tổng số giao điểm của nửa đường thẳng này với tất cả các cạnh của đa giác. Nếu số giao điểm này là lẻ thì M nằm trong đa giác, ngược lại thì kết luận M nằm ngoài đa giác. Ví dụ về hàm kiểm tra:

Code:



FUNCTION inside(x:xy;a:arr;n:byte):boolean;{kiểm tra điểm x có nằm trong đa giác a không }

varj,s,l,i,k:integer;

Begin

s:=0;

For i:=1 to n do

Begin

j:=i-1;k:=i+1;

{trường hợp không đi qua đỉnh}

if(x.xmin(a[i].x,a[k].x)) then

if x.y<=min(a[i].y,a[k].y) then s:=s+1

else {kiem tra gia tri cua ham tai x.x co nam duoi doan thang}

if x.y<=(x.x-a[i].x)*(a[k].y-a[i].y)/(a[k].x-a[i].x)+a[i].y then s:=s+1;

{trường hợp đi qua đỉnh}

If x.x=a[i].x then

Begin

if (x.x<>a[j].x)and(x.x<>a[k].x) then

if (x.xmax(a[j].x,a[k].x)) then

s:=s+2{x nằm về cùng một phía so với a[j]a[k]}

else if x.y<=(x.x-a[i].x)*(a[k].y-a[i].y)/(a[k].x-a[i].x)+a[i].y

then s:=s+1;

{trường hợp trùng cạnh a[i]a[k]}

if (x.x=a[k].x) then

if (x.xmax(a[j].x,a[k+1].x)) then

s:=s+2{x nam ve cung mot phia}

else if x.y<=(x.x-a[i+1].x)*(a[k+1].y-a[i+1].y)/(a[k+1].x-a[i+1].x)

+a[i+1].ythen s:=s+1;

End;

inside:=((s mod 2)=1);

End;


Đánh giá: Thuật toán ổn định, dễ cài đặt và có độ phức tạp khoảng O(N3) với N=Max(n,m). Trong trường hợp tổng quát, nếu đa giác có nhiều lỗ (hay còn gọi là các ring) lồng nhau nhiều cấp thì thuật toán vẫn thực hiện tốt với một chút sửa đổi trong chương trình. Đây không phải là một thuật toán thực sự tối ưu về tốc độ nhưng nó khá dễ tiếp cận trong việc cài đặt.

1%