ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HOA

MỘT SỐ KIỂU DỮ LIỆU TRỪU TƯỢNG
ỨNG DỤNG TRONG HÌNH HỌC TÍNH TỐN

LUẬN VĂN THẠC SĨ

Hà Nội – 2011


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HOA

MỘT SỐ KIỂU DỮ LIỆU TRỪU TƯỢNG
ỨNG DỤNG TRONG HÌNH HỌC TÍNH TỐN
Ngành

: Cơng nghệ Thơng tin

Chun ngành : Hệ thống Thông tin
Mã số

: 60 48 05

LUẬN VĂN THẠC SĨ


2.3.2 Multi-level partition trees ........................................................... 57
2.3.3 Cutting trees ............................................................................... 60
2.4 Kết luận ............................................................................................... 66
Chương 3 - CÀI ĐẶT VÀ ĐÁNH GIÁ.......................................................... 68
3.1 Cài đặt Kd-trees ................................................................................. 68
3.2 Cài đặt Range trees ............................................................................ 70
3.3 Cài đặt Interval trees .......................................................................... 72
3.4 Cài đặt Segment trees ......................................................................... 74
3.5 Kết luận ............................................................................................... 76
KẾT LUẬN ..................................................................................................... 77
TÀI LIỆU THAM KHẢO.............................................................................. 78


2

DANH SÁCH THUẬT NGỮ VÀ GIẢI THÍCH
Số
1

Thuật ngữ
Canonical subset

Giải thích
Tập con chính qui
chiều

2

-Dimensional Kd-trees


Priority search trees

Cây tìm kiếm ưu tiên

8

Range queries

Truy vấn phạm vi

9

Range trees

Cây phạm vi

10

Segment trees

Cây quản lí đoạn thẳng

11

Stabbing queries

Truy vấn stabbing

12


16

Hình 2.1

Giải thíchtruy vấncơ sở dữ liệu một cách hình

18

Hình 2.2

Truy vấn phạm vi một chiều trong cây nhị phân tìm kiếm

20

Hình 2.3

Kd-trees: mặt phẳng được chia và cây nhị phân

23

Hình 2.4

Các nútcủa kd-trees vàvùngmặt phẳng

24

Hình 2.5

Truy vấn trên kd-trees hai chiều


36

Hình 2.11

Phân loại các đoạn thẳng liên quan với

38

Hình 2.12

Interval trees

39

Hình 2.13

Các đoạn thẳngcắt bởi qcóđiểm đầu mút trái

40

Hình 2.14

Heap của tập hợp {1,3,4,8,11,15,21,22,36}

42

Hình 2.15

Một tập hợp các điểm và cây tìm kiếm ưu tiên tương ứng


53

Hình 2.22

Một phân vùng đơn hình tốt

54

Hình 2.23

Phân vùng mặt phẳng đơn hình và cây tương ứng

54

Hình 2.19

9

và

47

49


4
Số

Tên hình


63

Hình 3.1

Sơ đồ các lớp trong thực hiện Kd-trees

68

Hình 3.2

Sơ đồ các lớp trong thực hiện Range trees

70

Hình 3.3

Sơ đồ các lớp trong thực hiện Interval trees

72

Hình 3.4

Sơ đồ các lớp trong thực hiện Segment trees

74


5

MỞ ĐẦU

giá hiệu suất của thuật toán và chương trình.


