課 程：演算法 指導教師：楊昌彪 系 級：資工博三 姓 名：盧育群 學 號：8834809
Voronoi Diagrams( Apply to Mobile Phone Position
Located problem)
簡介：
於行動電話通訊網路中，在某些特定的需求中（諸如：刑事辦案、所在地相關資訊查詢服務、…等），我們必須求得行動電話所處位置、區塊的問題。
問題與原理解說：
本類的問題最主要的是要能求得行動電話明確之所處區域，且其範圍縮得愈小愈好。據此，我們提出下述的解決方案，其乃基於Voronoi Diagrams、Delaunay Triangulation與其相關之理論基礎。以下開始說明相關的基礎定義與演算法：
在行動電話通訊網路中，行動電話漫遊於基地台所涵蓋的服務範圍之中，手機在任一瞬間所使用的基地台，是在其所搜尋到的基地台訊號強弱列表中（一般為四到九組基地台）選擇訊號最好的基地台來註冊使用服務。
因此，針對以上特性，我們將此問題轉換到解Voronoi Diagrams的問題，
關於Voronoi Diagrams的定義，以下節錄自楊昌彪教授課程講義第五章：
l The Voronoi diagram problem
e.g.
The Voronoi Diagram for Three Points
Each Lij is perpendicular bisector of the line 
.
Def: Given two points Pi, Pj Î S, let H(Pi, Pj) denote the half plane containing Pi. The Voronoi polygon associated with Pi is defined as
V(i)
= 
H(Pi,
Pj)
e.g.
Given a set of n points, the Voronoi diagram consists of all the Voronoi polygons of these points.
e.g. A Voronoi diagram of 6 points:
The vertices of the Voronoi diagram are called Voronoi points and its segments are called Voronoi edges.
e.g. A Delaunay triangulation:
在此，我們將提供服務的基地台視為Voronoi Diagrams問題中的各點，假設每個基地台的發射功率均相同，而建物對電波訊號的干擾可忽略不計。當行動電話距離某一基地台較近時（進入它的勢力範圍），該基地台的訊號最強，因此會向該基地台註冊，並由該基地台提供服務，所以我們要求出各點的勢力範圍分佈圖Voronoi Diagrams，即可得知行動電話所處的區域範圍（第一版）。
在解Voronoi Diagrams的問題上，我們先求出各點所對應之Delaunay Triangulations，之後再進一步使用過程中已得知的中垂線、外心、visible neighbors等相關資訊求得相對應之Voronoi edges。在Delaunay Triangulations的建構上我們使用的是Bowyer-Watson Algorithm。
接下來我們針對演算法的部分做進一步的說明
演算法：
Step 1
Define a bounding box that contains all
the points. This step is needed to initialise the algorithm by defining an
initial triangulation and associated topology.
One of the possibilities is to specify
four points together with the associated vertex and neighbours structure. The
Figure below shows a typical start-up layout for the two-dimensional case.
Another possibility is to define an initial simplex (a triangle in 2D) which contains all the points.
figure. a Start-up layout in two dimensions (4 points, 2 triangles)
Step 2
Introduce a new point anywhere within the
bounding box which, by construction, contains all the points.
Step 3
Find the first triangle that fails the
Delaunay test.
Step 4
Determine all triangles that make up the
Delaunay cavity ..
The remaining steps in the algorithm are
needed to update the data structure. Broken elements are deleted and new ones,
obtained by connecting the new point to all edges of the cavity, are created.
Finally it is necessary to determine the contiguities that exist between the
new elements and also between the new elements and the ones that are on the
boundary of the Delaunay cavity to update all topological relationships.
Step 5
Remove all triangles in the Delaunay
cavity.
Step 6
Connect the edges of the Delaunay cavity
with the new point to generate a new set of triangles.
Step 7
Update the neighboring information for the
new triangles and the elements at the boundary of the cavity.
Step 8
Goto Step 2
We now have a triangulation of the set of
points whose boundary is defined by the extent of the bounding box built at the
beginning of the procedure.
Step 9
If we remove from the list of triangles
all elements that share a vertex with the initial bounding box, we obtain a
Delaunay triangulation of the convex hull of the given set of points. We can
also extract the boundary of the triangulation to obtain a set of edges
defining the convex hull of the point set.
Definition 1:
Let T be a Delaunay triangulation and let’s consider a new point P inside T. Let B Ì T be the set of triangles which are broken by P because they fail the In-Circle criterion (section 2.4.2) . Clearly this set contains at least one member, the triangle that contains P (fig 2.10a-b). Once a first broken element is found, by following the explicit topological relationships of each triangle with its neighbours it is easy to find the whole set of elements that fail the In-Circle criterion. The region created by removing B from T is called a Delaunay cavity.
Definition 2:
The point A of a
triangle set is visible from another point B if it is possible to join A
to B without intersecting any other edge. For the Bowyer-Watson’s algorithm to
be valid, it is necessary that all points of all edges forming a Delaunay
cavity be visible from point P. The situation depicted below, for example,
where edge CD is not visible from P leads to an invalid triangulation in which
two or more edges intersect . It is also necessary that the new triangulation,
formed by connecting P to the boundary points of the cavity, also be Delaunay.
Baker (1987) contains
complete proofs for definitions 1 and 2 and why the procedure described
generates a valid Delaunay triangulation.
Definition 3:
Given a triangle
(ABC), the circumcircle of the triangle, the centre of the circumcircle V, and
a point P, the comparison of the distance between a point P and the
circumcentre V with the radius (r) of the circumcircle will be referred to as
the Delaunay test for the triangle (ABC) and point P. If a point is
found to lie inside the circumcircle then we can say that the point has failed
the Delaunay test for that particular triangle.
程式設計：
The key issues of this algorithm about determining Delaunay cavity and Delaunay test function are implementing in isCross() and SetDelaunay() subfunctions.
There are some special exceptions need to take care during the implementation:
· two points are coincident
The first degeneracy is easily avoided by
requiring that each new point be some small distance from its nearest
neighbours. The n-tree data structure provides a natural way of guaranteeing
this, in fact points are sifted into the data structure and those that are
"close enough" to each other (depending on the machine precision)
will end up in the same space partition. At this point a co-ordinates check
against all the points already in the tree node is done to guarantee
uniqueness. In this latest comparison operation an allowance is made to
compensate for lack of machine precision through the use of a precision
parameter e (epsilon),
so that co-ordinate whose absolute distance is less than e are considered equal.
· three points of a potential triangle lie on a straight line
This degeneracy is equivalent to there not
existing a circumcentre of the three forming points of a potential triangle.
This case can be easily detected as the routine to compute the co-ordinates of
the circumcentre will fail. The point that causes the degeneracy is at first
temporarily excluded from the construction and another insertion attempt is
made at a later stage, if the problem still exists the point is then definitely
rejected. This is in practice a very rare case especially in two dimensions.
· four or more points are cyclic
This third degeneracy is of a more subtle
nature than the preceding two. In this case two Voronoi vertices are coincident
and generate a case where more than three Dirichlet polygons meet (fig 2.15).
In such a situation the resulting triangulation is not unique due to a symmetry
in the data points but this in itself is not a problem as the two possible
triangulations are both correct and acceptable. Which one is then built will
depend on the order of insertion of the points.
實驗結果：
Time Complexity Analysis:
To define the complexity
of the algorithm used in this implementation we need to highlight which
components are dependent on the number of points and therefore play an
important part in the complexity equation. With the exception of Step 3, all
the operations required are of a local nature and can be carried out in a time
independent of the total number of points within the current structure. When a
new point is inserted, we first have to search for the first element that fails
the Delaunay test. The other elements in the Delaunay cavity can be found using
a recursive search of the neighbors of the first element found if we maintain a
topological relationship among the elements so that each triangle also stores
the reference to all its neighbors.
We can define the time
T needed to generate a triangulation for N points as :
where Tk is the time to find the first element to be deleted and Sk the time to find all the other elements in the cavity. Sk will be proportional to the number of elements in the cavity, this can be considered independent from k if the points are inserted randomly into the triangulation (Baker, 1987). This means that we can consider Sk as being O(1). We can see now that the complexity of the algorithm is dominated by the search time Tk. In the worst case Tk will be O(k) leading to a total complexity of the triangulation of O(N2). To improve the time complexity of the algorithm it is then necessary to implement a data structure that allows an efficient search of the first element to be deleted independently from the way the points are sorted. If the search time Tk can be reduced to logN we could obtain a time complexity for this algorithm close to the theoretical optimum of O(NlogN).
結論心得：
本project的第一版是根據行動電話與基地台間的特性可與Voronoi Diagrams的問題相對應來解決其Position Locating的問題，但其實在行動電話其所搜尋到的基地台訊號強弱列表中（一般為四到九組基地台）隱含了更豐富的資訊可用來進一步的縮小其所在的地理範圍資訊，也就是說，我們可以引用目前所在的基地台（63）相關的Delaunay Triangulations的基地台資訊（如：11、08、19、74、…等）與行動電話上的基地台訊號強弱列表（如：63 > 08 > 11 > 74 > 19）。據此，以下圖為例，我們就可以將其所處的地域範圍大幅縮減到淺綠色多邊形的範圍，這是我們第二版要完成的部分（To be continued…）。
i.e. : 此法若應用在PHS低功率行動通訊環境下，縮小的範圍將更為顯著，因為目前各家廠商所生產的PHS基地台所能涵蓋的範圍界於一到五百公尺之間。
附錄：
原始程式碼（Java）：MPLocating.java
高雄地圖：KSMap.gif
Java applet: MPLocating.class
On-line Applet：
|
|