Các giải thuật hình học Computational Geometry

*Chương 4:Các giải thuật hình họcComputational GeometryPGS. TS. TRẦN CAO ĐỆĐại Học Cần Thơ 2013*Dữ liệu nhiều chiềuCác giải thuật hình học liên quan tới dữ liệu không gian đa chiều.Một điểm trong mặt phẳng (x,y)Một điểm trong không gian (x,y,z)Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiềuMột số bài toán quan trọngTìm kiếm theo phạm vi (range searching query)Tìm bao lồi (convex hull)*Cây tìm kiếm phạm viMột điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1,,xd-1).Tìm kiếm theo phạm vi là tìm kiếm các điểm trong một phạm vi nào đó.Ví dụ tìm các điểm gần với (xq,yq) trong khoảng cách r. Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r)Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi.*Tìm kiếm 1 chiều theo phạm viCho một tự điển (tập hợp các phần tử) có thứ tự findAllInRange(k1,k2): trả về các phần tử thỏa:k1 ≤ x ≤ k2Dùng cấu trúc cây TKNP để lưu trữ các phần tử Giải thuật tìm kiếm 1DTreeRangeSearch(k1,k2,v)Nếu v là nút ngoài (V=NULL): dừngNếu v là nút trongKey(v)k2: tìm đệ qui trên cây con trái của v.*Giải thuật 1DTreeRangeSearch1DTreeRangeSearch(k1,k2,v){ if v.isExternal(v) return ; if (k1 ≤ key(v) ≤ k2) { L= 1DTreeRangeSearch(k1,k2,T.leftChild(v)); R= 1DTreeRangeSearch(k1,k2,T.rightChild(v)); return L U {element(v)} U R; } else if (key(v) x2 L=2DTreeRangeSearch(x1,x2,y1,y2,T.leftChild(v),t); R= ; }}Return L U M U R;Gọi lần đầu tiên: 2DTreeRangeSearch(x1,x2,y1,y2,T.root(),”middle”); *Hiệu quả của giải thuật Giải thuật tìm kiếm 2 chiều theo phạm vi chứa n phần tử lấy thời gian O(log2n+s) với s là số phần tử trả về sau tìm kiếm.Chứng minh: xem trang 554-GoodrichO(logn) nút biênMỗi nút phân phối (allocation) v duyệt 1 chiều mất O(lognv+sv), nv là số nút trên cây Tv (cấu trúc phụ)Có O(logn) nút allocation Thời gian O(log2n+s)*Cây tứ phân (Quadtrees)Trong các bài toán xử lí ảnh Xử lí các điểm có tọa độ hạn chế (2048x2048)Các điểm tập trungXét các điểm trong mặt phẳng (x,y)Cây tứ phân là cây mỗi nút trong ứng với một vùng hình vuông RCác nút con của một nút tương ứng với 4 hình vuông con ở 4 góc của R.Các nút được phân chia một cách đệ qui để mỗi vùng chứa 1 điểm. Vùng chứa 1 điểm coi như là một nút ngoài. rr1r2r4r3*Ví dụfamkbdjilghecNút trongNút ngoài*Hiệu quả cây tứ phânNếu có hai điểm rất gần nhau thì thời gian xây dựng cây sẽ rất lâuThiết kế một biên (bound) D, chiều sâu giới hạn.Thời gian xây dựng cây tứ phân cho n điểm trong mặt phẳng là O(D*n), D là chiều sâu giới hạn của cây.*Tìm kiếm trên cây tứ phânTập S các điểm Giả sử câu truy vấn là hình chữ nhật AKết quả tìm kiếm là tất cả các điểm thuộc S nằm trong A.Tìm kiếmBắt đầu từ gốc r của cây.Nếu vùng R (tương ứng với r)  A =  : dừngNếu R  A: tất cả các nút lá của cây gốc r đều là kết quả. Nếu R  A ≠ : tìm kiếm đệ qui trên mỗi con v của nút r.Thời gian tìm kiếm là O(D*n), với n là số nút ngoài. Giải thuật tìm kiếm có thời gian > thời gian của giải thuật tìm brute forte!Trong thực hành thì TK trên cây tứ phân nhanh hơn tìm kiếm brute forte!*k-d-TreesCây tứ phân không thể tổng quát hóa cho nhiều chiều. KG 3 chiều mỗi nút có 8 nút con; KG d chiều, mỗi nút có 2d nút con.Cây k-d: là cây nhị phân được xây dựng khá tương tự với cách xây dựng cây tứ phân.Mỗi nút tương ứng với một vùng hình chữ nhật Phân chia không gian chứa các điểm thành các hình chữ nhật, mỗi hình chứa 1 điểm.*Hai loại cây k-dDựa trên vùng (region based)Chia vùng HCN thành hai HCN theo trục dài nhất. Nếu có nhiều trục dài bằng nhau thì chia xoay vòng theo các trục.Dựa trên điểm (point-based)Chia theo phân phối điểm. Mỗi HCN chứa phân nửa số điểmegcpjfnlhakmibod*Tìm kiếm gần nhất (nearest neigbor searching) Cho một điểm p, truy vấn: tìm điểm gần p nhất:Tìm kiếm (từ nút gốc) nút ngoài v tương ứng với vùng R nhỏ nhất chứa p.Các điểm thuộc R và thuộc các vùng tương ứng với nút anh em của v đều được so sánh để tìm điểm q gần nhất hiện tại.Định nghĩa hình tròn s(p,pq)Duyệt cây tìm các vùng giao với s khác rỗngTrong khi duyệt nếu tìm thấy điểm q’ gần p hơn q, thay q=q’.*Hiệu quả tìm kiếmTìm kiếm điểm gần nhấtTrong trường hợp xấu nhất: O(n) Trung bình: O(logn)Nhiều cải tiến giải thuật rất có ý nghĩa.*Kỹ thuật trượt phẳng (Plane sweep technique)Kỹ thuật trượt/quét phẳng áp dụng vào nhiều bài toán hình học. Ý tưởng: 1 chiều hóa bài toán 2 chiều*Giao đoạn thẳng trực giaoBài toán tổng quát: Cho n đoạn thẳng, tìm giao của tất cả các cặp đoạn thẳngBrute forte: xét n(n-1)/2 cặp, thời gian O(n2)Bài toán hạn chế: cho n đoạn thẳng trực giao, nghĩa là các đoạn song song với ox hoặc oy.Chuyển từ 2D sang 1D:Mỗi đọan thẳng thẳng đứng v, xét đường thẳng l(v) đi ngang qua v.Xét đường l với các đoạn thẳng nằm ngang  1D hóa (v,y), v cố địnhGọi S(v) là tập hợp các điểm là giao của l(v) và các đoạn thẳng nằm ngang. Thì việc tìm giao điểm của v và các đoạn nằm ngang tương đương với việc tìm kiếm 1 chiều theo y.*Giải thuật trượt phẳngCho trượt đường thẳng l thẳng đứng từ trái sang phải.Khi trượt, lưu các đoạn đang có giao điểm với l vào tự điển S (tổ chức có thứ tự theo tọa độ y)Các sự kiện và hành động:Sự kiệnHành độngGặp đầu trái của đoạn ngang hThêm h vào tự điển SGặp đầu phải của đoạn ngang hLoại h khỏi tự điển SGặp đoạn thẳng thẳng đứng vThực hiện tìm kiếm theo phạm vi trên S với phạm vi là tọa độ y của hai đầu điểm v*Hiệu quảThời gian thực hiện trượt phẳng để tìm giao điểm của n đoan thẳng trực giao cho trước là O(nlogn+s), với s là số giao điểm.*Tìm một cặp điểm gần nhấtCho tập gồm n điểmTìm một cặp điểm (p,q) gần nhau nhất. Khoảng cách giữa 2 điểm: d(a,b)=sqrt((xa-xb)2+(ya-yb)2)Brute forte: O(n2)Trượt phẳng:Dùng 1 đường thẳng thẳng đứng, trượt từ trái sang phải từ điểm trái nhất.Lưu giữ các cặp điểm gần nhất và các điểm gần với đường quét*Ý tưởngKhi quét ngang qua 1 điểm ta lưu trữ:Cặp điểm gần nhất trong tập hợp các điểm đã quét qua (a,b) với khoảng cách d(a,b)Một tự điển S chứa các điểm đã quét qua theo thứ tự tọa độ y.Như vậy, khi quét ngang 1 điểm p phải thực hiện các phép toán sau:Loại bỏ khỏi S các điểm r thỏa: x(p)-x(r) > dTìm điểm q trong S sao cho d(p,q)3 điểm (không thẳng hàng) trong mặt phẳng, tìm đa giác lồi:có các đỉnh thuộc tập các điểm đã cho, chứa tất cả các điểm đã cho.Đa giác là một chuỗi khép kín các đỉnh đa giác. Đa giác đơn: giao của hai cạnh bất kỳ (nếu có) là đỉnh của đa giác. Đa giác lồi nếu nó là đơn và mọi góc trong đều nhỏ hơn .*Hướng của 3 điểmCho một bộ 3 điểm (p,q,r)(p,q,r) là “cua trái” nếu chúng có hướng ngược chiều kim đồng hồ, tức là góc (p,q,r) <  nằm bên trái pq. (p,q,r) là “cua phải” nếu chúng có hướng cùng chiều kim đồng hồ, tức là góc (p,q,r) <  nằm bên phải pq. nếu (p,q,r)= thì 3 điểm thẳng hàng.pqrpqr*Phân tích toán họcCho ba điểm p1(x1,y1), p2(x2,y2), p3(x3,y3)Xét định thức x1 y1 1 (p1,p2,p3)= x2 y2 1 x3 y3 1Định lý: (p1,p2,p3) là cua trái, cua phải hoặc thẳng hàng tùy theo  dương, âm hoặc bằng 0 tương ứng. *Kiểm tra hai đoạn thẳng giao nhauCho hai đoạn thẳng s1=p1q1,s2=p2q2. s1 và s2 giao nhau nếu một trong các điều kiện sau thỏa:(p1,q1,p2), (p1,q1,q2) khác hướng VÀ (p2,q2,p1), (p2,q2,p2) khác hướng.(p1,q1,p2), (p1,q1,q2), (p2,q2,p1) và (p2,q2,q1) thẳng hàng, VÀ hình chiếu lên trục x của s1 và s2 là giao nhau, VÀ hình chiếu của s1 và s2 lên trục y là giao nhau. *Tính chất cơ bản của bao lồiVùng R là lồi nếu hai điểm p,q thuộc R thì cả đoạn thẳng pq thuộc R.Định lý: Cho S là tập hợp điểm và H là bao lồi của S, ta có:Cặp (a,b) làm thành một cạnh của H nếu và chỉ nếu tất cả điểm khác thuộc nửa mặt phẳng xác định bởi đường thẳng ab.Điểm p là một đỉnh của bao lồi nếu và chỉ nếu tồn tại một đường thẳng l đi qua p sao cho tất cả các điểm khác p thuộc về nửa mặt phẳng xác định bởi lĐiểm p không phải là đỉnh của H nếu và chỉ nếu p chứa trong một tam giác có 3 đỉnh là 3 điểm khác trong S hoặc p thuộc một đoạn thẳng nối hai đỉnh khác. *Hệ quả Các điểm sau đây sẽ luôn nằm trên biên của bao lồiĐiểm có tọa độ x nhỏ nhấtĐiểm có tọa độ x lớn nhấtĐiểm có tọa độ y nhỏ nhấtĐiểm có tọa độ y lớn nhất*Giải thuật “gói quà” (gift wrapping)Chọn điểm A(xmin,ymin), A là một đỉnh của bao lồi, gọi là điểm neo (anchor)Xét tia AxQuay tia Ax ngược chiều kim đồng hồ cho đến khi gặp một điểm B. B là đỉnh kế tiếp A trên bao lồi. Thay A bởi B và tiếp tục quay tia Ax.Cho đến khi điểm B tìm thấy trùng với điểm neo.ABAB*Định lýCho tập S gồm các điểm trong mặt phẳng, a là một đỉnh của bao lồi H của S, điểm p là đỉnh kế tiếp trên bao lồi khi quay ngược chiều kim đồng hồ thì (a,p,q) là “cua trái” với mọi điểm q của S.Gọi C(a) hướng của (a,p,q), định nghĩa:C(a).isLess(p,q) nếu và chỉ nếu (a,p,q) là một “cua trái”*Hiệu quả của giải thuật “gói quà”Cho n là số điểm, h là số đỉnh của bao lồi (h≤n). Thời gian thực hiện “gói quà” là O(hn), trong trường hợp xấu nhất h=n thì thời gian gói quà là O(n2).Gọi p0,p1,,ph-1 là các đỉnh bao lồi.Thời gian tìm điểm neo p0 là O(n)Ở bước i: thời gian tìm đỉnh kế tiếp (tính C(pi-1)) là O(n)Có h đỉnh phải tìm vậy thời gian là O(hn)Trong trường hợp xấu nhất h=n thì thời gian “gói quà” là O(n2). *Giải thuật quét Graham (Graham Scan)Cho tập P các điểm trong mặt phẳngGiải thuật tìm bao lồi HTìm một điểm A nằm trên bao lồi, gọi là điểm neo; ví dụ điểm có tọa độ y nhỏ nhất. Thêm A vào HSắp xếp các điểm P-{A} theo C(A), tức là góc của hợp phương ngang (tia Ax).Xét các điểm p  P-{A} theo thứ tự trênThêm p vào H nếu H có ít hơn 2 điểm hoặc Nếu p hợp với hai điểm trước đó làm thành một cua tráiXóa điểm cuối cùng trong H trong trường hợp ngược lại và lặp lại test đối với p*Giải thuật quét GrahamScan(S,a){//Input: S là danh sách có thứ tự theo chiều ngược chiều kim đồng hồ; a là điểm neo//Output: S chứa các đỉnh của bao lồi (các đỉnh còn lại sau khi thực hiện giải thuật)S.Append(a)Prev=S.first();//prev=aCurr=S.after(prev);Do{ next=S.after(curr) if isLeftturn(prev,curr,next) prev=curr else{ S.remove(curr); prev=S.before(prev); } curr=S.after(prev)} while curr!=S.last()S.Remove(S.last());//xóa điểm neo a }*Hiệu quả của giải thuật quét GrahamTìm điểm neo O(n)Sắp xếp các điểm O(nlogn)Giải thuật quét thực hiện vòng lặp do..while nhiều nhất là 2n, mỗi lần mất O(1)Vậy thời gian thực hiện giải thuật quét Graham là O(nlogn).*Cài đặt giải thuật quét GrahamTrang 583-586, Algorithm Design, Goodrich.Hết chương 5