6

Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TỐN
1.1 Các bài tốn của hình học tính tốn
Hình họctính tốnlà mộtchun ngành củakhoa họcmáy tínhnghiên
cứucácthuật tốncó nội dung hình học. Một sốbài tốnhình họcphát sinh hồn
tồntừviệc nghiên cứu cácthuật tốnhình học tính tốnvà cácbài tốnnàycũng
đượcxemlà một phần củahình học tính tốn. Hình học tính tốn nghiên cứusự
phức tạpcủa cácbài tốnhình học, xây dựngcấu trúc dữ liệuđểlưu trữcác loại dữ
liệuhình học, thiết kếthuật tốncho cácbài tốnhình học và khám phácác tính
chấthình học. Những vấn đề cốt lõi trong hình học tính tốn có thể được chia với
nhiều cách khác nhau, theo nhiều tiêu chí khác nhau. Ở đây, có thể phân loại các
bài tốntrong hình học tính tốn thành các lớp bài toán như dưới đây[1].
1.1.1 Bài toán tĩnh
Trong cácbài toántĩnhcho trướcđầu vàovàđầu ratương ứngcần phải
đượcxây dựng hoặcđược tìm thấy.Một sốbài toáncơ bảncủa loại nàylà:
Convex Hull: Cho tập hợp các điểm và yêu cầu tìm đa giác lồi nhỏ nhất
chứa tất cả các điểm đó.
Line segment intersection: Cho tập hợp các đoạn thẳng và yêu cầu tìm
điểm cắt nhau giữa các đoạn thẳng trongtập hợp cho trước.
Polygon cutting: Chia đa giác thành các dạng hình học khác với tổng
chiều dài được chia là nhỏ nhất.
Delaunay triangulation.
Voronoi diagram: Cho tập hợp các điểm và u cầu tìm phân vùng khơng
gian theo các điểm đóng.
Linear programming.
Closest pair of points: Cho tập hợp các điểm và u cầutìm cặp điểm có

vớiđiểmtruy vấn một cách hiệu quả.
Raytracing: Cho tập hợp các đối tượngtrong không gian và yêu cầu tạo
racấu trúcdữ liệuhiệu quảchođối tượngcó tiatruy vấncắtđầu tiên.
Nếu khơng gian tìm kiếm là cố định, độ phức tạp tính tốn cho bài tốn
truy vấn hình họcđược ước tính bởi thời gian và không gian cần thiết để xây
dựng các cấu trúc dữ liệu tìm kiếm và thời gian trả lời các truy vấn.
1.1.4Các biến thể
Một số bài tốncó thểđược xem làthuộcmột trong cácloại trên,tùy
thuộcvào bối cảnh.Chẳng hạn xét bài toán: Point in polygon – Xác định một
điểm nằm trong hay nằm ngoài đa giác cho trước.Trong một vài tình huống của
bài tốn truy vấn có thể kỳ vọng hợp lí vào thứ tự các truy vấn, hoặc có thể được


8
khai thác với cấu trúc dữ liệu hiệu quả hoặc ước tính độ phức tạp chặt chẽ hơn.

1.2 Các đối tượng hình học
Máy tính ngày càng được sử dụng nhiều hơn để giải quyết các bài tốn có
quy mơ lớn về hình học. Các đối tượng hình học cơ bản như điểm, đoạn thẳng
và đa giác là nguồn gốc của tập đáng kể các bài toán và thuật toán.
1.2.1 Điểm
Trong không gian hai chiều, đối tượng cơ sở là điểm được biểu diễn bởi
một cặp số nguyên – tọa độ của điểm đó trong hệ trục tọa độ Descart. Một điểm
trong mặt phẳng có tọa độ và tọa độ , kí hiệu
[13].
1.2.2 Đoạn thẳng
Một tổ hợp lồi của hai điểm phân biệt
một điểm bất kỳ

sao cho

, với

. Đoạn thẳng có hướng
, kí hiệu

là

[13].

1.2.3 Vectơ
Vectơ là một đoạn thẳng có hướng. Vectơ có điểm đầu
được kí hiệu

và điểm cuối ,

. Khi không cần chỉ rõ điểm đầu, điểm cuối ta kí hiệu

Tọa độ của vectơ là

=

với

;

[13].
.

1.3 Một số bài tốn hình học và thuật tốn
1.3.1 Bài toán xác định cặp đoạn thẳng bất kỳ cắt nhau


tại , kí hiệu

và giao điểm của

.
e
g

b

