Luận án Nghiên cứu công nghệ thành lập và ứng dụng bản đồ số địa chính trong điều kiện Việt Nam

40 
sau, phải trước, phải sau, mặt trái, mặt phải. Các cạnh đều phải xác định 
hướng. 
Bảng 2.2. Bảng dữ liệu thửa đất cấu trúc Winged-edge Topology 
Cạnh Trái 
trước 
Trái 
sau 
Phải 
trước 
Phải 
sau 
Thửa 
trái 
Thửa 
phải Thửa 
Cạnh 
đầu 
e1 e7 -e2 -e3 e5 f1 f2 f1 e1 
e2 e1 e6 f1 f2 e5 
e3 e4 -e1 f2 
e4 e5 -e3 f2 
e5 -e1 e4 f2 
e6 -e2 e7 f1 
e7 e6 e1 f1 
e2 
f1 
Hình 2.5. Hai thửa đất kề nhau 
f2 
e3 
e4 
e5 e7 
e6 
e1 
Phải trước Trái sau 
Trái trước Phải sau 
Mặt trái Mặt phải 
Hình 2.4. Mô hình cấu trúc Winged-edge Topology 
41 
 Đặc điểm của cấu trúc này lưu trữ các cạnh theo hướng do đó việc xác 
định hướng của cạnh thửa cần đặc biệt quan tâm, từ đó mới xác định được các 
cạnh trái trước, trái sau, phải trước, phải sau. 
 Ưu điểm: Khối lượng lưu trữ dữ liệu nhỏ do không dư thừa dữ liệu, 
mỗi cạnh liên kết với bốn cạnh khác. 
 Nhược điểm: Nhìn vào bảng 2.2 cho thấy cách lưu trữ này tương đối 
phức tạp, phải tạo mô hình Topo trước thì mới xây dựng được cấu trúc dữ 
liệu. 
2.4.2.2. Cấu trúc dữ liệu Doubly Connected Edge List (DCEL) 
 DCEL là cấu trúc dữ liệu danh sách cạnh liên kết kép quản lý bản vẽ và 
mối quan hệ Topo giữa các thửa đất (Hình 2.6). Mỗi cạnh thửa đất được quản 
lý bởi hai nửa cạnh có hướng ngược nhau và nửa cạnh này là nửa cạnh đảo 
của nửa cạnh kia. DCEL quản lý dữ liệu bởi 3 bảng: Bảng danh sách đỉnh; 
bảng danh sách nửa cạnh và bảng danh sách vùng. 
 - Bảng danh sách đỉnh (Bảng 2.3): Số hiệu đỉnh (số nguyên), tọa độ X 
(số thực), tọa độ Y (số thực), số hiệu nửa cạnh gắn liền với đỉnh (số nguyên) 
v1 v2 v3 
v4 
Hình 2.6. Mô hình cấu trúc danh sách cạnh liên kết kép 
v6 
e1 
e'1 
e2 
e'2 
e4 
e'4 
e5 
e'5 
e3 
e'3 
a1 
a2 
v5 
a3 
42 
Bảng 2.3. Bảng danh sách đỉnh 
Đỉnh Tọa độ X Tọa độ Y Nửa cạnh gắn liền với đỉnh 
v1 X1 Y1 e1 
v2 X2 Y2 e2 
v3 X3 Y3 e'2 
v4 X4 Y4 e4 
v5 X5 Y5 e3 
v6 X6 Y6 e'5 
 - Bảng danh sách nửa cạnh (Bảng 2.4): Số hiệu nửa cạnh (số nguyên), 
số hiệu đỉnh gốc (số nguyên), số hiệu nửa cạnh đảo (số nguyên), số hiệu nửa 
cạnh trước (số nguyên), số hiệu nửa cạnh sau (số nguyên), số hiệu vùng bên 
phải của nửa cạnh (số nguyên). Ngoài ra còn có thể có cờ báo hiệu đưa nó vào 
lịch sử để lưu trữ (lô gíc) trong trường hợp cập nhật biến động đất đai. 
Bảng 2.4. Bảng danh sách nửa cạnh 
Nửa 
cạnh 
Đỉnh 
gốc 
Nửa 
cạnh 
đảo 
Vùng 
phải 
Nửa 
cạnh 
sau 
Nửa 
cạnh 
trước 
e3 v5 e'3 a2 e2 e4 
e'3 v2 e3 a1 e5 e1 
... 
 - Bảng danh sách vùng (Bảng 2.5): Số hiệu vùng (số nguyên), số hiệu 
