ĐẠ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 TOÁ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Ệ
Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN 6
1.1 Các bài toán của hình học tính toán 6
1.2 Các đối tượng hình học 8
1.3 Một số bài toán hình học và thuật toán 8
1.3.1 Bài toán xác định cặp đoạn thẳng bất kỳ cắt nhau 8
1.3.2 Bài toán tìm bao lồi 11
1.3.3 Bài toán tìm cặp điểm gần nhất 14
1.4 Kết luận 17
Chương 2 - KIỂU DỮ LIỆU TRỪU TƯỢNG TRONG HÌNH HỌC TÍNH TOÁN 18
2.1 Tìm kiếm phạm vi trực giao 18
2.1.1 Mô hình quản lí đối tượng một chiều 19
2.1.2 Mô hình quản lí đối tượng hai chiều 22
2.1.3 Mô hình quản lí đối tượng nhiều chiều 30
2.2 Cấu trúc dữ liệu hình học 35
2.2.1 Interval trees 36
2.2.2 Priority search trees 41
2.2.3 Segment trees 45
2.3 Biến thể của các cấu trúc dữ liệu hình học 51
2.3.1 Partition trees 52
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
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
Windowing queries
Truy vấn cửa sổ
3
DANH SÁCH HÌNH VẼ
Số
Tên hình
Trang
Hình 1.1
Thứ tự giữacácđoạnthẳng với đườngthẳngquétdọc
9
Hình 1.2
Các mảngliên kếtvớicác núttrongcây chính
34
Hình 2.10
Truy vấn cửa sổ trong bản đồ của U.S.
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
43
Hình 2.16
Truy vấn của cây tìm kiếm ưu tiên
43
Hình 2.17
Đoạn thẳng lưu tại v thay vì lưu trữ tại và
47
Hình 2.18
Segment trees: mũi têntừcácnúttrỏtới tập con chính qui
48
Hình 2.19
(1/2) - cutting kích thước 10 cho tập hợp 6 đường thẳng
61
Hình 2.27
Cáctập con chính quivàtập conđiquatam giác
62
Hình 2.28
Tìm kiếm phạm vi tam giác
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
Hình học tính toán xuất hiện từ lĩnh vực phân tích và thiết kế thuật toán
trong cuối những năm 1970 và lớn mạnh trở thành một môn học với tạp chí
6
Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN
1.1 Các bài toán của hình học tính toán
Hình họctính toánlà mộtchuyên ngành củakhoa họcmáy tínhnghiên
cứucácthuật toáncó nội dung hình học. Một sốbài toánhình họcphát sinh hoàn
toàntừviệc nghiên cứu cácthuật toánhình học tính toánvà cácbài toánnàycũng
đượcxemlà một phần củahình học tính toán. Hình học tính toán nghiên cứusự
phức tạpcủa cácbài toá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 toáncho cácbài toá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 toá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 toántrong hình học tính toá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à yê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à yêu cầutìm cặp điểm có
khoảng cách nhỏ nhất.
Nearest neighbor:Cho tập hợp các điểm và yêu cầutìmđiểm nằm gần nhất
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 toán cho bài toá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 toá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 toá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 toá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 và là
một điểm bất kỳ sao cho và
với . Hay viết dưới dạng khác .
rằng ở trên tại , kí hiệu .
Hình 1.1 -Thứ tự giữa cácđoạnthẳng vớiđườngthẳngquétdọc
Với bất kỳ cho trước, mối quan hệ là một thứ tự hoàn toàn của
đoạn thẳng cắt đường thẳng quét tại . Những mối quan hệ , ,
, và ; Đoạn thẳng không so sánh được với các đoạn thẳng
khác, hình 1.1a. Khi đoạn thẳng và giao nhau, nhưng ; mọi
đường thẳng quét đi qua vùng bóng mờ đều có và nằm liên tiếp nhau trong
quan hệ thứ tự , 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
sắp thứ tự từ trái sang phải để xác định vị trí dừng của đường thẳng quét.
Gọi mỗi vị trí dừng như một điểm biến cố. Tình trạng của đường thẳng
quét thay đổi tại các vị trí dừng của đường thẳng quét.
v
r
t
u
a
b
c
d
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
giải trùng hợp bằng cách đặt các điểm đầu mút trái trước các điểm đầu mút
phải và kế đến phân giải trùng hợp bằng cách đặt các điểm đầu mút có tọa
độ nhỏ hơn được sắp xếp trước.
3. for mỗi điểm trong danh sách được sắp xếp của các điểm đầu mút do
4. if là điểm đầu mút trái của đoạn thẳng then
5. INSERT
6. if (ABOVE tồn tại và cắt ) hoặc
(BELOW tồn tại và cắt s) then
7. return TRUE
11
8. if là điểm đầu mút phải của đoạn thẳng then
9. if (ABOVE và BELOW đều tồn tại)
và (ABOVE cắt BELOW ) then
10. return TRUE
11. DELETE
p
q
không lồi
12 Hình 1.2 -Tập hợp gồm các điểm và bao lồi
1.3.2.2 Thuật toán
Thuật toán quét Graham và thuật toá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 toán quét GRAHAM [13, 17]
Thuật toán quét Grahamgiải quyết bài toá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 được
đẩylênđầu ngăn xếpvàcác điểmkhông phải làđỉnhcủa được loại bỏ khỏi
ngăn xếpsau cùng. Khithuật toánkết thúc, ngăn xếp chứachính
xáccácđỉnhcủa theo thứ tự ngược chiều kimđồng hồ vớisự xuất hiệncủa
các điểm trên biên.Thuật toángọihàmTOP( ) - trả vềđiểmtrên cùng củangăn xếp
mà không thay đổithứ tự Svàhàm NEXT-TO-TOP( ) - trả vềđiểmtiếp theo
trong các điểmdướicùng củangăn xếp mà khôngthay đổithứ tự của .
Algorithm GRAHAM-SCAN( )
Input. Tập hợp gồm điểm trong mặt phẳng với .
Output. Bao lồi của là
1. Gọi là điểm nằm trong có tọa độ nhỏ nhất hoặc điểm ngoài cùng bên
trái trong trường hợp đồng hạng.
p
6
p
9
p
8
p
7
p
0
p
12
p
3
p
10
p
1
p
11
p
2
p
9
p
8
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 độ nhỏ nhất.
2. Chọn là một điểm trong tập hợp mà góc giữa đoạn thẳng với trục
hoànhlà nhỏ nhất.
3. Return
4.
5. while do
6. Chọn là điểm trong tập hợp mà góc giữa là lớn nhất.
7.
8. Return
1.3.2.3 Phân tích độ phức tạp
Định lí 1.2 Cho tập hợp gồm điểm trong mặt phẳng. Thời gianthực hiện
thuật toán quétGrahamlà , trong đó n là số điểm trong [13].
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
gian độc lập vớimất thời gian cho vòng lặpwhile của dòng7-8vàvì thếtoàn
bộ vònglặp for mấtthời gian chỉ có mộtvòng lặp while lồng nhau.
Với mỗiđiểm được đẩyvàongăn xếp đúng một lần, cónhiều
nhất một toán tử POPứng vớimỗitoán tử PUSH. Có ít nhấtbađiểm và -là
không bao giờlấy rakhỏi ngăn xếp, trongthực tế nhiều nhất toán tử
POPđược thực hiệntrong tổng số. Mỗilần lặpwhilemộtPOPthực hiệnvàdo
Divide:Chiatập hợp các điểm thành hai tập con và với điểm giữa của
tọa độ trong ( , 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 trênhoặc bên phải của .Mảng được chia thànhcác
mảng và ,chứacác điểm của và tương ứng,sắp xếp tăng dần theo tọa độ
. Tương tự,mảng được chia thànhcác mảng và , chứa
cácđiểmcủa và 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
khác tìmcặpđiểmgần nhấttrong .Cácđầu vào củalời gọi đầu tiênlà tập con ,
mảng và ; lời gọi thứ hainhận các đầu vào , và . Gọicác khoảng
cáchcặp điểm gần nhấttrả lạicủa và tương ứng là và ;gọi
.
Combine:Cặp điểmgần nhất hoặc làhaicặpkhoảng cách tìm thấybởimột
trong các lời gọi đệ quy,hoặc cặp điểm gần nhất là cặpđiểm vớimột điểm nằm
trong và một điểm khácnằm trong .Thuật toánxác địnhkhi cócặpđiểm
màkhoảng cáchnhỏ hơn . Nếu có cặpđiểm vớikhoảng cáchnhỏ hơn , cả hai
điểmcủa cặpđiểm đó phải đượcnằm trong đơn vị củađường thẳng .
- Tạo ra mảng , đó là mảng với tất cả các điểm không nằm trong dải
dọc rộng được loại bỏ. Mảng được sắp xếp theo tọa độ , cũng như .
- Với mỗi điểm trong mảng , tìm các điểm trong được nằm trong đơn
vị của . Chỉ có 7 điểm trong sau cần được xem xét. Thuật toán tính
khoảng cách từ đế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 đã tìm trên các cặp điểm trong mảng .
- Nếu 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ề.
p
L
p
R
P
L
P
R
P
L
P
R
các điểm trùng
nhau, một trong
P
L
, một trong P
R
các điểm trùng
nhau, một trong
P
L
, một trong P
được đưa ra bởi Shamos và Hoey [28] với độ phức tạp về thời gian là .
Thuật toá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 toán quét Graham [17] với chi phí thời gian là và
thuật toá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 toá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 toá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
Chương 2 - KIỂU DỮ LIỆU TRỪU TƯỢNG TRONG
HÌNH HỌC TÍNH TOÁN
2.1 Tìm kiếm phạm vi trực giao
Ngay từ đầu có vẻ nhưcơ sở dữ liệuítlàmviệc vớihình học. Tuy
nhiên,nhiềuloại câu hỏi – được gọi là các truy vấn –về dữ liệu trongcơ sở dữ
liệucó thểđượcgiải thíchmột cách hình học. Bằng cách chuyển các bản
ghitrongcơ sở dữ liệuthành cácđiểmtrongkhông giannhiềuchiềuvàchuyểncác truy
vấntrên bản ghithànhcác truy vấntrêntập hợp điểm.
Xétmộtcơ sở dữ liệuquản lí nhân sự, mỗi nhân viên được lưu trữ các
thông tin như họ tên,địa chỉ, tuổi,lương.Mộttruy vấntạobáo cáotìm tất cả các
nhân viêncó tuổi từ 30 đến 50 và thu nhập hàng tháng từ 4000000đến 6000000.
Vấn đềhình họcbiểu diễn mỗinhân viênlàmột điểmtrong mặt phẳng.Tọa độ thứ
nhất của điểm là tuổivàtọa độ thứ haibiểu diễn lương. Truy vấncơ sở dữ liệuyêu
cầu hiển thị tấtcảnhân viêncó tuổi từ 30 đến 50 và thu nhập hàng tháng từ
4000000đến 6000000 được chuyển thành truy vấnhình học: báo cáotất cả
cácđiểmvới tọa độthứ nhấttừ 30 đến 50vàtọa độ thứ hai từ 4000000đến 6000000,
nghĩa làbáo cáotất cảcácđiểm nằm trongtruy vấnhình chữ nhật song songtrục tọa
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ấnyêu 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 toán [5].
2.1.1 Mô hình quản lí đối tượng một chiều
2.1.1.1 Truy vấn phạm vi một chiều
Cho tập hợp gồm điểm trênđường thẳng thực là và
yêu cầu báo cáo tất cả các điểm nằm trong phạm vi truy vấn .
2.1.1.2 Thuật toán và cấu trúc dữ liệu
Cấu trúc dữ liệu được sử dụng để giải quyết bài toán truy vấn phạm vi
một chiều hiệu quả là cây nhị phân tìm kiếm cân bằng [26]. Các lá của lưu
trữ các điểm của và các nút trong của lưu trữ các giá trị chia hỗ trợ việc tìm
kiếm, nút lưu trữ giá trị chia . Giả sử cây con trái nút chứa tất cả các điểm
nhỏ hơn hoặc bằng và cây con phải chứa tất cả các điểm lớn hơn .
Gọi và là hai lá nơi mà tìm kiếm kết thúc tương ứng với và .
Trước tiên tìm theo và trong . Các điểm trong phạm vi là những
điểm được lưu trữ tại các lá ở giữa và bao gồm và , có thể chứa điểm
lưu trữ tại và lưu trữ tại . Để tìm các lá giữa và , trước tiên cần phải tìm
Output. Nút nơi chia các đường đi đến điểm và , hoặc lá nơi mà cả hai
đường đi kết thúc.
1.
2. while không là lá và( hoặc ) do
3. if then
4.
5. else
6. return
Bắt đầutừ theo đường đitìm kiếmvới , tại mỗinútvới đường đi bên
trái vàbáo cáotất cảcáclátrongcây conphải. Tương tự, theođường đi tìm kiếm
với vàbáo cáocác látrongcây contráicủacác nút. Cuối cùng,phảikiểm
tracácđiểmlưu trữtạicáclánơicác đường đi kết thúc, các điểm này có thể nằm
trong hoặckhôngnằmtrong khoảng .
49
23
19
80
70
100
89
59
30
62
37
10
3
10
3
23
thời gianlàtuyến tínhvới số điểmbáo cáo[5].
Algorithm 1DRANGEQUERY( )
Input. Cây nhị phân tìm kiếm và phạm vi
Output. Tất cả các điểm lưu trữ trong nằm trong phạm vi.
1. ← FINDSPLITNODE( )
2. if là một lá then
3. Kiểm tra nếu điểm lưu trữ tại thì phải được báo cáo.
4. else (∗ Theo đường đi đến và báo cáo các điểm trong cây con phải của
đường đi.∗)
5.
6.whileν không là lá do
7. if then
8. REPORTSUBTREE( )
9.
10. else
11. Kiểm tra điểm lưu trữ tại lá phải được báo cáo.
12. Tương tự, theo đường đi đến báo cáo các điểm trong các cây con trái
của đường đi và kiểm tra nếu điểm lưu trữ tại lá nơi đường đi kết thúc
phải được báo cáo. các cây con được chọn
root(T)
22
y
y’
y
x’
p
x
x
p
x
y
23
Trước tiênta chia theotọa độ rồi đến tọa độ và thực hiện luân phiên với quá
trình như sau:Tạigốc, chia bởi đường thẳng dọc thànhhaitập con và
có kích thướcgầnbằng nhau.Đường thẳngchiađượclưu trữtạigốc.Tập hợp
gồm các điểmở bên tráihoặc ở trênđường thẳng chia, đượclưu trữtrongcây
contrái và tập hợp gồm các điểm ở bên phải đường thẳng chia, được lưu
trữ trong cây con phải. Cứ thực hiện quá trình trên cho đến khi chỉ còn một
điểm. Một cây như thế gọi làkd-trees, cây mà trong hình 2.3 là 2d-trees hay còn
gọi là kd-trees hai chiều [5]. Hình 2.3 - Kd-trees: mặt phẳng được chia và cây nhị phân tương ứng
Thuật toán xây dựng kd-treesvới thủ tụcđệ quymô tảdưới đây[5].Thủ
tụcnàysử dụng haitham số: tập hợpcácđiểmvàmột số nguyên. Tham số thứ
nhấtlàtập hợpcác điểm dùng để xây dựng kd-trees; khởi tạolà tập hợp .Tham
sốthứ hailàchiều sâucủagốccây con. Tham sốchiều sâu bằng khôngtạilời gọiđầu
Copyright: Tài liệu đại học ©