i

c

h
t

với đường thẳng

với cùng đường thẳng qt đó thì ta nói

d

a

r

nếu đường thẳng qt


và

,

không so sánh được với các đoạn thẳng
giao nhau,

đường thẳng quét đi qua vùng bóng mờ đều có
quan hệ thứ tự

,

và

nhưng

; mọi

nằm liên tiếp nhau trong

, hình 1.1b.

Khi di chuyển đường thẳng quét, thuật toán thường phải quản lí hai tập
hợp dữ liệu sau:
- Tình trạng đường thẳng quét cho biết thứ tự giữa các đoạn thẳng được cắt
bởi đường thẳng quét.
- Lịch các điểm biến cố là một dãy các tọa độ

của các điểm đầu mút được


- Mỗi điểm đầu mút của các đoạn thẳng trong

là một điểm biến cố, là vị

trí đường thẳng quét nơi thứ tự thay đổi.
- Lịch điểm biến cố là tĩnh và được xây dựng bằng cách sắp xếp các điểm
đầu mút của các đoạn thẳng theo thứ tự từ trái sang phải.
Nếu khi sắp xếp các điểm đầu mút của các đoạn thẳng trong
phải nếu có nhiều điểm có cùng tọa độ

từ trái sang

thì phân giải trùng hợp như sau:

- Các điểm đầu mút trái được sắp xếp trước các điểm đầu mút phải.
- Tiếp theo, các điểm đầu mút có tọa độ y nhỏ hơn được xếp trước.
Sắp xếp các điểm đầu mút (x, y) theo thứ tự (x, e, y) trong đó xvàylàtọa
độvới e = 0 cho điểm đầu mút trái và e = 1 cho điểm đầu mút phải.
Thuật toán xác định cặp đoạn thẳng bất kỳ cắt nhaunhư sau[13].
Algorithm ANY-SEGMENTS-INTERSECT
Input. Tập hợp gồm đoạn thẳng.
Output. Cặp các đoạn thẳng trong

cắt nhau thì giá trị True, ngược lại là False.

1.
2. Sắp xếp các điểm đầu mút của các đoạn thẳng trong

từ trái sang phải, phân


8.
9.

if (ABOVE

và (ABOVE
10.
11.

và BELOW

cắt BELOW

đều tồn tại)

) then

return TRUE
DELETE

12. return FALSE
1.3.1.3 Phân tích độ phức tạp
Định lí 1.1 Gọi là tậphợp gồm đoạn thẳng, thuật toán ANY-SEGMENTSINTERSECT thực hiện trong thời gian

[13].

Thật vậy, dòng1thực hiện mấtthời gian là
gian là

. Dòng2thực hiện mất thời

p
lồi
Bao lồi của tập hợp

p
không lồi

bất kỳ là giao của tất cả các tập lồi chứa

bằng trực quan hơn, tập lồi nhỏ nhất chứa , kí hiệu

, hay

[26].

1.3.2.1 Phát biểu bài toán
Cho

là tập hợp các điểm trong mặt phẳng và yêu cầu tìm bao lồi

của nó, tức là tìm đa giác lồi nhỏ nhất mà mỗi điểm của
của hoặc nằm trong phần trong của .

hoặc nằm trên biên


12
p10

p10


p0

gồm các điểm và bao lồi

Hình 1.2 -Tập hợp
1.3.2.2 Thuật tốn

Thuật tốn qt Graham và thuật tốn bước Jarvis tìm bao lồi của tập hợp
gồm điểm trong mặt phẳng. Cả hai thuật toán quét Graham và bước Jarvis đều
sử dụng kỹ thuật “quét quay trịn”, các đỉnh được xử lí theo thứ tự của các góc
giữa tạo với một đỉnh tham chiếu.
Thuật tốn qt GRAHAM [13, 17]
Thuật tốn qt Grahamgiải quyết bài tốntìm bao lồibằng cách khởi
tạongăn xếp gồm cácđiểm ứng viên. Mỗiđiểmcủatập hợp đầu vàotrong
đẩylênđầu ngăn xếpvàcác điểmkhơng phải làđỉnhcủa
ngăn