nửa cạnh đường bao (số nguyên), danh sách số hiệu nửa cạnh của các vùng 
đảo tương ứng. 
43 
Bảng 2.5. Bảng danh sách vùng 
Vùng 
Danh sách 
nửa cạnh 
vùng bao 
Danh sách 
nửa cạnh 
vùng đảo 
a1 e1 Nil 
a2 e2 Nil 
a3 e'1 e1, e2 
... 
 Ưu điểm: cấu trúc dữ liệu đơn giản, dễ quản lý, có thể tạo ngay được 
cấu trúc dữ liệu DCEL chính mà chưa cần tạo mô hình Topo, chỉ cần dựa vào 
mối quan hệ không gian giữa các nửa cạnh. 
 Nhược điểm: mô hình này có nhược điểm là dung lượng lưu trữ lớn.. 
2.4.2.3. Cấu trúc dữ liệu Link-Node 
 Cấu trúc dữ liệu Link-Node là cấu trúc liên kết các điểm (Hình 2.7). 
 + Link là chuỗi các đoạn không cắt nhau có cùng những thuộc tính 
chung và không cắt các link khác trừ điểm đầu và điểm cuối. 
 + Node: là điểm đầu hoặc điểm cuối của Link, một Node có thể là điểm 
chung của nhiều Link. 
 Các tọa độ của Node được lưu vào một file riêng biệt, nó có thể được 
tham chiếu tới các Link khác qua điểm đầu và điểm cuối của Link đó. 
10 15 27 
17 
Hình 2.7. Mô hình cấu trúc dữ liệu Link-Node 
23 
100 
101 
152 1 
2 
21 
0 
16 
19 
151 
153 154 
3 
44 
Bảng 2.6. Bảng lưu trữ Nodes 
STT 
bản ghi 
Số hiệu 
Node X Y Links 
1 15 X15 Y15 100,101,152 
2 16 X16 Y16 101, 154, 153 
3 19 X19 Y19 151, 153, 154 
4 21 X21 Y21 100,152,151 
... 
Bảng 2.7. Bảng lưu trữ Links 
STT 
bản 
ghi 
Links 
Vùng Node 
Số 
điểm Tọa độ Trái Phải Từ Đến 
1 100 0 1 21 15 2 X23, Y23, X10,Y10 
2 101 0 2 15 16 0 
3 151 0 2 19 21 0 
4 152 2 1 15 21 0 
5 153 3 2 16 19 0 
6 154 0 3 16 19 2 X27, Y27, X17,Y17 
... 
Bảng 2.8. Bảng lưu trữ vùng 
STT bản ghi Số hiệu vùng 
1 0 
2 1 
3 2 
... ... 
 Ưu điểm của cấu trúc dữ liệu Link-Node là dung lượng lưu trữ ít hơn, 
thay các đoạn liền kề chung của hai vùng bằng các Link, ít dư thừa dữ liệu. 
 Nhược điểm lưu trữ tương đối phức tạp, cần xác định chính xác các 
Nodes, các Links ngoài ra trên mỗi Link cần quản lý danh sách tọa độ các 
45 
điểm trong Link, cần phải tạo mô hình Topo trước mới tạo được cấu trúc dữ 
liệu. 
 Qua nghiên cứu các mô hình dữ liệu cho thấy, các mô hình Topo đều 
thuận lợi cho việc quản lý mô hình Topo thửa đất, tuy nhiên cấu trúc dữ liệu 
DCEL quản lý các nửa cạnh độc lập là cấu trúc đơn giản, dễ hiểu, nên dễ xử 
lý. Chính vì vậy, trong nghiên cứu của luận án, chọn mô hình Topo với cấu 
trúc dữ liệu DCEL để nghiên cứu. 
 Tuy vậy, làm thế nào để khi biên tập thửa đất phải phát sinh dữ liệu để 
