Phương pháp thiết kế thuật toán giải quyết một số bài toán trong hình học

1. Các khái niệm cơ bản 1.1. Điểm Điểm là một đối tượng hình học cơ sở. Trong không gian hai chiều với hệ trục toạ độ Descart người ta biểu diễn điểm là bởi một cặp số thực (x, y). Để đơn giản trong việc biểu diễn và tính toán trên máy tính chúng ta sử dụng cặp toạ độ số nguyên để biểu diễn cho một điểm. Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của điểm như sau: TYPE POINT = Record x, y : Integer; END; VAR p : POINT; 1.2. Đoạn thẳng và các tính chất của đoạn thẳng Đoạn thẳng là một phần của đường thẳng đi qua hai điểm P1, P2 và được giới hạn bởi hai điểm phân biệt P1 và P2. Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của đoạn thẳng như sau: TYPE LINE = Record P1, P2 : POINT; END; VAR l : LINE; Cho hai điểm phân biệt P1 = (x1, y1) và P2 = (x2, y2), tổ hợp lồi của hai điểm P1 và P2 là bất kỳ điểm P3 (x3, y3) sao cho với a mà 0 £ a £ 1, ta có x3 = ax1 + (1 - a)x2 và y3 = ay1 + (1 - a)y2. Ta có thể viết gọn lại như sau: P3 = aP1 + (1 - a)P2. Theo trực giác thì P3 nằm trên đoạn thằng P1 và P2, hai điểm P1 và P2 được gọi là các điểm cuối của đoạn thẳng P1P2. Nếu ta quan tâm đến thứ tự sắp xếp của P1 và P2 thì ta nói về đoạn thẳng có hướng , Nếu P1 là gốc (0, 0) thì ta có thể xem đoạn thẳng có hướng như vectơ . 1.3. Đa giác Đa giác là một danh sách các điểm, với hai điểm cạnh nhau được nối bởi một đoạn thẳng và điểm đầu và điểm cuối trùng nhau. Đa giác bao giờ cũng là một đường khép kín. Thông thường chúng ta sử dụng mảng các điểm để biểu diễn một đa giác, trong một số trường hợp chúng ta có thể sử dụng danh sách liên kết. Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của đa giác như sau: VAR polygon : Array[0..100] of POINT; 1.4. Xác định chiều quay của các vectơ Tích các vectơ là một trong những phép tính cơ bản và trọng tâm của các phương pháp đoạn thẳng. Xét vectơ và như trong hình 1.1. Tích vectơ ´ là một vectơ vuông góc với hai vectơ , và có độ lớn là |x1y2 – x2y1|. Độ lớn này chính là diện tích (biểu diễn ở vùng màu sẫm) của hình bình hành được giới hạn bởi các điểm (0, 0), P1(x1, y1), P2(x2, y2), P1 + P2 (x1 + x2, y1 + y2). Sau đây chúng ta sẽ xét một đại lượng được trích rút ra từ khái niệm tích vectơ để xác định tính chất quay theo chiều kim đồng hồ hay ngược chiều kim đồng hồ của vec tơ này đối với vectơ kia. Hình 1.1. Độ lớn của tích hai vectơ và là phần hình bình hành tô sẫm Nếu C(´) là dương thì ta nói theo chiều kim đồng hồ từ đối với gốc toạ độ (0, 0); nếu C(´) âm, thì ta nói ngược chiều kim đồng hồ từ đối với gốc toạ độ (0, 0). Nếu C(´) là 0 thì các vectơ cộng tuyến với nhau. Hình 1.2 nêu lên vùng cùng chiều kim đồng hồ và vùng ngược chiều kim đồng hồ đối với vectơ . Hình 1.2. Vùng tô bóng tối chứa các vectơ ngược chiều kim đồng hồ từ , vùng tô bóng sáng chứa các vectơ cùng chiều kim đồng hồ . Sau đây là đoạn chương trình minh hoạ, giá trị trả về của nó là 1 nếu theo chiều kim đồng hồ từ đối với gốc toạ độ (0, 0); -1 nếu ngược chiều kim đồng hồ từ đối với gốc toạ độ (0, 0); 0 nếu hai vectơ và cộng tuyến với nhau. FUNCTION ccw0(P1, P2 : Point) : Integer; Var A1, A2 : Integer; Begin A1:=P1.x*P2.y; A2:=P2.x*P1.y; If A1-A2>0 Then ccw:=1 Else If A1-A2<0 Then ccw:=-1 Else ccw:=0; End; Để xác định một đoạn thẳng có hướng có theo chiều kim đồng hồ từ một đoạn thẳng có hướng đối với điểm đầu chung P0 của chúng hay không chúng ta làm cách như sau: Tịnh tiến vectơ và về gốc toạ độ, nghĩa là cho - thể hiện bởi vectơ = , trong đó và . Tương tự cho - thể hiện bởi vectơ = , trong đó và . Lúc này ta tính toán C(´) = = . Nếu C(´) là dương, thì theo chiều kim đồng hồ từ , ngược lại nếu C(´) âm, thì ngược chiều kim đồng hồ từ . Nếu C(´) bằng 0 thì hai vectơ cộng tuyến. FUNCTION ccw(P0, P1, P2 : Point) : Integer; Var A1, A2, dx1, dx2, dy1, dy2 : Integer; Begin dx1:=P1.x - P0.x; dx2:=P2.x - P0.x; dy1:=P1.y - P0.y; dy2:=P2.y - P0.y; A1:=dx1*dy2; A2:=dx2*dy1; If A1-A2>0 Then ccw:=1 Else If A1-A2<0 Then ccw:=-1 Else ccw:=0; End; Trên đây là đoạn chương trình minh hoạ xem một đoạn thẳng có hướng có theo chiều kim đồng hồ từ đoạn thẳng có hướng đối với điểm đầu chung P0 của chúng hay không. Giá trị trả về là 1 nếu cùng chiều kim đồng hồ từ đối với P0; -1 nếu ngược chiều kim đồng hồ từ đối với P0; 0 nếu cộng tuyến với . 1.5. Xác định hai đoạn thẳng liên tiếp quay trái hay quay phải Ta xét hai đoạn thẳng liên tiếp và quay ngược chiều kim đồng hồ hay cùng chiều kim đồng tại điểm . Tương tự ta có thể xác định một góc đã cho sẽ quay theo chiều kim đồng hồ hay ngược chiều kim đồng hồ mà không cần phải tính toán góc. Phương pháp làm ở đây là ta kiểm tra đoạn thẳng có hướng có theo chiều kim đồng hồ hay ngược chiều kim đồng hồ so với đoạn thẳng có hướng . Theo trên, ta có, thể hiện cho vectơ - và thể hiện cho vectơ - . Tính C(´), nếu dấu của đại lượng này là âm, thì ngược chiều kim đồng hồ đối với , và như vậy hai đoạn thẳng có hướng và quay ngược chiều kim đồng hồ tại điểm . Nếu đại lượng C(´) là dương thì và quay cùng chiều kim đồng hồ tại điểm . Nếu đại lượng C(´) bằng 0 thì hai đoạn thẳng có hướng và cộng tuyến. Ngược chiều kim đồng hồ Cùng chiều kim đồng hồ Hình 1.3. Dùng đại lượng C(, ) để xác định chiều quay của các đoạn thẳng có hướng liên tiếp và 1.6. Xác định hai đoạn thẳng giao nhau Để kiểm tra hai đoạn thẳng và có giao nhau hay không ta tiến hành qua hai giai đoạn. Giai đoạn thứ nhất là phép loại nhanh các đoạn thẳng không thể giao nhau - đó là trường hợp hai hình chữ nhật định cận không giao nhau. Hình chữ nhật định cận của một hình là hình chữ nhật nhỏ nhất chứa hình đó và có các cạnh song song với hai trục toạ độ. Với đoạn thẳng thì hình chữ nhật định cận là hình chữ nhật được biểu diễn thông qua hai điểm và , trong đó , , , . Hai hình chữ nhật định cận của và là (, ) và (, ) giao nhau nếu và chỉ nếu phép hội là đúng. Các hình chữ nhật phải giao nhau theo cả hai chiều; chiều của trục x (thể hiện ở hai phép so sánh đầu tiên) và chiều của trục y (thể hiện ở hai phép so sánh cuối cùng). Giai đoạn thứ hai để xác định hai đoạn thẳng có giao nhau hay không khi biết các hình chữ nhật định cận đã giao nhau. Để biết được điều này, chúng ta xét xem mỗi đoạn thẳng có nằm trên đường thẳng chứa đoạn thẳng kia hay không. Nếu thoả mãn điều kiện trên thì ta kết luận hai đoạn thẳng giao nhau. a)P4 P3 P2 P1 b)P2 P3 P4 P1 c)P2 P3 P4 P1 d) P2 P1 P3 P4 Hình 1.4. Xác định xem đoạn thẳng nằm trên đường thẳng chứa đoạn thẳng . (a) Nếu nó nằm trên, thì các dấu của các và khác nhau; (b) Nếu nó không nằm trên, thì các dấu của hai đại lượng trên là giống nhau; (c)-(d) Tồn tại một đại lượng bằng 0 nếu có ít nhất một cận của nằm trên đường thẳng kia. Ta có thể dùng phương pháp tích vectơ để xác định đoạn thẳng có nằm trên đường thẳng chứa đoạn thẳng hay không. Như đã nêu trong hình 1.4. (a) và (b), ta xét xem các đoạn thẳng có hướng và có hướng trái ngược nhau tương đối với hay không. Tức là, dấu của đại lượng và có khác nhau hay không. Nếu có, thì đoạn thẳng nằm trên đường thẳng, ngược lại thì đoạn thẳng không nằm trên đường thẳng. Trong trường hợp hoặc nằm trên đường thẳng chứa đoạn thẳng thì sẽ có một đại lượng hoặc bằng 0. Ta gọi đây là trường hợp cận như đã thấy trong hình 1.4. (c) và (d). Độ dài một đoạn thẳng bằng 0 khi và chỉ khi bằng 0. Sau đây là đoạn chương trình minh hoạ hai đoạn thẳng có giao nhau hay không. Giá trị trả về là 1 nếu hai đoạn thẳng giao nhau; 0 nếu hai đoạn thẳng không giao nhau. FUNCTION Intersect(L1,L2 : Line) : Boolean; Var x1, x2, x3, x4, y1, y2, y3, y4 : Integer; Begin x1:=Min(L1.P1.x,L1.P2.x); y1:=Min(L1.P1.y,L1.P2.y); x2:=Max(L1.P1.x,L1.P2.x); y2:=Max(L1.P1.y,L1.P2.y); x3:=Min(L2.P1.x,L2.P2.x); y3:=Min(L2.P1.y,L2.P2.y); x4:=Min(L2.P1.x,L2.P2.x); y4:=Min(L2.P1.y,L2.P2.y); If (x2>x3) and (x4>x1) and (y2>y3) and (y4>y1) Then If (ccw(l1.p1,l2.p2,l1.p2)*ccw(l1.p1,l2.p1,l1.p2)<=0) and (ccw(l2.p1,l1.p2,l2.p2)*ccw(l2.p1,l1.p1,l2.p2)<=0) Then Intersect:=True Else Intersect:=False Else Intersect:=False; End; 2. Các thuật toán cơ bản 2.1. Đường khép kín đơn Bài toán: Cho một tập N điểm xác định trên mặt phẳng, các điểm đôi một không trùng nhau. Yêu cầu: Tìm một đường đi (là các đoạn thẳng nối các điểm đã cho lại với nhau) qua tất cả các điểm rồi quay trở về điểm ban đầu sao cho chúng không cắt nhau. Đường đi như trên được gọi là đường khép kín đơn. Bài toán tìm đường đi khép kín đơn được ứng dụng trong nhiều lĩnh vực như tìm đường đi cho người đưa thư đi đến mỗi nhà mà không đi qua những đường đã đi, hay bài toán về cách vẽ các điểm bằng plotter sao cho hợp lý, ... a)A M I K G F E D C B H J L Đường khép kín đơn ABCDEFGHIJKLM b)A M I K G F E D C B H J L Không là đường khép kín đơn AFBCDEGHIJKLM Hình 2.1. a) Đường khép kín đơn và b) Không là đường khép kín đơn Để tìm đường khép kín đơn đi qua N điểm từng đôi một khác nhau A1, A2, ..., An đã cho trên mặt phẳng toạ độ. Đầu tiên, ta chọn một điểm làm gốc (thường là điểm có tung độ bé nhất). Tiếp đó tìm các góc của các đoạn thẳng nối giữa gốc và các điểm Ai còn lại so với trục hoành. Như vậy, các góc này có giá trị nằm trong đoạn [0, 360]. Sau khi đã tìm được các góc tương ứng với các điểm Ai, ta sắp xếp các điểm Ai theo thứ tự tăng dần của góc, nếu có nhiều góc bằng nhau thì sắp xếp ưu tiên điểm gần gốc trước, điểm xa gốc sau trừ các góc cuối cùng. Đối với các góc cuối cùng thì chúng ta ưu tiên điểm xa góc toạ độ trước. Với thứ tự đó chúng ta có một đường khép kín đơn đi qua tất cả các điểm đã cho. y A5 A0 A4 A2 A3 x A1 Hình 2.2. Tính các góc thông qua đường chuẩn của gốc Thứ tự là: A0, A1, A3, A4, A2, A5 Bây giờ chúng ta sẽ tìm hiểu cách tính các góc ứng với các điểm. Gọi dx, dy là khoảng cách từ điểm gốc đến một điểm cần tính góc tương ứng theo trục hoành (trục x) và trục tung (trục y) thì gốc cần tính ở đây là tang-1(dy/dx). Mặc dù đã có nhiều ngôn ngữ hỗ trợ tính hàm tang-1 (arctang), nhưng nó thường chậm, hơn nữa chúng ta lại gặp những rắc rối khi dx = 0 và điểm đang xét nằm trong góc phần tư nào. Với mục đích chỉ dùng để sắp xếp các điểm trong phần này, chúng ta có thể sử dụng một hàm khác dễ tính hơn nhưng vẫn có cùng thuộc tính như hàm arctang, đó là hàm dy/(dx+dy). Sau đây là đoạn chương trình trả về một giá trị trong đoạn [0, 360] có tính chất tương tự như góc tạo bởi đường thẳng so với phương ngang. FUNCTION theta(P1, P2 :Point) : Real; Var dx, dy, ax, ay : Integer; t : Real; Begin dx:=P2.x–P1.x; dy:=P2.y–P1.y; ax:=abs(dx); ay:=abs(dy); If (dx=0) and (dy=0) Then t:=0 Else t:=dy/(ax+ay); If dx<0 Then t:=2–t Else If dy<0 Then t:=4+t; theta:=t*90.0; End; Sau đây là thuật toán tìm đa giác đơn khép kín từ một tập hợp điểm đã cho, thuật toán này thực chất chỉ là một phép sắp xếp theo các góc theta đối với một điểm góc đã được chọn trước (đó là điểm có tung độ y nhỏ nhất, nếu trường hợp có nhiều điểm như vậy thi ta chọn điểm có hoành độ x lớn nhất). Để đơn giản chúng tôi làm một thuật toán sắp xếp quen thuộc thông thường. Chúng ta cũng cần phải có một thủ tục để dùng để sắp xếp chi tiết khi có các góc bằng nhau. Thủ tục ArangeDetail có nhiệm vụ sắp xếp các điểm có cùng góc theo thứ tự tăng dần của khoảng cách đối với điểm gốc nếu như góc đó không phải là góc cuối cùng và sắp xếp theo thứ tự giảm dần nếu như đó là góc cuối. PROCEDURE ArrangeDetail(Var Poly :Polygon, N : Integer); Var i, j, k ,h : Integer; P : Point; Begin i:=1; While (i<=n) do Begin j:=i; While (i<n) and (theta(Poly[1],Poly[i])=theta(Poly[1],Poly[i+1])) do i:=i+1; If in Then Begin If i>j Then For k:=j to i-1 do For h:=k+1 to i do If dist(Poly[1],Poly[k])>dist(Poly[1],Poly[h]) Then Begin {dist là hàm khoảng cách giữa hai điểm} P:=Poly[k]; Poly[k]:=Poly[h]; Poly[h]:=P; End; End Else If i>j Then For k:=j to i-1 do For h:=k+1 to i do If dist(Poly[1],Poly[k])<dist(Poly[1],Poly[h]) Then Begin P:=Poly[k]; Poly[k]:=Poly[h]; Poly[h]:=P; End; i:=i+1; End; End; PROCEDURE simpleclosepath(Var Poly :Polygon, N : Integer); Var i, j : Integer; P : Point; Begin Min:=1; For i:=2 to n do If Poly[i].y<Poly[min].y Then Min:=i; For i:=1 to n do If (Poly[i].y=Poly[Min].y) and (Poly[i].x>Poly[Min].x Then Min:=i; P:=Poly[1]; Poly[1]:=Poly[Min]; Poly[Min]:=P; For i:=2 to n-1 do For j:=i+1 to n do If theta(Poly[1], Poly[i])>theta(Poly[1], Poly[j]) Then Begin P:=Poly[i]; Poly[i]:=Poly[j]; Poly[j]:=P; End; ArrangeDetail(Poly, n); End; 2.2. Thuật toán tìm bao lồi Bao lồi của một tập hợp điểm Q là đa giác lồi P nhỏ nhất chứa tất các điểm của Q. Như vậy bất kỳ một điểm nào của tập hợp Q cũng nằm trong P hoặc trên biên của P và nếu ta lấy bất kỳ hai điểm nào của Q nối lại với nhau thì đoạn thẳng nối hai điểm này nằm trong P. Theo trực giác, ta có thể hình dung mỗi điểm của Q như một chiếc đinh lồi ra từ tấm ván. Bao lồi của Q là hình dáng của dãi cao su bao quanh các chiếc đinh đó. c. Thuật toán diễu hành Jarvis (Thuật toán bao gói) Thuật toán diễu hành Jarvis tính toán bao lồi của một tập hợp Q các điểm bằng một kỹ thuật có tên là đóng gói. Thuật toán bao gói để tìm bao lồi là một thuật toán đơn giản và khá tự nhiên. Bắt đầu từ một điểm chắc chắn nằm trên bao lồi (điểm mốc), điểm này có thể là điểm có tung độ nhỏ nhất (hoặc tung độ lớn nhất, hoặc hoành độ nhỏ nhất, hoặc hoành độ lớn nhất). Dùng một tia quét ngược chiều kim đồng hồ cho đến khi đụng một điểm khác: điểm mới này phải thuộc bao lồi. Lấy điểm này làm mốc và tiếp tục quét cho đến khi gặp điểm tiếp theo, quá trình tiếp tục cho đến khi gặp lại điểm ban đầu. Như vậy ta thấy rằng, hàm theta vừa thiết lập ở trên là một trong những công cụ để ta làm tia quét. Thuật toán chạy trong thời gian O(hN), trong đó h là số đỉnh của bao lồi. Do vậy, thuật toán diễu hành Jarvis hội tụ nhanh hay chậm phụ thuộc vào số đỉnh của bao lồi P của tập hợp điểm Q. Thuật toán này có nhược điểm là khi tất cả các điểm đều thuộc bao lồi thì thời gian thực hiện của nó là N2 (với N là số điểm của tập cần tìm bao lồi). Bắt đầu từ một điểm P0 là điểm có tung độ y nhỏ nhất (trong trường hợp có nhiều điểm có tung độ y nhỏ nhất thì ta lấy điểm có hoành độ x lớn nhất), ta tìm điểm P1 có góc cự bé nhất đối với điểm P0 (trong trường hợp có nhiều góc cự bé nhất bằng nhau thì ta có thể lấy điểm xa nhất hoặc gần nhất so với P0 tuỳ theo từng yêu cầu cụ thể). Tiếp đến ta tìm điểm P2 là điểm có góc cực bé nhất đối với điểm P1. Quá trình cứ tiếp tục như vậy cho đến khi đạt đến điểm có hoành độ lớn nhất Pk, và như vậy chúng ta đã kiến tạo được xích phải của bao lồi. Để kiến tạo xích trái, ta bắt đầu từ điểm Pk và chọn Pk+1 với tư cách là điểm có góc cực bé nhất đối với Pk, nhưng so với trục x âm. Cứ tiếp tục như thế cho đến khi gặp điểm Po ban đầu. Tuy nhiên trong khi cài đặt chương trình chúng ta không cần phải chia ra thành hai phần xích trái và xích phải, mà ta gộp chung vào thành một. Rõ ràng điều này có thể thực hiện được bởi vì khi tính các điểm trên xích trái thì góc cực bé nhất đối với trục x âm cũng tương đương với góc cực ứng với trục x dương. Chúng ta có thể hình dung bằng hai hình vẽ minh hoạ sau: Hình 2.3. a. Hình ảnh các góc cực với xích trái và xích phải b. Hình ảnh các góc cực không phân biệt xích trái hay xích phải Sau đây là đoạn chương trình minh hoạ cho thuật toán diễu hành Jarvis. Kết quả trả về của chương trình là số M (số điểm của bao lồi) và bao lồi là tập các điểm P1, P2, ..., PM. FUNCTION jarvis(Var Poly : Polygon, n : Integer) : Integer; Var i, j, Min, M : Integer; Minangle : Real; P : Point; Begin Min:=1; For i:=2 to n do If Poly[i].y<Poly[min].y Then Min:=i; For i:=1 to n do If (Poly[i].y=Poly[Min].y) and (Poly[i].x>Poly[Min].x Then Min:=i; P:=Poly[1]; Poly[1]:=Poly[Min]; Poly[Min]:=P; Poly[N+1]:=Poly[1]; j:=2; Repeat M:=j-1; Min:=j; Minagle:=theta(Poly[M], Poly[j]); For i:=j+1 to n+1 do If Minagle>theta(Poly[M], Poly[i]) Then Begin Min:=i; Minagle:=theta(Poly[M], Poly[i]); End; P:=Poly[j]; Poly[j]:=Poly[Min]; Poly[Min]:=P; j:=j+1; Until Min=N+1 jarvis:=M; End; b. Thuật toán quét graham Thuật toán quét Graham bắt đầu bằng việc xây dựng một đa giác khép kín đơn từ tập hợp điểm đã cho. Từ đa giác đơn tìm được ta tìm cách lấy ra các điểm nằm trên bao lồi theo cách: Thử đặt một điểm vào bao lồi rồi kiểm tra những điểm trước đó xem có còn thuộc bao hay không nếu không thuộc bao thì ta loại các điểm này ra; nếu thuộc bao thì ta giữ lại. Để làm được việc này ta thực hiện như sau: Khi đặt một điểm Pi vào bao lồi, ta lần quanh điểm đã được đưa vào bao lồi trước đó Pi-1 với Pi-2 (tức là xem xét ba điểm PiPi-1Pi-2) và kiểm tra nó có quay phải (theo chiều kim đồng hồ) hay không; nếu có quay phải thì chúng ta loại điểm Pi-1 ra khỏi bao lồi, rồi cứ tiếp tục như vậy với Pi-2 (PiPi-2Pi-3),... cho đến khi nào không còn quay phải nữa. Quá trình lặp lại cho đến khi điểm cần xét cuối cùng PN+1. H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F H G C A B E D F Hình 2.4. Tiến trình của thuật toán quét Graham tìm bao lồi của một tập hợp điểm Việc cài đặt thuật toán không mấy phức tạp, đầu tiên ta dùng một thuật toán sắp xếp lại các điểm theo thứ tự tăng dần của các góc so với một điểm gốc để được một đa giác đơn khép kín. Tiếp theo ta thực hiện việc đặt vào các điểm và loại bỏ các điểm để có được bao lồi. Thuật toán có thể minh hoạ như sau: FUNCTION grahamscan(Var Poly : Polygon, n : Integer) : Integer; Var i, M : Integer; P : Point; Begin simpleclosepath(Poly, n); M:=3; For i:=4 to n do Begin While ccw(Poly[M], Poly[M-1], Poly[i])=1 Do M:=M-1; M:=M+1; P:=Poly[M]; Poly[M]:=Poly[i]; Poly[i]:=P; End; Grahamscan:=M; End; 2.3. Điểm nằm trong đa giác Để xét xem một điểm có P nằm trong đa giác hay không, chúng ta có thể sử dụng hai thuật toán sau: - Thuật toán số lần cắt (Crossing Number - cn) Thuật toán số lần cắt đếm số lần một tia xuất phát từ điểm P cắt cạnh của đa giác. Điểm P nằm ngoài đa giác thì số lần cắt là chẵn; ngược lại khi số lần cắt là lẻ thì điểm P nằm trong đa giác. Thuật toán này nhiều khi còn được gọi là thuật toán kiểm tra chẵn lẻ. - Thuật toán số lần bao gói (Winding Number - wn) Thuật toán này đếm số lần đa giác bao quanh điểm P. Nếu số lần bao gói lớn hơn 0 thì ta kết luận điểm P nằm trong đa giác; ngược lại thì kết luận điểm P nằm ngoài đa giác. Nếu đa giác chúng ta xét là đa giác đơn (nghĩa là nó không tự cắt), thì cả hai phương pháp trên cho cùng một kết quả như nhau với tất cả các điểm P cần kiểm tra. Nhưng với những đa giác không đơn (nghĩa là nó tự cắt), thì hai phương pháp có thể cho kết quả khác nhau đối với một số điểm. Ví dụ, khi một đa giác có phần chồng lên chính nó, thì những điểm P ở vùng chồng nhau được cho là nằm ngoài đa giác đối với thuật toán số lần cắt (do có số lần cắt các cạnh đa giác là chẵn), nhưng đối với thuật toán bao gói thì điểm P là nằm trong (do có số lần bao gói lơn hơn 0). Chúng ta có thể thấy rõ qua hình ảnh minh hoạ sau: Hình 2.5. a. Thuật toán số điểm cắt b. Thuật toán số lần bao gói Trong hình vẽ ví dụ này, chúng ta thấy những điểm nằm trong phần chồng nhau của đa giác thì thuật toán số lần bao gói cho kết quả wn=2, nghĩa là nó nằm trong đa giác hai lần. Tuy nhiên đối với thuật toán số điểm cắt thì cn là chẵn, vì vậy nó không nằm trong đa giác. Rõ ràng, thuật toán số lần bao gói tốt hơn so với thuật toán số điểm cắt, nhưng việc cài đặt khó hơn nhiều và độ phức tạp thuật toán cao hơn. a. Thuật toán số lần cắt Như đã đề cập ở trên, thuật toán này đếm số lần một tia xuất phát từ điểm P cần kiểm tra cắt các cạnh của đa giác. Nếu số lần cắt là chẵn, thì điểm P nằm ngoài đa giác; ngược lại số lần cắt lẻ thì điểm P nằm trong đa giác. Với một tia xuất phát từ P, thì rõ ràng điểm cuối của nó phải nằm ngoài đa giác. Vì vậy, nếu một điểm nằm trong đa giác thì chuỗi tuần tự của nó khi tia cắt các cạnh của đa giác như sau: in®out®...®in®out. Nếu một điểm nằm ngoài đa giác thì chuỗi tuần tự khi tia cắt các cạnh như sau: out®in®...®in®out. Có thể thấy điều này qua hình vẽ minh hoạ sau: Hình 2.6. Điểm nằm trong đa giác có số lần cắt các cạnh của đa giác là lẻ, điểm nằm ngoài đa giác có số lần cắt các cạnh của đa giác là chẵn. Tuy nhiên chúng ta cần phải lưu ý một số trường hợp đặc biệt như tia bắt đầu từ P đi qua đỉnh của đa giác, nằm chồng trên một cạnh của đa giác. Chúng ta có thể minh hoạ các trường hợp thông qua hình vẽ sau: Hình 2.7. Các trường hợp đặc biệt cần xử lý khi tính cn của thuật toán số lần cắt. Đối với trường hợp a, tia kiểm tra đi qua một đỉnh của đa giác có hai cạnh nằm về hai phía, chúng ta đếm số lần cắt là 1. Đối với trường hợp b và c, tia kiểm tra đi qua một đỉnh của đa giác có hai cạnh nằm về một phía, chúng ta đếm số lần cắt là 0. Đối với trường hợp d, tia kiểm tra trùng một cạnh của đa giác có hai cạnh nối với cạnh trùng (có tia kiểm tra đi qua) nằm khác phía, chúng ta đếm số lần cắt là 1 (cũng có thể áp dụng cho nhiều cạnh trùng liên tiếp). Nếu điểm P nằm trên cạnh trùng với tia kiểm tra thì số lần cắt được đếm là 1. Đối với trường hợp e và f, tia kiểm tra trùng một cạnh của đa giác có hai cạnh nối với cạnh trùng (có tia kiểm tra đi qua) nằm cùng phía, chúng ta đếm số lần cắt là 0 (cũng có thể áp dụng cho nhiều cạnh trùng liên tiếp). Nếu điểm P nằm trên cạnh trùng với tia kiểm tra thì số lần cắt được đếm là 1. Để cho thuật toán đơn giản tia xuất phát từ P ta lấy là tia nằm ngang (song song với trục x, nghĩa là điểm cuối của tia có toạ độ (maxint, P.y)), điều này sẽ thuận lợi cho việc nhận biết giao điểm của các cạnh với tia kiểm tra có nằm ở các đỉnh của đa giác hay không, hoặc một cạnh có trùng với tia kiểm tra hay không. Khi tia kiểm tra giao với một cạnh PiPi+1 của đa giác, nếu Pi.y hoặc Pi+1.y bằng P.y thì có một đỉnh (tương ứng Pi hoặc Pi+1) của cạnh đó; nếu Pi.y và Pi+1.y bằng P.y thì cạnh này trùng với tia kiểm tra; còn nếu Pi.y và Pi+1.y khác P.y thì tia kiểm tra cắt cạnh PiPi+1 tại một điểm giữa cạnh này. Sau đó tiến hành kiểm tra tính cùng phía hay khác phía của các cạnh liên quan. Đối với trường hợp tia kiểm tra đi qua một đỉnh Pi+1 của đa giác (nghĩa là Pi+1.y = P.y) ta sẽ xét đối với các cạnh: PiPi+1, Pi+1Pi+2, nếu (Pi.y - P.y)´(Pi+2.y - P.y)>0 thì hai cạnh này cùng phía so với tia kiểm tra, ngược lại hai cạnh này khác phía so với tia kiểm tra. Đối với trường hợp tia kiểm tra đi qua một cạnh PiPi+1 của đa giác (nghĩa là Pi.y = Pi+1.y = P.y) ta sẽ xét với các cạnh: Pi-1Pi, Pi+1Pi+2, nếu (Pi-1.y - P.y)´(Pi+2.y - P.y)>0 thì hai cạnh này cùng phía với nhau so với tia kiểm tra, ngược lại hai cạnh này khác phía với nhau so với tia kiểm tra. Trong thuật toán sau đây ta đã hoán đổi đa giác ban đầu về một đa giác cùng hình dạng nhưng đỉnh bắt đầu là đỉnh Q[1]. Q[1] là đỉnh có toạ độ y nhỏ nhất. Trong trường hợp có nhiều đỉnh có cùng toạ độ y nhỏ nhất thì ta lấy đỉnh có toạ độ x nhỏ nhất. Trong cài đặt thuật toán, ta sử dụng kỹ thuật dùng một điểm Q[0] có toạ độ (-∞, ∞) để làm lính canh cho việc xử lý trường hợp đỉnh Q[1]. Kết quả trả về của đoạn chương trình là True nếu điểm P nằm trong đa giác; False nếu điểm P nằm ngoài đa giác. FUNCTION cn_poly(P: Point; Poly: Polygon, n: Integer):Boolean; Var d1, d2, cn, i, j, Min : Integer; L1, L2 : Line; Q : Polygon; Begin Min:=1; For i:=2 to n do If Poly[i].y<Poly[min].y Then Min:=i; For i:=1 to n do If (Poly[i].y=Poly[Min].y) and (Poly[i].x<Poly[Min].x Then Min:=i; j:=1; For i:=Min to N do Begin Q[j]:=Poly[i]; j:=j+1; End; For i:=1 to Min-1 do Begin Q[j]:=Poly[i]; j:=j+1; End; Q[0].x:=-maxint; Q[0].y:=maxint; {Điểm làm lính canh} Q[N+1]:=Q[1]; L1.P1:=P; L1.P2.x:=maxint; L1.P2.y:=P.y; cn:=0; For i:=1 to n do Begin L2.P1:=Q[i]; L2.P2:=Q[i+1]; If Intersect(L1, L2) Then Begin If (P.y=Q[i].y) Then Begin If (P.y=Q[i+1].y) Then {Trùng với một cạnh} If ((P.x>=Q[i].x) and (P.x<=Q[i+1].x)) or ((P.x>=Q[i+1].x) and (P.x<=Q[i].x)) Then cn:=cn+1 Else Begin d1:=Q[i-1].x – P.x; d2:=Q[i+2].x – P.x; If d1*d2 < 0 Then cn:=cn+1; End; Else Begin d1:=Q[i-1].x – P.x; d2:=Q[i+1].x – P.x; If d1*d2 < 0 Then cn:=cn+1; End; End; Else If (P.y Q[i+1]) Then cn:=cn+1; End; End; If (cn mod 2 = 0) Then cn_poly:=False; Else cn_poly:=True; End; b. Thuật toán số lần bao gói Thuật toán số lần bao gói đếm số lần đa giác bao quanh điểm P, nếu số lần này lơn hơn 0 thì điểm P nằm trong đa giác. Thuật toán này cho phép ta kiểm tra đối với đa giác tự cắt (có các phần chồng lên nhau). Với một đa giác P1, P2, ...,Pn và điểm P cho trước. Một tia xuất phát từ P song song với trục hoành dùng để xét xem tia kiểm tra này có cắt các cạnh hay không? Khi tia kiểm tra cắt một cạnh của đa giác, ta sẽ quyết định cộng thêm cho số lần bao gói (wn) 1 đơn vị, hay trừ đi số lần bao gói 1 đơn vị tuỳ theo hướng của cạnh bị cắt. Hình ảnh sau minh hoạ việc cộng thêm 1 đơn vị hay trừ đi 1 đơn vị cho wn. Hình 2.8. Khi tia kiểm tra cắt các cạnh của đa giác thì số lần bao gói tăng lên hoặc giảm xuống 1 đơn vị tuỳ theo cạnh đó đi lên hay đi xuống Khi tia kiểm tra xuất phát từ P cắt cạnh PiPi+1, ta xét xem cạnh này đi lên hay đi xuống để biết P nằm bên trái hay bên phải của cạnh PiPi+1. Nếu tam giác PiPi+1P ngược chiều kim đồng hồ thì P nằm bên trái cạnh PiPi+1, lúc này ta cho wn tăng lên 1 đơn vị; ngược lại PiPi+1P cùng chiều kim đồng hồ thì P nằm bên phải cạnh PiPi+1 và cho wn giảm đi 1 đơn vị. Vì vậy, chúng ta cần thiết kế một hàm mà kết quả trả về cho biết điểm P nằm phía bên trái hay phía bên phải hay trên một cạnh của đa giác. Nếu kết quả trả về là 1 thì P nằm bên trái của cạnh đó; nếu kết quả trả về là 0 thì P nằm trên cạnh đó; nếu kết quả trả về là -1 thì P nằm bên phải của cạnh đó. P Pi Pi+1 Hình 2.9. a. Cạnh đi lên, P nằm bên phải cạnh PiPi+1. P Pi Pi+1 b. Cạnh đi xuống P nằm bên phải trái PiPi+1. Sau đây là đoạn chương trình cho biết điểm P nằm bên trái hay bên phải hay trên cạnh PiPi+1 của một đa giác. FUNCTION isLeft(P, P1, P2 : Point) : Integer; Var d : Integer; Begin d:=((P1.x-P.x)*P2.y-P.y)-(P2.x-P.x)*(p1.y-P.y)); If d>0 Then isLeft:=1 Else If d=0 Then isLeft:=0 Else isLeft:=-1 End; Tiếp theo đây là đoạn chương trình cho biết điểm P có nằm trong đa giác hay không. Kết quả tra về là True nếu điểm P nằm trong đa giác; ngược lại kết quả trả về là False nếu điểm P nằm ngoài đa giác. FUNCTION wn_poly(P: Point; Poly: Polygon, n: Integer):Boolean; Var wn, i, j, Min : Integer; L1, L2 : Line; Q : Polygon; Begin wn:=0; For i:=1 to n-1 do Begin If (Poly[i].y<=P.y) Then Begin If (Poly[i+1]>P.y) Then If (isLeft(P, Poly[i], Poly[i+1])>0) Then wn:=wn+1 End Else Begin If (Poly[i+1].y<=P.y) Then If (isLeft(P, Poly[i], Poly[i+1])<0) Then wn:=wn-1; End; End; If (wn > 0) Then wn_poly:=True; Else wn_poly:=False; End; Phần này đã trình bày hai thuật toán dùng để kiểm tra xem một điểm có nằm trong đa giác hay không. Đối với thuật toán cn, ta cũng có thể cải tiến theo hướng như thuật toán wn để quá trình kiểm tra đỡ phức tạp hơn, hiệu quả của thuật toán cao hơn, và độ phức tạp thuật toán bé hơn. Độ phức tạp của hai thuật toán trên là O(N) 4. Giao và hợp của các đối tượng cơ bản Các bài toán tìm phần giao và phần hợp của các đối tượng hình học phẳng như hình tròn, đa giác, ... là những bài toán khá hay và để tìm ra các 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 của 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, ... 4.1. Giao của hai đường thẳng tổng quát Một đường thẳng tổng quát trong mặt phẳng toạ độ bao giờ cũng có phương trình là ax + by = c (1). Tuy nhiên, không phải lúc nào ta cũng có phương trình đường thẳng như dạng trên, mà thay vào đó là đường thẳng đi qua hai điểm P1(x1, y1), P2(x2, y2). Trong trường hợp như vậy, ta phải tìm cách chuyển về dạng (1) để cho việc tìm giao điểm được dễ dàng hơn. Đối với đường thẳng đi qua hai điểm phân biệt P1(x1, y1), P2(x2, y2) ta có thể chuyển về dạng (1) theo cách: viết phương trình đường thẳng đi qua hai điểm P1(x1,y1), P2(x2,y2) như sau: Û (x - x1)(y2 – y1) = (y – y1)(x2 – x1) Û (y2 – y1)x + (x1 – x2)y = (x1 – x2)y1 + (y2 – y1)x1 Û (y2 – y1)x + (x1 – x2)y = x1y2 - x2y1 Đây chính là phương trình dạng (1) đã được đề cập ở trên. Vấn đề đặt ra là tìm giao điểm của hai đường thẳng tổng quát có phương trình lần lượt là: a1x + b1y = c1 và a2x + b2y = c2. Việc tìm giao điểm này thực chất là việc giải hệ phương trình: (2) Sau đây là đoạn chương trình tìm giao điểm của hai đường thẳng dựa trên việc giải hệ phương trình (2). Kết quả trả về của hàm là True và toạ độ của điểm giao nhau (một cặp số thực thông qua bản ghi Point) nếu hai đường thẳng này giao nhau, ngược lại, nếu hai đường thẳng không giao nhau thì hàm trả về kết quả là False. FUNCTION int_point(a1,b1,c1,a2,b2,c2:Real; Var P:Point):Boolean; {Ở đây chúng ta có thể xem Point là một bản ghi có hai thành phần đều là số thực} Var D, DX, DY : Real; Begin D:=a1*b2-a2*b1; DX:=c1*b2-c2*b1; DY:=a1*c2-a2*c1; If D0 Then Begin P.x:=DX/D; P.y:=DY/D; int_point:=True; End Else int_point:=False; End; 4.2. Giao và hợp của hai đường tròn Bài toán: Với hai đường tròn có tâm và bán kính cho trước lần lượt là P1(x1, y1), R1 và P2(x2, y2), R2. Yêu cầu: Tìm phần giao và phần hợp của hai đường tròn này. Hình 2.12. Phần diện tích giao nhau của hai hình tròn là phần được gạch chéo Việc tìm phần giao của hai đường tròn này được thực hiện thông qua phương pháp chia lưới, nghĩa là chúng ta 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 trục tung và trục hoành. Tiến hành kiểm tra từng ô vuông, nếu nó nằm trong cả hai đường tròn thì chúng ta cộng vào giá trị diện tích cần tìm một lượng chính bằng diện tích của ô vuông đó. Đây cũng chính là kỹ thuật tìm phần giao của nhiều đối tượng hình phẳng với nhau như đa giác, elíp, ... Hình 2.12. Chia lưới để tính diện tích phần giao nhau của hai hình tròn Theo như thuật toán chúng ta cần phải quét hết các ô vuông có trong mặt phẳng hay ít ra thì cũng là những ô vuông của phần mặt phẳng chứa cả hai đường tròn. Như vậy số lượng ô vuông cần phải duyệt là quá lớn. Ta cần có một kỹ thuật để hạn chế số lượng hoặc khoanh vùng các ô vuông cần kiểm tra. Đối với bài toán trên, 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 hình tròn. Để thực hiện thao tác chia mặt phẳng thành lưới các ô 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. Muốn kiểm tra một ô vuông có thuộc hình tròn hay không chúng ta xét một cách một cách đơn giản là nếu đỉnh trên bên trái của nó thuộc hình tròn thì nó sẽ thuộc hình tròn. Phương pháp này chỉ cho kết quả gần đúng. Kích thước các ô vuông càng nhỏ thì độ chính xác càng cao nhưng tốc độ thực hiện lại chậm. Sau đây là đoạn chương trình tính diện tích phần giao của hai đường tròn. FUNCTION distance(P1, P2 : Point) : Real; Begin distance:=sqrt(sqr(P1.x-P2.x)+sqr(P1.y-P2.y)); End; Tính diện tích phần giao nhau của hai hình tròn. FUNCTION area_int_cc(P1, P2 : Point; R1, R2 : Real):Real; {Ở đây chúng ta có thể xem Point là một bản ghi có hai thành phần đều là số thực} Var s : Real; P, Q : Point; Begin s:=0; If distance(P1, P2)<R1+R2 Then Begin P.x:=P1.x-R1; Q.x:=P1.x+R1; Q.y:=P2.y+R1; While P.x<Q.x Do Begin P.y:=P2.y-R1; While P.y<Q.y Do Begin If (distance(P, P1)<R1) and (distance(P, P2)<R2) Then s:=s+0.0025; P.y:=P.y+0.05; End; P.x:=P.x+0.05; End; End; area_int_cc:=s; End; Chương trình tìm giao của hai hình tròn có thể cải tiến thêm để tăng tốc độ thực hiện bằng cách chỉ duyệt các ô vuông nằm trong hình chữ nhật là giao của hai hình vuông ngoại tiếp hai hình tròn Thuật toán tìm phần hợp của hai hình tròn rất đơn giản, chúng ta lấy tổng diện tích của hai hình tròn trừ đi phần diện tích giao của hai hình tròn. Đoạn chương trình mô tả thuật toán như sau: FUNCTION area_uni_cc(P1, P2 : Point; R1, R2 : Real):Real; {Ở đây chúng ta có thể xem Point là một bản ghi có hai thành phần đều là số thực} Var s : Real; P, Q : Point; Begin s:=area_int(P1, P2, R1, R2); area_uni_cc:=Pi*(sqr(R1) + sqr(R2))-s; End; 4.3. Giao của đa giác với hình tròn Bài toán: Cho một đa giác được xác định bởi N điểm P1, P2, .., Pn và một hình tròn có tâm P bán kính là R. Yêu cầu: Tìm diện tích phần giao nhau của đa giác với hình tròn trên. Cũng tương tự như việc tìm giao của hai hình tròn, ta có thể tìm phần diện tích giao của đa giác với hình tròn theo thuật toán trên. Ta sẽ quét tất cả các ô vuông nằm trong hình vuông ngoại tiếp hình tròn, sau đó kiểm tra xem ô vuông này có thuộc hình tròn và đa giác không. Nếu thuộc thì ta sẽ cộng thêm phần diện tích này vào phần diện tích cần tìm. Hình 2.12. Chia lưới để tính diện tích phần giao nhau của đa giác và hình tròn Có thể minh hoạ thuật toán qua đoạn chương trình sau: FUNCTION area_int_pc(P:Point;R:Real;Poly:Polygon;n:Integer):Real; {Ở đây chúng ta có thể xem Point là một bản ghi có hai thành phần đều là số thực} Var s : Real; A, B : Point; Begin s:=0; A.x:=P.x-R; B.x:=P.x+R; B.y:=P.y+R; While A.x<B.x Do Begin A.y:=P.y-R; While A.y<B.y Do Begin If (distance(A, P)<R) and (cn_Poly(A, Poly, n)) Then s:=s+0.0025; A.y:=A.y+0.05; End; A.x:=A.x+0.05; End; End; area_int_pc:=s; End; 4.4. Giao của đa giác với đa giác Bài toán: Cho hai đa giác được xác định bởi các điểm P1, P2, .., Pn và Q1, Q2, …,Qm. Yêu cầu: Tìm diện tích phần giao của hai đa giác Áp dụng thuật toán đã nói trên, ta sẽ quét tất cả các ô vuông nằm trong hình chữ nhật ngoại tiếp một đa giác, sau đó kiểm tra xem ô vuông này có hai đa giác không. Nếu thuộc thì chúng ta sẽ cộng thêm phần diện tích này vào phần diện tích cần tìm. Hình 2.12. Chia lưới để tính diện tích phần giao nhau của hai đa giác Có thể minh hoạ thuật toán qua đoạn chương trình sau: FUNCTION area_int_pp(P,Q:Polygon;n,m:Integer;):Real; {Ở đây chúng ta có thể xem Point là một bản ghi có hai thành phần đều là số thực} Var s : Real; i : integer; A, B : Point; Miny : Real; Begin s:=0; A.x:=P[1].x; For i:=2 to n do If A.x>P[i].x Then A.x:=P[i].x; B.x:=P[1].x; For i:=2 to n do If B.x<P[i].x Then B.x:=P[i].x; Miny:=P[1].y; For i:=2 to n do If Miny>P[i].y Then Miny:=P[i].y; B.y:=P[1].y; For i:=2 to n do If B.y<P[i].y Then B.y:=P[i].y; While A.x<B.x Do Begin A.y:=Miny; While A.y<B.y Do Begin If (cn_Poly(A, P, n)) and (cn_Poly(A, Q, m)) Then s:=s+0.0025; A.y:=A.y+0.05; End; A.x:=A.x+0.05; End; End; area_int_pp:=s; End;