xếpsau

xáccácđỉnhcủa

cùng.

Khithuật

tốnkết

thúc,


2.

trái trong trường hợp đồng hạng.
Gọi
là các điểm còn lại trong , sắp xếp theo góc nhọn
(polar angle) theo thứ tự ngược chiều kim đồng hồ quanh

(nếu có nhiều

hơn một điểm có cùng góc thì loại bỏ tất cả nhưng lấy điểm xa nhất từ

).


13
3.

PUSH

4.

PUSH

5.

PUSH

6.

for

nàycũng là mộtđỉnhcủabaolồi.Cứ thực hiệntiếp tụcnhư thếtrên tập hợp
cácđỉnhcho đến khigặp lạiđỉnhban đầu .
Algorithm JARVIS'S MARCH
Input. Tập hợp gồm điểm trong mặt phẳng.
Output. Bao lồi

của .

1.

Chọn

là một điểm trong tập hợp

có tọa độ

2.

Chọn

là một điểm trong tập hợp

mà góc giữa đoạn thẳng

nhỏ nhất.
với trục

hồnhlà nhỏ nhất.
3.


Thật vậy, dịng1chi phíthời gian

. Dịng2chi phíthời gian là


14
, bằng cách sử dụngmegersort hoặcheapsortđểsắp xếpcác góc giữa
vàphương pháptích có hướng để so sánh các góc. Dịng3-5chi phí thời gian
là

. Vì

, vịng lặp forcủa dịng6-9được thực hiệnnhiều nhất

lần. Khi đó thao tác PUSHchi phí thời gian

, mỗi lần lặpchi phíthời

độc lập vớimất thời gian cho vịng lặpwhile của dịng7-8vàvì thếtồn

gian

bộ vịnglặp for mấtthời gian

chỉ có mộtvịng lặp while lồng nhau.

mỗiđiểm được đẩyvàongăn xếp đúng một lần, cónhiều

Với


Thật vậy, với

điểm trong mặt phẳng. Thời gian thực hiện

, trong đó

đỉnh của

[13].

, tìm đỉnhvớigócgiữa nhỏ nhất.Mỗilần so

sánhcác góc giữavới chi phí thời gian là
trịtrong thời gian

là số đỉnh của bao lồi

. Ta có thểtính tốnít nhất giá
.Như

nếumỗi lần so sánhchi phí thời gian là

vậy,thuật tốn bướcJarvisđược thực hiện với chi phí thời gianlà

.

1.3.3 Bài tốn tìm cặp điểm gần nhất
Bài tốn cặp điểm gần nhất tìm hai điểm gần nhất trong tập hợp điểm cho
trước.Khoảng cách giữa các điểm thường được xét trong các bài tốn hình học khoảng cáchEuclide:khoảng cáchgiữa các điểm
và

mảng và ,mỗi mảng có chứatất cả các điểmcủa tập conđầu vào

.Các điểm

trongmảng được sắp xếptăng dần theo tọa độ , mảng được sắp xếp tăng
dầntheotọa độ .
Divide:Chiatập hợp các điểm thành hai tập con
tọa độ

trong