bảo toàn cấu trúc như trên, khi cập nhật biến động đất đai không làm phá vỡ 
mối quan hệ Topo của thửa đất. Ngoài ra, quá trình cập nhật bản đồ địa 
chính với nhiều đơn vị cập nhật khác nhau vào bản đồ tổng thể lưu trữ trong 
hệ thống quản lý. Vậy cần xử lý như thế nào để không bị xung đột và có thể 
cập nhật được các dữ liệu đã được biên tập lên toàn hệ thống. Chương sau sẽ 
nghiên cứu sử dụng cấu trúc dữ liệu DCEL trong công nghệ thành lập và ứng 
dụng bản đồ số địa chính. 
46 
CHƯƠNG 3. SỬ DỤNG CẤU TRÚC DỮ LIỆU DCEL 
TRONG THÀNH LẬP VÀ ỨNG DỤNG BẢN ĐỒ SỐ ĐỊA CHÍNH 
 Thuật toán tạo mô hình Topo đã được nghiên cứu trong [12], [13]. Các 
thuật toán tạo mô hình Topo đã được ứng dụng trong các mô đun phần mềm 
như Picklot, Famis, TMV-Map, AcadMap, ArcTopo ... 
 Mô hình Topo DCEL được trình bày chi tiết trong [33], các mô hình 
Topo khác được mô tả trong các tài liệu [34] và [39]. Để thể hiện mối quan hệ 
Topo của các thửa đất hiện nay, chuẩn dữ liệu địa chính (Bộ Tài nguyên và 
Môi trường (2010)-điều 9)[3] đã quy định chuẩn định dạng dữ liệu và siêu dữ 
liệu theo ngôn ngữ định dạng GML, XML với cơ sở là cấu trúc dữ liệu 
DCEL. 
 Các phần mềm biên tập bản đồ địa chính ở Việt Nam hiện nay hầu hết 
chỉ tập trung tạo mô hình Topo mà chưa chú trọng đến việc lưu trữ mối quan 
hệ Topo của các vùng. Chính vì vậy, mỗi khi có sự biến động về thông tin 
không gian của vùng cần phải xây dựng lại mô hình Topo. Quá trình này vừa 
tốn thời gian, vừa mất đi các thông tin thuộc tính của các vùng đã có. Sau khi 
tạo lại Topo người sử dụng phải gắn thêm các dữ liệu thuộc tính cho các vùng 
phát sinh và việc này thường khó kiểm soát bởi các vùng biến động có thể ở 
nhiều nơi trên bản vẽ. Chính vì vậy, người sử dụng thông thường gán lại toàn 
bộ cơ sở dữ liệu thuộc tính trên bản vẽ khi có bất kỳ một biến động nào về 
vùng dù chỉ những thay đổi nhỏ. Đây là một trong những công việc tốn thời 
gian và dễ nhầm lẫn, bỏ sót trong công tác nội nghiệp. 
 Để giải quyết vấn đề này, cần phải xây dựng một hệ thống biên tập 
chuyên dụng với một mô hình cấu trúc dữ liệu Topo phù hợp đồng thời có các 
giải pháp để quản lý cơ sở dữ liệu khi có biến động về vùng mà vẫn đảm bảo 
mối quan hệ Topo giữa các vùng. Với cấu trúc dữ liệu lựa chọn là cấu trúc 
DCEL một số vấn đề quan trọng trong công tác thành lập và ứng dụng bản đồ 
47 
số như tạo mô hình Topo, biên tập thửa đất, chồng phủ các vùng cần có 
những giải pháp, thuật toán cụ thể để thực hiện. 
 Trước hết cần nghiên cứu một số thuật toán cơ sở sẽ áp dụng trong việc 
sử dụng cấu trúc DCEL thành lập và ứng dụng bản đồ số địa chính. 
3.1. Một số thuật toán cơ sở 
3.1.1. Sắp xếp và tìm kiếm 
3.1.1.1. Sắp xếp nhanh 
 Trong các thuật toán sắp xếp chúng ta cần quan tâm đặc biệt đến những 
thuật toán có độ phức tạp O(nlogn) như QuickSort (sắp xếp nhanh), HeapSort 
(sắp xếp vun đống), MergeSort (sắp xếp trộn),... Trong số các thuật toán đã 
biết, QuickSort là thuật toán có tốc độ trung bình nhanh hơn cả, do đó nếu sử 
dụng QuickSort trong các bài toán đòi hỏi sắp sếp một số lượng lớn các đối 
tượng sẽ làm tăng đáng kể hiệu suất của chương trình. So với một số thuật 
toán sắp xếp khác như sắp xếp vun đống, sắp xếp trộn, ... độ ổn định của thuật 
toán QuickSort không cao. Vì vậy từ các nghiên cứu lý thuyết của QuickSort, 
khi sử dụng phải chủ động tránh các tình huống xấu hoặc trong trường hợp 
cần thiết biến đổi dữ liệu cho thích hợp với thuật toán. 
 QuickSort là thuật toán được A.R. Hoare phát minh vào năm 1960. Các 
