Luận văn Tóm tắt Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin địa lý

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- BÙI THANH HUYỀN NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN TÍCH KHÔNG GIAN TRONG HỆ THÔNG TIN ĐỊA LÝ CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01 Người hướng dẫn khoa học: PGS. TS. Đặng Văn Đức TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012 - 1 - MỞ ĐẦU Hệ thống thông tin địa lý GIS (Geographical Information System) đã được khá nhiều người quan tâm muốn tìm hiểu và ngày càng nhiều tổ chức kinh tế xã hội ứng dụng trong công tác nghiên cứu khoa học và sản xuất. Công nghệ GIS đã và đang thâm nhập như một nhu cầu tất yếu vào hầu hết các ngành. Thông tin GIS cung cấp cho người sử dụng hướng thay đổi của dữ liệu trong một lãnh thổ theo thời gian, đồng thời xác định những gì có thể xẩy ra khi có sự thay đổi dữ liệu đó. Nói cách khác GIS cung cấp cho người sử dụng những mô hình khác nhau của sự thay đổi. Dữ liệu bản đồ là thành phần chính trong cơ sở dữ liệu của GIS. Các bản đồ gắn chặt với thế giới thực và luôn được bổ sung những thông tin mới. Nền tảng của thông tin hình học trong GIS là bản đồ đã được số hóa ở dạng nào đó để thực hiện từ những phép tính đơn giản như: đo đạc diện tích, chu vi, chiều dài, vị trí … đến những phép tính phức tạp như: mở rộng diện tích, xác định giao của nhiều vùng diện tích … là những bài toán khá phổ biến trong quản lý và nghiên cứu khoa học. Không giống như các CSDL thông thường, GIS rất trực quan, thuận tiện và cùng một lúc cung cấp cho người sử dụng nhiều thông tin một cách tổng hợp. Nhận thấy những tiện ích của GIS, em lựa chọn và thực hiện đề tài “Nghiên cứu một số thuật toán phân tích không gian trong hệ thông tin địa lý” nhằm khắc phục những hạn chế và đáp ứng các yêu cầu trên. Dữ liệu không gian, các phép toán phân tích không gian và ứng dụng của chúng. - 2 - CHƯƠNG 1 – KHÁI QUÁT VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ GIS 1.1. Định nghĩa GIS Hệ thông tin địa lý (GIS - Geographical Information System), là một hệ thống thông tin có khả năng thu thập, cập nhập, quản trị và phân tích, biểu đồ dữ liệu địa lý phục vụ giải quyết các bài toán ứng dụng có liên quan tới vị trí địa lý trên bề mặt trái đất hoặc được định nghĩa như làm một hệ thông tin với khả năng truy nhập, tìm kiếm, xử lý, phân tích và truy xuất dữ liệu địa lý nhằm hỗ trợ cho công tác quản lý, quy hoạch và quản lý tài nguyên thiên nhiên, môi trường và y tế. Mục tiêu của GIS là cung cấp cấu trúc một cách hệ thống để quản lý các thông tin địa lý khác nhau và phức tạp, đồng thời cung cấp các công cụ, các thao tác hiển thị, truy vấn, mô phỏng… Cái GIS cung cấp là cách thức suy nghĩ mới về không gian. Phân tích không gian chỉ là truy cập mà còn cho phép khai thác các quan hệ và tiến trình biến đổi của chúng. Công nghệ GIS tích hợp giữa các thao tác trên cơ sở dữ liệu như: đưa ra các câu hỏi truy vấn (query), phân tích thống kê (statistcal analysis) với việc thể hiện và các phép phân tích địa lý. Những khả năng đó của hệ thống GIS đã phân biệt GIS với các hệ thống thông tin khác và tạo cho nó một giá trị đến khu vực công cộng và các nhân để giải thích các sự kiện, và lên kế hoạch chiến lược. 1.2. Các thành phần của GIS Hệ thống GIS có 5 thành phần cơ bản bao gồm con người, phương pháp, phần cứng tin học, phần mềm tin học và dữ liệu. Tầm quan trong mỗi thành phần và các mối quan hệ giữa chúng: 1.2.1. Con người (People) Công nghệ GIS sẽ bị hạn chế nếu không có con người tham gia - 3 - quản lý hệ thống và phát triển những ứng dụng GIS trong thực tế. Người sử dụng GIS có thể là những chuyên gia kỹ thuật, người thiết kế và duy trì hệ thống, hoặc những người dùng GIS để giải quyết các vấn đề công việc. 1.2.2. Dữ liệu (Data) Dữ liệu được sử dụng trong GIS không chỉ là số liệu địa lý mà còn phải được thiết kế trong một cơ sở dữ liệu. Những thông tin là sẽ bao gồm các dữ kiện về vị trí địa lý, thuộc tính của thông tin, mối liên hệ không gian của các thông tin, và thời gian. 1.2.3. Phần cứng (Hardware) Phần cứng là hệ thống các máy tính điện tử trên đó hệ GIS hoạt động. Ngày nay, phần mềm GIS chạy trên rất nhiều dạng phần cứng, từ máy chủ trung tâm đến các máy trạm hoạt động độc lập hoặc liên kết mạng. 1.2.4. Phần mềm (Software) Là tập hợp các câu lệnh, chỉ thị nhằm điều khiển phần cứng của máy tính thực hiện một nhiệm vụ xác định, phần mềm hệ thống thông tin địa lý có thể là một hoặc tổ hợp các phần mềm máy tính. Phần mềm GIS cung cấp các chức năng và các công cụ cần thiết để lưu trữ, phân tích và hiển thị thông tin địa lý. 1.2.5. Phương pháp (Methods) Đây là hợp nhất rất quan trọng để đảm bảo khả năng hoạt động của hệ thống, là yếu tố quyết định sự thành công của việc phát triển công nghệ GIS. Hệ thống GIS cần được điều hành bởi một số bộ phận quản lý, bộ phận này phải được bổ nhiệm để tổ chức hoạt động hệ thống GIS một cách có hiệu quả để phục vụ người sử dụng thông tin. 1.3. Cấu trúc dữ liệu trong GIS 1.3.1. Dữ liệu không gian Dữ liệu không gian là dữ liệu về đối tượng mà vị trí của nó được xác định trên bề mặt Trái đất. Dữ liệu không gian sử dụng - 4 - trong hệ thống địa lý luôn được xây dựng trên một hệ thống tọa độ. Mô hình dữ liệu quyết định cách thức mà dữ liệu được cấu trúc, lưu trữ, xử lý và phân tích trong một hệ thông tin địa lý. Mô hình dữ liệu raster sử dụng lưới để thể hiện đặc trưng không gian. Mô hình dữ liệu Vector sử dụng các điểm và tọa độ của chúng để xây dựng các đặc trưng không gian như điểm, đường và vùng. Các đặc trưng dựa trên mô hình dữ liệu véctơ được coi như các đối tượng riêng biệt trong không gian. Nhiều hệ thông tin địa lý sử dụng cả hai mô hình dữ liệu vector và raster Mô hình dữ liệu dạng raster phản ánh toàn bộ vùng nghiên cứu dưới dạng một lưới các ô vuông hay điểm ảnh (pixel). Mô hình raster có các đặc điểm: Các điểm được xếp liên tiếp từ trái qua phải và từ trên xuống dưới. Mỗi một điểm ảnh (pixel) chứa một giá trị. Một tập các ma trận điểm và các giá trị tương ứng tạo thành một lớp (layer). Trong cơ sở dữ liệu có thể có nhiều lớp. Mô hình dữ liệu raster là mô hình dữ liệu GIS được dùng tương đối phổ biến trong các bài toán về môi trường, quản lý tài nguyên thiên nhiên. Mô hình raster chủ yếu dùng để phản ánh các đối tượng dạng vùng là ứng dụng cho các bài toán tiến hành trên các loại đối tượng dạng vùng: phân loại, chồng xếp. Các nguồn dữ liệu raster có thể bao gồm: Quét ảnh Ảnh máy bay, ảnh viễn thám Chuyển từ dữ liệu Vector sang Lưu trữ dữ liệu dạng raster. Nén theo hàng (Run lengh coding). Nén theo ngữ cảnh (Fractal). Nén theo chia nhỏ thành từng phần (Quadtree). - 5 - .Mô hình dữ liệu Vector xem các sự vật, hiện tượng là tập các thực thể không gian cơ sở và tổ hợp của chúng. Trong mô hình 2D thì các thực thể cơ sở bao gồm: điểm (point), đường (line), vùng (polygon). Các thực thể sơ đẳng được hình thành trên cơ sở vector hay tọa độ của các điểm trong một hệ trục tọa độ nào đó. Loại thực thể cơ sở được sử dụng phụ thuộc vào tỷ lệ quan sát hay mức độ khái quát. Với bản đồ có tỷ lệ nhỏ thì thành phố được biểu diễn bằng điểm (point), đường đi, sông ngòi được biểu diễn bằng đường (line). Khi tỷ lệ thay đổi kéo theo sự thay đổi về thực thể biểu diễn. Thành phố lúc này sẽ được biểu diễn bởi vùng có đường ranh giới. Khi tỷ lệ lớn hơn, thành phố có thể được biểu diễn bởi tập các thực thể tạo nên các đối tượng nhà cửa, đường sá, các trình tiện ích,… 1.3.2. Dữ liệu phi không gian Là những mô tả về đặc tính, đặc điểm và các hiện tượng xẩy ra tại vị trí địa lý xác định mà chúng khó hoặc không thể biểu thị trên bản đồ được. Hệ thống thông tin địa lý sử dụng phương pháp chung để kết hai loại dữ liệu đó thông qua bộ xác định, lưu trữ đồng thời trong các thành phần đô thị và phi đô thị. Các bộ xác định có thể đơn giản là một số duy nhất liên tục, ngẫu nhiên hoặc là các chỉ báo địa lý hay dữ liệu vị trí lưu trữ. Bộ xác định cho một thực thể có thể chứa tọa độ phân bố của nó, số hiệu mảnh bản đồ, mô tả khu vực hoặc là một con trỏ đến vị trí lưu trữ của dữ liệu liên quan. 1.4. Chức năng của hệ GIS Sức mạnh của các chức năng của hệ thống GIS khác nhau là khác nhau. Kỹ thuật xây dựng các chức năng cũng rất khác nhau. Chức năng của một hệ thống thông tin địa lý được phân chia thành năm loại như sau: Thu thập dữ liệu, thao tác dữ liệu, quản lý dữ liệu, hỏi đáp và phân tích, và hiển thị. - 6 - Nhập dữ liệu là quá trình mã hóa dữ liệu thành dạng có thể dùng trên máy tính và ghi dữ/ liệu vào cơ sở dữ liệu GIS. Nhập dữ liệu là một công việc đòi hỏi thời gian và công sức và kinh phí (giá thành xây dựng CSDL ban đầu thường là 5 -10 lần giá thành phần cứng và phần mềm). Có những trường hợp các dạng dữ liệu luôn đòi hỏi được chuyển dạng và thao tác theo một số cách để có thể tương thích với một hệ thống nhất định. Công nghệ GIS cung cấp nhiều công cụ cho các thao tác trên dữ liệu không gian và cho loại bỏ dữ liệu không cần thiết. - 7 - CHƯƠNG 2 – NGHIÊN CỨU MỘT SỐ THUẬT TOÁN PHÂN TÍCH DỮ LIỆU KHÔNG GIAN 2.1. Các thuật toán xếp chồng bản đồ Xếp chồng bản đồ là phần cốt lõi của hoạt động phân tích GIS. Nó kết hợp một số tính năng không gian để tạo ra yếu tố mới không gian. Mặt khác, xếp chồng bản đồ có thể được định nghĩa là một hoạt động không gian, kết hợp các lớp địa lý khác nhau để tạo ra lớp thông tin. Xếp chồng bản đồ được thực hiện bằng cách sử dụng số học, logic, các toán tử quan hệ và được thực hiện trong cả hai loại dữ liệu Vector và Raster. Quá trình thực hiện Overlay bản đồ qua 2 bước: Xác định tọa độ các giao điểm và tiến hành chồng khít 2 lớp bản đồ tại giao điểm này. Kết hợp dữ liệu không gian và thuộc tính của hai lớp bản đồ. 2.1.1. Các phương pháp trong xếp chồng bản đồ Phương pháp vector Overlay Trong Vector Overlay, các tính năng và thuộc tính của bản đồ được tich hợp để cho ra một bản đồ mới.Vector Overlay có thể được thực hiện trên các kiểu chức năng của bản đồ như: Điểm và đường (Point in Line), đoạn và đa giác (Line in Polygon), đa giac và đa giác (Polygon in Polygon). Phương pháp Raster Overlay Phương pháp Raster Overlay sử dụng số học và các toán tử Boolean để kết hợp các điểm ảnh hoặc giá trị tế bào trong mỗi bản đồ tạo ra một giá trị mới trong bản đồ kết hợp 2.1.2. Phép toán trong Overlay Các phép toán trong overlay bao phủ: Phép hợp (Union), phép giao (Insertect) và phép đồng nhất (Indentity). Phép hợp (Union): phép hợp hoạt động như toán tử Or. Đầu vào là hai lớp bản đồ là kiểu đa giác (polygon), đầu ra là một lớp bản đồ mới bằng cách xếp chồng hai miền dữ liệu đầu vào - 8 - và dữ liệu thuộc tính của chúng. Điều kiện: miền dữ liệu phải là polygon. Phép giao (Intersect): Phép giao hoạt động như toán tử And. Tạo ra một vùng bao mới bằng cách xếp chồng hai tập dữ liệu đầu. Kết quả đầu ra bao gồm phần dữ liệu thuộc vào cả hai tập dữ liệu đầu vào. Phép đồng nhất (Indentity): Tạo ra một vùng bao phủ mới bằng cách xếp chồng hai tập dữ liệu đầu vào. Kết quả đầu ra bao gồm toàn bộ phần dữ liệu của lớp đầu tiên và chỉ những phần nào của lớp thứ hai được chồng khít. 2.1.3. Thuật toán Bentley – Ottmann Trong hình học tính toán thuật toán Bentley – Ottmann (BO) là một thuật toán quét dòng để liệt kê tất cả các đoạn thẳng giao nhau trong mặt phẳng. Tương tự như các thuật toán khác để kiểm tra có hay không các đoạn thẳng giao nhau, với đầu vào là n đoạn thẳng và k điểm cắt nhau BO có độ phức tạp là O(n+k)logn. 2.1.4. Thuật toán giao của hai đa giác Đã có nhiều thuật toán tìm giao của hai đa giác được công bố [RIG] [JOS]. Phần lớn các thuật toán này xuất phát từ tìm giao của hai đa giác lồi. Do vậy, nếu vùng nghiên cứu đa giác bất kỳ thì chúng phải được tách ra thành đa giác lồi trước khi thực hiện thuật toán. Phát biểu bài toán: Hãy tìm phần giao của hai đa giác phẳng không tự cắt A và B. Cho biết A = a1a2…an và B = b1b2 … bm. Chi tiết thuật toán Phần giao của A và B 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 bà 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ạch 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 - 9 - 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: Bước 1: Trường hợ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 Xx = { x| x là giao điểm của cạnh v với các cạnh u  b}  {aiai+1} (nếu trong Xx 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 Xx theo chiều tằng dần về khoảng cách từ mỗi điểm đến ai, ta được Xx = {x1 = ai, x2,…,xlv = ai+1}, với |Xx|= 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. Bước 2: Trường hợ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ạnh trùng nhau. Giả sử cạnh aiai+1 và cạnh bkbk+1 song song và giao nhau (nhưng không trùng nhau). Ta xử ly như sau: Nếu ai bkbk+1 (ai nằm trong đoạn bkbk+1), thì chèn ai vào giữa bk và bk+1, tức là coi bkai và aibk+1 là hai cạnh mới của đa giác B. Xử lý tương tự cho ba đỉnh: ai+1, bk, bk+1. Sau đó, xét mỗi cặp cạnh trùng nhau v=aiai+1  A và u = bkbk+1  B (giả sử ai = bk và 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}. - 10 - Để kiểm tra xem cạng 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ất sau: 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 thỏa mãn: N I(B) và MO(A). NO(B) và MI(A). Chứng minh tính chất: Để chứng minh tính chất trên ta sử dụng 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. Xét về vị trí tương đối của M với đa giác A và của N với đa giác B ta thấy chỉ có bốn trường hợp sau: 1. NI(B) và MO(A). 2. NO(B) và MI(A). 3. NI(B) và MI(A). 4. NO(B) và MO(A). Xét trường hợp 1: Vì N I(B) chiều thuận của đa giác B là chiều đi từ bk đến bk+1 (1) Vì MO(A) Chiều thuận của đa giác A là chiều đi từ ai đến ai+1 (2). Từ (1), (2) và giả thiết aiai+1 bkbk+1 =>  một đa giác là giao của A và B nhận aiai+1 là cạnh với chiều thuận là chiều từ ai tới ai+1. Chứng minh tương tự cho trường hợp 2, ta thua được kết quả:  một đa giác là giao của A và b nhận aiai+1 là cạnh với chiều thuận là chiều từ ai+1 tới ai. Tóm lại, trong cả hai trường hợp thì aiai+1 là một cạnh của tập đa - 11 - giác giao. Bằng cách chứng minh tương tự cho hai trường hợp còn lại ( trường hợp 3 và 4) ta đều thu được kết quả: aiai+1 không phải là cạnh của tập đa giác giao. Các thuật toán liên quan. Thuật toán trình bày trên có sử dụng hai thuật toán khác nhau để cài đặt, đó là kiểm tra điểm trong đa giác và tìm giao của hai đoạn thẳng. Để kiểm tra một điểm có nằm trong đa giác hay không ta có thể sử dụng thuật toán sau: Đầu vào: Cho trước đa giác P và điểm p. Đầu ra: p nằm trong hay ngoài P. Begin if (p nằm trong cạnh P), p trong P else đếm =0 l = tia song song trục X vẽ từ p for (i=1 to n) begin if (nếu cạnh (i) cắt l) and not cạng (i) không trùng với l) then begin if (một đầu cuối của cạnh (i) nằm phía trên tia l) đếm= đếm +1 end end for if (đếm là lẻ ), p nằm trong P endif end Để tìm giao của hai đoạn thẳng ta sử dụng thuật toán biểu diễn đoạn thẳng bằng phương pháp tham số như sau: Phương trình đoạn thẳng là cạnh đa giác được xác định từ hai tọa độ đỉnh liên tiếp. Giả sử ta có tham số t thay đổi từ 0 đến 1 cho phần đoạn thẳng AB giữa hai đỉnh đa giác và có giá trị 0 tại một đầu, - 12 - giá trị 1 tại đầu kia. Vậy vố 0  t 1, ta có: x = xA + t(xB – xA) y = yA +t(yB – yA) Tương tự, cạnh CD của đa giác thứ hai sẽ được biểu diễn bởi tham số s và phương trình sau: x– xC + s(xD – xC) y– yC + s(yD – yC) (2) )3( ))(())(( ))(())(( ))(())(( ))(())(( ABDCDCAB ABACACAB ABDCDCAB ACACDCAC yyxxyyxx yyxxyyxxs yyxxyyxx yyxxyyxxt       Từ các công thức sau đây ta tính đượ giá trị của t và s. Trong đó, nếu 0 t  1 và 0 s  1 khi hai đoạn thẳng cất nhau tại một điểm và giao điểm này được tính từ (1) và (2). Phân tích và cài đặt thuật toán Trình bày tóm tắt các bước chính cài đặt chức năng xếp chồng các bản đồ trong hệ thống GIS vector. Giả sử ta phải thực hiện tính toán bao phủ của vùng địa lý được biểu diễn bởi đa giác P trong chủ đề T1 với các vùng của chủ đề T2. Bước 1. Xác định xem đa giác P của chủ đề T1 giao với các đa giác nào của chủ đề T2. Một bản đồ chủ đề chứa vô số đa giác (bản đồ hành chính Việt nam), đa giác biểu diễn xã lại có vô số cạnh. Để tăng tốc độ xử lý của máy tính ta sẽ không so sánh đa giác P của T1 với mọi đa giác của T2. Cấu trúc cơ sở dữ liệu địa lý thường lưu trữ chữ nhật bao của các đa giác. Trước khi kiểm tra hai đa giác có giao nhau hay không thì cần kiểm tra chữ nhật bao của chúng có giao nhau hay không vì hai đa giác giao nhau chỉ khi hai chữ nhật bao của chúng giao nhau. Giải pháp này làm giảm đáng kể số lần tính toán. Việc xác định chính xác hai đa giác P, Q có giao nhau hay không được thực hiện theo thuật toán sau: Đầu vào: Đa giác P, Q Đầu ra: P và Q có giao nhau? begin if (không có cạnh nào của p cắt cạnh nào đó của Q) do - 13 - begin p = điểm bất kỳ nào trên biên của P if (p nằm trong Q) P Q else begin q = điểm bất kỳ trên biên của Q if (q nằm trong Q) Q P else P và Q không giao nhau end if end if else P giao với Q end Độ phức tạp của thuật toán tìm giao các cạnh hai đa giac sẽ là O(nlogn). Bước 2. Phân lớp các đỉnh đa giác p và Q. Mỗi đỉnh đa giác được gán bởi giá trị I (trong), O (ngoài) hay B (biên) so với đa giác kia. Các giá trị này được thực hiện nhờ thuật toán điểm trong đa giác trình bày trên. Các giá trị của đỉnh được lưu vào danh sách PV cho đa giác P và QV cho đa giác Q như sau: PV = QV = Trong đó, n là tổng số đỉnh của đa giác P, m là tổng số đỉnh của đa giác Q. Bước 3. Tìm giao điểm của các cạnh đa giác P và Q. Giao của các cạnh đa giác được tính theo công thức (3) ở trên. Phải xét lần lượt các cạnh của P có cắt các cạnh của Q hau không. Nếu cí điểm cắt thì xen chúng vào danh sách PV và QV với giá trị B (biên). Kết quả cho lại các cạnh của đa giác được chia thành đoạn nhỏ. Mỗi đoạn của đa giác này sẽ nằm toàn bộ trong hay toàn bộ ngoài đa giác kia. Ta có thể sử dụng tính chất mô tả ở phần trên để xác định - 14 - các đoạn thẳng nằm trong hay ngoài đa giác: nếu điểm giữa đoạn thẳng nằm trong hay nằm ngoài đa giác thì đoạn thẳng đó sẽ nằm trong hay nằm ngoài đa giác.