(

với điểm giữa của

và

bởi đường thẳng dọc tất cả

,

các điểmtrong nằm trênhoặcbên trái củađường thẳng và tất cả các điểm
trong

nằm

mảng

và



chứa

tương ứng,sắp xếp tăng dần theotọa độ .

Conquer:Tập hợp các điểm

được chia thànhhai tập con

và

,tạo ra

hai lời gọiđệ quymột lời gọi đệ quy tìm cặpđiểmgần nhấttrong vàlời gọi đệ quy
.Cácđầu vào củalời gọi đầu tiênlà tập con ,

khác tìmcặpđiểmgần nhấttrong

và ; lời gọi thứ hainhận các đầu vào

mảng
cáchcặp

điểm gần nhấttrả

lạicủa và

,

và

sau

được nằm trong đơn

cần được xem xét. Thuật tốn tính

đến mỗi điểm trong 7 điểm đó và theo dõi những khoảng cách

cặp điểm gần nhất
- Nếu

với tất cả các điểm không nằm trong dải

đã tìm trên các cặp điểm trong mảng .
thì dải dọc thực tế khơng có một cặp điểm gần hơn đã được

tìm thấy bởi các lời gọi đệ quy. Cặp điểm này và khoảng cách

của nó được trả

về. Ngược lại, cặp gần nhất và khoảng cách của nó được tìm bởi các lời gọi đệ
quy được trả về.


16
PR

PL

pL

= CLOSEST_PAIR(

3.
4.

thành

) và

thành

và

.

= CLOSEST_PAIR(

).

.
Tính khoảng cách giữa các điểm mà một điểm nằm trong
điểm nằm trong

4.1 Mảng

trong

cặp điểm gần nhất
4.3 Nếu


Return

1.3.3.3 Phân tích độ phức tạp
Định lí 1.4Cho tập hợp gồm điểm trong mặt phẳng. Thời gian thực hiện thuật
toán tìm cặp điểm gần nhất là
Thời gianthực hiện là
bảo đảmcác mảng

và

[13].
. Khó khănchính ở việc
được truyền chocác lời gọiđệ quyđược sắp xếp

theocáctọa độthích hợp vàcũnglàmảng được sắp xếp theo tọa độ .


17
Trình bàychínhở trongmỗi lời gọi,cầntạo thành mộttập conthứ tựcủa
mộtmảng được sắp xếp. Tập hợp được chia thành và ,hình thànhcácmảng
được sắp xếp theo tọa độ

và

. Phương phápnày có thể xem như làđối

lậpvới thủ tụcMERGEtừthuật toán sắp xếp trộn (merge sort):chia mảng được sắp
xếpthành haimảngđược sắp xếp.Để đơn giản kiểm tra các điểm trongmảng theo
thứ tự.Nếumột điểm


quyvà

và
Do đó

và

[13].

1.4 Kết luận
Trong chương này giới thiệu về các vấn đề của hình học tính tốn, các đối
tượng cơ bản của hình học và các thuật tốn kinh điển của hình học tính tốn
trong khơng gian hai chiều. Thuật tốn xác định cặp đoạn thẳng bất kỳ cắt nhau
được đưa ra bởi Shamos và Hoey [28] với độ phức tạp về thời gian là
.
Thuật tốn tìm bao lồi của tập hợp các điểm trong mặt phẳng sử dụng phương
pháp quét là thuật tốn qt Graham [17] với chi phí thời gian là
và
thuật tốn bước Jarvis [19] với chi phí thời gian là

. Có nhiều phương

pháp để giải quyết bài tốn tìm cặp điểm gần nhất với độ phức tạp khác nhau, sử
dụng thuật tốn chia để trị tìm cặp điểm gần nhất thì thời gian thực hiện là
được đưa ra bởi Shamos và xuất hiện trong Preparata và Shamos
[27].


18



Hình 2.1- Giải thíchtruy vấncơ sở dữ liệu một cách hình
Nếucó thêm thơng tinvềsố concủamỗi nhân viênvà u cầu tạo truy
vấn“báo cáo tất cả nhân viêncó tuổi từ 30 đến 50, thu nhậphàng tháng từ
4000000 đến 6000000 và cótừ 2 đến 4 con”.Trong trường hợpnày,mỗinhân viên


19
được mô tả bởimộtđiểmtrongkhông gianba chiều vớitọa độthứ nhất, tọa độ thứ
hai,tọa độthứ babiểu diễntuổi,lương và sốcon tương ứng. Để trả lờitruy vấn, cần
phảibáo cáotất cảcác điểmnằm trong hìnhhộpsong songtrục tọa độ [30 : 50]
×[4000000: 6000000] ×[2: 4]. Nếu taquan tâmcác truy vấntrả lờitrên

thuộc

tính củacác bản ghi trongcơ sở dữ liệu thì các bản ghiđược chuyển thành các
điểmtrongkhơng gian chiều. Mộttruy vấnu cầubáo cáotất cảcác bản ghicó các
thuộc tínhnằmgiữa cácgiá trịcố địnhthì chuyểnthành mộttruy vấnđưa ra tất cảcác
điểmnằm trongmộthình hộpsong songtrục tọa độ chiều. Như vậy,truy vấnnày
được gọilà truy vấn phạm vi hình chữ nhậthoặc truyvấnphạm vi trực giaotrong
hình học tính tốn [5].

6000000
4000000

4
2
30

50


.

là hai lá nơi mà tìm kiếm kết thúc tương ứng với

Trước tiên tìm theo

và trong

. Các điểm trong phạm vi

điểm được lưu trữ tại các lá ở giữa
lưu trữ tại

lưu trữ các giá trị chia hỗ trợ việc tìm

và lưu trữ tại

và

bao gồm

. Để tìm các lá giữa

và

và

và


10

37

3

3

30

19
10

19

23

30

62
49

37

89

59

62



, hoặc lá nơi mà cả hai

đường đi kết thúc.
1.
2.
3.

while

khơng là lá và(

if

hoặc

) do

then

4.
5.

else

6.

return
Bắt đầutừ


)