ưu điểm của thuật toán Quick Sort là chỉ sử dụng một ngăn xếp phụ nhỏ, chỉ 
cần khoảng trung bình O(nlogn) thao tác để sắp n phần tử, và có một vòng lặp 
"trong" ngắn. 
 QuickSort thuộc loại "chia để trị" (divide and conquer). Nó thực hiện 
bằng cách phân hoạch một tập tin thành hai phần, sau đó sắp xếp các phần 
riêng biệt. Giả sử mảng cần sắp xếp là a(n), khi đó thuật toán QuickSort được 
thực hiện theo trình tự sau: [27] 
 Hàm QuickSort (l, r) 
 i = Phanhoach (l, r) 
48 
 QuickSort (l, i-1); QuickSort (i+1, r) 
 Kết thúc hàm 
 Tham số l và r không giới hạn các tập tin con trong tập tin gốc cần sắp 
xếp; nếu gọi QuickSort(1,N) sẽ sắp toàn bộ tập tin. 
 Thủ tục "Phanhoach" sẽ tổ chức lại mảng thỏa mãn ba điều kiện sau: 
 - Phần tử a(i) đặt ở vị trí cuối cùng trong mảng với i nào đó. 
 - Tất cả các phần tử trong a(l), ..., a(i-1) nhỏ hơn hay bằng a(i). 
 - Tất cả các phần tử trong a(i+1), ..., a(r) lớn hơn hay bằng a(i). 
 Đầu tiên chọn tùy ý a(r) là phần tử sẽ rơi vào vị trí đặt cuối cùng. Kế 
tiếp, quét từ trái của mảng cho đến khi gặp một phần tử lớn hơn a(r), và quét 
từ đầu phải cho đến khi gặp một phần tử nhỏ hơn a(r). Hai phần tử dừng việc 
quét dĩ nhiên không đúng vị trí trong mảng được phân hoạch cuối cùng nên 
phải hoán vị chúng (thực ra tốt nhất nên ngừng việc quét đối với những phần 
tử bằng a(r), dù là có thể đi vào một số hoán vị không cần thiết). Tiếp theo 
bảo đảm là tất cả các phần tử trên mảng ở bên trái con trỏ phải lớn hơn a(r). 
Khi các con trỏ giao nhau, quá trình phân hoạch gần như hoàn tất, còn lại là 
hoán vị a(r) với phần tử trái nhất của tệp tin con bên phải (phần tử do con trỏ 
trái trỏ đến). 
 Kết thúc sắp xếp bằng cách sắp xếp hai tệp tin ở mỗi phía của thuật 
toán phân hoạch nhờ dùng vào đệ quy. 
3.1.1.2. Tìm kiếm nhị phân 
Tìm kiếm nhị phân cũng dựa trên nguyên tắc "chia để trị": chia mảng 
thành hai phần, xác định xem phần nào chứa khóa, kế đến tiếp tục quá trình 
cho phần chứa khóa. Sở dĩ chúng ta có thể chia đôi và chỉ tiếp tục tìm trên 
một nửa mảng là nhờ vào giả thiết mảng đã được sắp xếp theo thứ tự khóa. 
Có thể giả sử mảng được sắp xếp tăng, trường hợp sắp xếp giảm thì tương tự. 
Để tìm khóa v có trong mảng hay không, trước tiên ta so sánh nó với phần tử 
49 
ở vị trí giữa của mảng, nếu v nhỏ hơn thì nó chỉ có thể ở trong một nửa đầu 
tiên của mảng; nếu v lớn hơn thì nó chỉ có thể ở trong một nửa còn lại của 
mảng. Kế đến áp dụng đệ quy phương pháp này. Bởi vì chỉ gọi đệ quy một 
lần, chúng ta có thể dùng phương pháp lặp. 
Giả sử mảng a đã được sắp xếp tăng theo thứ tự khóa, chúng ta có thể 
cài đặt hàm tìm kiếm nhị phân BinarySearch như sau:[27] 
Hàm BinarySearch(v) 
L = 1; R = N ; X = (L + R) / 2 
Làm tới khi (v = X) 
nếu v > X thì L = X 
nếu v < X thì R = X 
Lặp 
Kết thúc hàm 
3.1.2. Xác định điểm nằm ở phía nào của đoạn thẳng 
Đoạn thẳng được xem như một vectơ có chiều từ đầu mút thứ nhất đến 
đầu mút thứ hai. Khi giải quyết bài toán này, chúng ta cần chú ý đến các 
trường hợp ba điểm thẳng hàng. Theo cách giải quyết trong [27], hàm ccw có 
ba giá trị 1, -1 và 0, trong đó 1: điểm xét ở bên trái, -1 :điểm xét ở bên phải. 
Khi ba điểm thẳng hàng, 1: đầu mút thứ hai nằm giữa, -1: đầu mút thứ nhất 
nằm giữa, 0: điểm xét nằm trong đoạn thẳng. Hàm này được xây dựng trên cơ 
sở xét dấu của tích có hướng hai vectơ, vectơ thứ nhất là bản thân đoạn thẳng, 
vectơ thứ hai nối từ điểm thứ hai đến điểm xét. 
Gọi hai đầu mút của đoạn thẳng là P1(X1,Y1), P2(X2,Y2); điểm xét là 
P(X,Y), ta có: 
Hàm ccw(P1, P2, P) 
Nếu (X2- X1) (Y2- Y) - (Y2- Y1) (X2- X) > 0 thì ccw = 1 
Nếu (X2- X1) (Y2- Y) - (Y2- Y1) (X2- X) < 0 thì ccw = -1 
50 
Còn nếu (X2- X1) (Y2- Y) - (Y2- Y1) (X2- X) = 0 thì 
Nếu (X2- X1) (X2- X) < 0 hoặc (Y2- Y1) (Y2- Y) < 0 thì 
ccw = -1, 
Ngược lại thì 
Nếu (X2- X1)2 + (Y2- Y1)2 (X2- X)2 + (Y2- Y)2 thì 
ccw = 0 
Ngược lại thì 
ccw = 1 
Kết thúc hàm 
3.1.3. Kiểm tra giao của hai đoạn thẳng 
Trong mối quan hệ giữa hai đoạn thẳng, trường hợp thường gặp nhất là 
bài toán xác định giao điểm. Tuy nhiên đôi khi chúng ta chỉ muốn biết chúng 
có thực sự giao nhau hay không mà không cần xác định điểm giao. Trong 
trường hợp này, chúng ta chỉ cần kiểm tra điều kiện: hai đầu mút của đoạn 
thẳng này phải nằm ở hai phía so với đoạn thẳng kia và ngược lại, khi đó hàm 
ccw của hai đầu mút này sẽ có dấu ngược nhau [27]. 
Gọi P1, P2 là hai đầu mút của đoạn thẳng thứ nhất; P3, P4 là hai đầu mút 
của đoạn thẳng thứ hai, điều kiện để hai đoạn thẳng này giao nhau sẽ là: 
Hàm InterSect(P1, P2, P3, P4) 
Nếu ccw(P1, P2, P3).ccw(P1, P2, P4) 0 và 
ccw(P3, P4, P1).ccw(P3, P4, P2) 0 thì InterSect có giao 
Kết thúc hàm 
3.1.4. Kiểm tra điểm nằm trong đa giác 
Bài toán này nhằm xác định xem một điểm có nằm trong miền một đa 
giác khép kín hay không. Bài toán Điểm nằm trong đa giác có nhiều ứng 
dụng trong thực tiễn. Đây là bài toán cần được giải quyết cho hầu hết các 
phần mềm đồ họa. Bài toán này sẽ được mở rộng để giải quyết các bài toán 
51 
phức tạp hơn như đoạn nằm trong một đa giác, miền nằm trong một đa giác 
[27]. 
Có thể liệt kê một số ứng dụng của các bài toán này: 
- Phục vụ cho thao tác chọn đối tượng theo vùng 
- Lọc các điểm ngoài biên trong xây dựng mô hình số độ cao 
- Phục vụ cho việc xử lý, phân tích các miền 
Như vậy, đầu vào của bài toán này sẽ là một điểm và một đường đa 
giác khép kín cho trước, còn đầu ra là câu trả lời "có" nếu điểm nằm trong, 
hoặc "không" nếu điểm nằm ngoài vùng có biên là đa giác nói trên. 
Giải pháp để giải quyết bài toán như sau: 
- Xác định số lượng các giao điểm của một nửa đường thẳng bất kỳ 
xuất phát từ điểm xét với đa giác nêu trên. 
 - Nếu số này là lẻ thì điểm xét sẽ nằm trong đa giác 
 - Còn nếu là chẵn thì điểm xét nằm ngoài. 