và phạm vi

Output. Tất cả các điểm lưu trữ trong

nằm trong phạm vi.

← FINDSPLITNODE(

1.

)

2.

if

là một lá then

3.

Kiểm tra nếu điểm lưu trữ tại

4.

else (∗ Theo đường đi đến và báo cáo các điểm trong cây con phải của

thì phải được báo cáo.




22
2.1.1.3 Phân tích độ phức tạp
Định lí2.1Chotập hợp gồm

điểmtrong khơng gianmột chiều. Tập hợp

đượclưu trữ trongcây nhị phân tìm kiếmcân bằngsử dụnglưu trữ

và có thời

, như vậycác điểmtrong phạm vi truy vấncó thểbáo

gian xây dựng
cáotrongthời gian

, với làcácđiểmbáo cáo [5].

Thật vậy, cấu trúc dữ liệu sử dụng trong tìm kiếm phạm vi một chiều
làcây nhị phân tìm kiếmcân bằngsử dụnglưu trữ

và có thểđược xây dựng

Trongtrường hợpxấu nhấttất cảcác điểmcó thểnằm

trongthời gian

trongphạm vitruy vấn thì thời giantruy vấnlàΘ(n). Thời gian chi phí một lời gọi
REPORTSUBTREElàtuyến tínhvới sốđiểmbáo cáo. Do đó, tổng thời gianchi phí

vàtọa độ

. Giả sửrằngkhơng cóhaiđiểmtrong

.Mộtđiểm
và

cùngtọa độ

vàtọa độ

nằmtrong hình chữ nhậtkhi và chỉ khi
[5].

y

y’
p

py
y
x

x

px x’

2.1.2.2 Thuật toán và cấu trúc dữ liệu
2.1.2.2.1 Kd-trees 2 chiều (2-dimensional Kd-trees)
Ta cần xây dựng cấu trúc dữ liệu cho truy vấn phạm vi hai chiều. Trong

Input. Tập hợp các điểm

bởi đườngthẳng

)

và chiều sâu hiện tại

.

Output. Gốc của kd-trees được lưu trữ .
1.
2.
3.
4.

if chỉ chứa một điểm then
return lá lưu trữ điểm này
else if

là chẵn then
Chia
tọa độ

hoặc nằm trên

thành hai tập con bởi đường thẳng dọc
của các điểm trong
và