Thông thường, nên lấy nửa đường thẳng này song song với một trục tọa 
độ. 
Tuy nhiên cần phải xét các trường hợp biên: 
- Nửa đường thẳng đi qua một trong số các đỉnh của đa giác 
- Một trong số các đoạn của đa giác trùng với một phần của nửa đường 
thẳng này. 
Ta có thể thay thế nửa đường thẳng này bằng một đoạn thẳng song 
song với trục hoành, được gọi là đoạn thẳng kiểm tra với đầu mút thứ nhất là 
điểm xét, còn đầu mút thứ hai phải nằm ngoài đa giác bằng cách lấy điểm thứ 
hai có tọa độ X lớn hơn tọa độ X lớn nhất trong số các đỉnh của đa giác. Việc 
loại bỏ các trường hợp biên được thực hiện bằng cách bỏ qua khi đỉnh đa giác 
rơi trên đoạn thẳng kiểm tra, tức là không tăng biến đếm giao khi gặp các 
trường hợp này. 
52 
Trong trường hợp đa giác lồi, tình hình sẽ đơn giản hơn nếu ta sử dụng 
tính chất không bao giờ có hơn 2 giao điểm với đoạn thẳng kiểm tra. 
Thuật toán hàm Điểm nằm trong đa giác 
Hàm PntInPolygon 
Tạo đoạn thẳng kiểm tra e 
Cho i = 1 tới n+1 
Nếu (ei,i+1 giao e) thì k = k+1 
Tăng tiếp i 
Nếu k chẵn thì điểm nằm ngoài 
còn nếu k lẻ thì điểm nằm trong 
Kết thúc hàm 
Trong trường hợp khi đa giác là một hình chữ nhật bài toán trên sẽ trở 
nên đơn giản hơn nữa. Lúc đó điều kiện để điểm nằm trong hình chữ nhật là:
maxmin XXX , maxmin YYY ; với Xmin, Ymin, Xmax, Ymax là các giá trị tọa 
độ cực trị của các đỉnh hình chữ nhật. 
3.1.5. Phân hoạch không gian đối tượng 
 Khi tổ chức một CSDL, người ta thường sắp xếp chúng theo một cách 
nào đó để thuận tiện cho việc tìm kiếm dữ liệu khi cần thiết. Việc này cũng 
tương tự việc tổ chức sắp xếp các từ trong một cuốn từ điển theo thứ tự ABC 
để thuận tiện cho việc tra cứu. Một ví dụ khác là việc sắp xếp các cuốn sách 
trong thư viện theo thứ tự của tên các tác giả hoặc sắp xếp theo chủ đề để 
người thủ thư có thể dễ dàng tìm thấy cuốn sách theo yêu cầu của người đọc. 
Việc sắp xếp dữ liệu theo thứ tự như vậy đòi hỏi một số phí tổn về thời gian 
và nguồn lực ban đầu, tuy nhiên việc tìm kiếm chúng sẽ được thực hiện nhanh 
chóng hơn nhiều. Đối với các loại dữ liệu khác nhau sẽ tương ứng với cách 
sắp xếp phù hợp khác nhau. Phân hoạch không gian là thuật ngữ để chỉ việc 
sắp xếp các đối tượng đồ họa theo đặc điểm vị trí của chúng trong không gian 
53 
với mục đích tương tự. Thông thường, việc tìm kiếm các đối tượng đồ họa 
được tìm kiếm theo một vùng phẳng nào đó. Trong các ứng dụng thực tế, 
vùng tìm kiếm được giới hạn bởi một hình chữ nhật là trường hợp thường gặp 
nhất[11]. 
 Để thuận tiện cho việc phân hoạch, tạo một mảng Quad(), trong đó mỗi 
phần tử của mảng này là một cấu trúc có các thuộc tính như sau 
 - RECT - hình chữ nhật của Quad 
 - Id() - mảng các chỉ số các phần tử đồ họa thuộc Quad 
 Hình chữ nhật ban đầu để khởi tạo việc phân chia các đối tượng đồ họa 
của bản vẽ phải chứa tất cả các phần tử. Có thể lấy hình chữ nhật Extent 
(Hình chữ nhật bao khít tất cả các đối tượng có trong bản vẽ) để sử dụng cho 
mục đích này và là Quad khởi điểm ("Quad mẹ") trong mảng, gọi là Quad0. 
 Xuất phát từ Quad0, chia hình chữ nhật RECT thành 4 hình chữ nhật 
con, sẽ thu được 4 "Quad con" tương ứng. 
 Lần lượt xét từng phần tử đồ họa, kiểm tra xem phần tử đó nằm trong 
hình chữ nhật của các Quad con vừa tạo không, nếu có chuyển chỉ số của 
phần tử này trong Quad mẹ sang mảng chỉ số phần tử của Quad con. Các phần 
tử đồ họa còn lại trong Quad mẹ là các phần tử có giao với các đường phân 
chia giữa các Quad con. Trong trường hợp các phần tử đồ họa chỉ là các điểm, 
trong Quad mẹ sẽ không còn phần tử nào. 
 Quá trình phân hoạch tiếp tục được thực hiện đệ quy và điều kiện để 
dừng quá trình đệ quy là Nmin - số phần tử nhỏ nhất có trong Quad. Một điều 
kiện khác có thể sử dụng làm tiêu chuẩn để dừng quá trình phân hoạch là 
Ntg_max - số tầng lớn nhất của cây tứ phân hoặc Nquad_max - số Quad lớn nhất. 
 Trong một phần mềm đồ họa, phân hoạch không gian có thể được sử 
dụng cho nhiều trường hợp khác nhau như khi thực hiện thao tác thu phóng, 
trượt bản vẽ, trong phạm vi cửa sổ màn hình chỉ có một số đối tượng được 
54 
hiển thị. Để tăng tốc độ, cần có biện pháp loại bỏ việc ánh xạ các đối tượng 
nằm ngoài cửa sổ màn hình. Một trong những biện pháp hiệu quả là phân 
hoạch các đối tượng trong mặt chiếu ảo dưới dạng cây tứ phân. Khi hiển thị, 
chỉ cần chú ý đến các phần tử thuộc các vùng Quad có giao với cửa sổ màn 
hình để vẽ. 
 Cũng như màn hình, việc xuất các đối tượng ra các thiết bị ngoại vi 
khác như máy in, máy vẽ, có thể tăng tốc độ thực hiện bằng các biện pháp 
tương tự. 
 Trong nhiều trường hợp, cần phải thực hiện việc chọn, tìm kiếm các đối 
tượng theo một chỉ tiêu chỉ vị trí nào đó. Khi vùng chọn là một hình chữ nhật, 
chỉ xét những đối tượng trong những Quad có giao với hình chữ nhật này 
cũng theo cách tương tự. 
3.1.6. Tính diện tích đại số một đa giác 
 Một đa giác có n đỉnh, mối đỉnh có tọa độ (xi, yi). Diện tích đại số của 
đa giác S được tính theo công thức cơ bản: 
 
n
1i
1i1ii yyx2
1S với yn+1 = y1; y0 = yn 
 Diện tích đại số cho giá trị có dấu, nếu tính theo chiều kim đồng hồ sẽ 
có dấu dương, tính ngược chiều kim đồng hồ có dấu âm. 
3.1.7. Xác định góc hợp bởi phương thẳng đứng với đoạn thẳng 
 Một đoạn thẳng AB nối hai điểm A (xA, yA) và B (xB, yB). Góc α hợp 
bởi phương thẳng đứng từ A tới đoạn thẳng AB theo chiều kim đồng hồ được 
tính như sau: 
 Đặt  x = xB - xA;  y = yB - yA; atn(x) là giá trị arctan của x 
 π = 3.14159265358979 là hằng số 
 Nếu y = 0 và x > 0 thì α = π/2 
 Nếu y = 0 và x < 0 thì α = 3π/2 
55 
 Nếu y > 0 thì