2D and 3D Voronoi Diagrams - Essay Example

The use of computer simulations to a model a geographic location is already widespread especially in terrestrial systems. The need formodeling marine systems rose from the increasing active use of the said system especially in navigation and environmental management concerns. Because of this, 2D Voronoi Diagrams were develop to enable the modeling of such systems. Improvement in computer technology and persistent and brilliant ideas paved the way for a 3D counterpart . This paper compares the two models by looking at its advantages and disadvantages over the other and points out the strengths and weaknesses inherent in the system. Introduction Traditional GIS methods have been found to inapplicable for marine mapping. This is primarily because they were built for two-dimensional land application making it hard to integrate marine features into the model. Marine objects are also likely to move over time which cannot be modeled using the traditional GIS. These limitations necessitated the development of a new modeling system that can accurately incorporate marine features while allowing modifications to the system which does not require an overhaul of the whole model. Christopher Gold (1990) responded to the challenge by spearheading research and development of the Voronoi Diagram - a modeling system with a dual geometric structure. Most of the literature on the development of the VD, either in 2D or in 3D, was authored by him. Voronoi diagrams that were developed were able to solve most of the problems because of the following features: 1) VD will adapt naturally to distribution of data 2) Tiling properties enable topographical management between unconnected objects 3) Local update to topology available All of these features are available in 2D and 3D Voronoi Diagrams. This paper aims to differentiate 2D Voronoi Diagrams from 3D Voronoi Diagrams delineating their differences, advantages and disadvantages over the other. This paper also aims at pointing out the strengths and weakness of the two diagrams such that a conclusion on which one is more advantageous can be made. 2D Voronoi Diagram Construct In 2D Voronoi Diagram, the cell surrounding a data point is a flat convex polygon having a defined number of neighbors (Gold and Ledoux, 1992). That is, its coordinates are only x and y with no z attribute. The analogy is the same as that of drawing figures on a piece of paper. When a plan view is done on the paper, one can see the shapes defined by the lines that were drawn. When the paper is leveled against one's eyesight, there are no figures which can be seen. This illustrates that no such elevation or depth attribute of the figures exist. The geometric dual structure of 2D Voronoi Diagrams are also "flat" in nature and are defined by Delaunay triangles. In Figure 1, Delaunay Triangles are shown by the dashed lines while the solid lines defining a polygon represent the cells surrounding a data point p. Figure 1. A 2D Voronoi Sample Output (Gold, 1991) The vertices of the triangle generating each Voronoi cell must satisfy the empty circumcircle test. A circle is considered empty when there are no points in its interior but more than three points can be directly on the circle - i.e. the points are on its edges. 3D Voronoi Diagram Construct 3-Dimensional Voronoi Diagrams, as implied by its name, have 3 coordinates defining the space where the figure can be drawn. As opposed to 2D VDs', leveling the plane of the paper with one's eyesight provides a view of the sides of a figure. An appropriate analogy would be that of the viewing a cube held by the hand. When the figure is viewed from the top, one can see a square. When the hand is leveled against one's eyesight, one can still see the figure of a square. The figure is a volumetric object. The convex polygon in a 2D, thru a construction algorithm, generalizes to a convex polyhedron. The geometric dual becomes a Delaunay tetrahedron. In Figure 2, the edges are the Delaunay edges joining the generator to its natural neighbors. The data set is the point directed by the arrow. Figure 2. A 3D VD cell (Gold, 1991) The Delaunay Tetrahedral must also satisfy the empty circumcircle test. The DT's are unique for a set of points except when five or more points are co spherical in 3D. Advantages of Using 3D Voronoi Diagrams The main advantage of using 3 dimensional modeling lies in its comprehensive and realistic construction of the environment involved. In 2D Voronoi Diagrams, a person will only be able to see lines, points, flat polygons and segments. Consider the following figures below: Fig 3. A 2D VD Simulation of Boat Navigation Fig. 4. 3D VD Simulation of Boat Navigation (Gold, 1992) (Gold, 1998) In Fig. 3, the boat is represented by a shaded figure labeled B. Another boat is represented by a shade labeled A. In Fig. 4, we have a ship modeled as if the viewer is actually in the operating environment. Looking at the figures, it is apparent that the 3D VD provides a better rendering and more realistic simulation of the events that are taking place in the environment. As can be seen from Fig 4., 3D VDs provides a volumetric view of objects. This feature enables the user to have a dynamic view of the objects in the diagram. He is now given the facility to view the environment at any angle. From Fig 5, the user can also see the height of marine outcrops and depth of water along with its two other dimensions. In planning, as is often done with Geographical Information Systems, the planner needs to have a view of the environment in which he is working on. The view provided by the 3D diagram is such that the viewer is really inside the environment. 2D VD's can be considered as a flat map while 3D Fig. 5. Island Rendering of 3D VD (Gold and Ledoux, 1997) VD's are those maps with clay models of vertical structures imposed on horizontal attributes like ports and highways. Looking at Figure 4 and Figure 5, one can see that 3D VD's are more appealing to end users. The flexibility that it provides- view at any angle, color rendering, volumetric view- makes it more preferable to use. These features provide better visualization which is precisely what Geographical Information Systems should offer. Another benefit of the display is that environmental management trainees can get a better feel of the simulated environment that they are working on. The realistic rendering of 3D VD's enables them to relate the events in real world situations. Disadvantages of Using 3D Voronoi Diagrams Modeling in 3 dimensions is quite challenging because of the addition of the 3rd coordinate. To illustrate, let's say one is to model a boat moving in a flowing body of water. Data on boat dimensions are needed. The mechanics of boat movement - speed, turnings, acceleration- should be considered to really have a realistic model. This illustration is just one of the few problems when modeling with 3D VD's. The complexity of model construction and other disadvantages are enumerated and discussed below: 1. The Existence of Slivers Slivers are tetrahedrons which have their four vertices almost lying in a plane. It therefore has a volume of almost zero. This is caused by the inability of the system to fully maximize the minimum angles - to make it as equilateral as possible. Slivers are unwanted because they pose a problem in interpolating. Interpolating is used to estimate the value of an attribute at unsampled locations. It is required to model, visualize and better understand a dataset and also to convert a dataset to another format. A sliver will return an erroneous value and may corrupt the system. 2. Large Storage Space Required With all the data needed to model 3D objects, it is expected that a larger memory is needed for the computer to run it effectively. In a 2D VD, the computer only deals with flat polygons and lines. It does need to generate objects along with their height and the accompanying changes in the surface of the object making the storage space needed quite small as compared to 3Ds. 3. Construction Algorithm is inherently unstable. The available construction algorithms for 3D VDs all possess glitches that undermine the integrity of the whole system. The algorithm proposed by Brown (1979) requires the construction of convex hulls (polygons in 2D and polyhedrons in 3D) of the set of points and then projecting it one dimension lower to get the Delaunay tetrahedralization. Although this is quite useful and easy to implement to get the DT dual structure, local modifications such as point insertion, deletion and movement are slow or may even be impossible. This translates to the modification of the whole system whenever a new data is inserted. There are algorithms which were developed to allow local modifications. These are called 'incremental insertion algorithms'. The first of its kind was proposed by Watson (1981). The problem with his algorithm was that it requires deletion of any tetrahedral that conflict with the generated space needed by the inserted data point. Although temporary, the deletion of tetrahedrals temporarily can corrupt the algorithm itself as was explained by Field (1986). 4. Point Deletion Problem The point deletion process of 3D Voronoi Diagrams follows that of Devillers (2003) point deletion algorithm for 2D VD's. This algorithm involves deleting all the triangles incident to the point to be deleted. A retriangulation using a priority queue of the potential triangles is then used to fill the hole. The process generalizes to 3D with the 3D tetrahedrals being deleted. Again, the deletion can result to the corruption of the system. Advantages of Using 2D Voronoi Diagrams Although 2D's seem to be the underdog, it does have some benefits that can outweigh its limitations in visual display. They are the following: 1. Algorithms are not as problematic as that of 3D VD's As was already discussed, 3D VD algorithms tend to be unstable. In 2D VD's, point deletion, insertion and movement algorithms are relatively free of these nuisances. 2. Lower Data Storage Space required Handling 2 Dimensional objects require only computations and movements in 2 coordinates. The data needed for the display of the object are just its length and width with information on its height and any other relevant information stored but not incorporated directly in the visual display. 3. Angles of dual structure are as equal as possible 2D makes use of Delaunay triangulation which creates triangles with angles as equal as possible. This feature facilitates the interpolation process and does not give rise to corrupted figures as slivers are to Delaunay tetrahedrals. Disadvantage of 2D Voronoi Diagrams The main disadvantage of 2D VD's is its limited visualization capacity. Two dimensional modeling of a 3 Dimensional environment results is technically undesirable as it offers limited views of the working environment. Furthermore, the use of triangles as dual structures in computer modeling is considered as primitive and therefore unappealing to the public's taste. When, for example, the model is presented to the public, 3 dimensional figures tend to be more effective in making laymen appreciate the information offered by the system. Although 2D's can technically give adequate information, it is harder to appreciate and may lead to conflict in information understanding. Conclusion Considering all factors, the 3D Voronoi Diagram is more advantageous compared to its 2D counterpart mainly due its to its visualization capacity which is precisely what is needed for an effective GIS As is expected, 3D VD construction requires more involvement because of the addition of a dimension. The addition does not only entail incorporating the attribute but also designing its interaction with its surrounding. One can imagine the complexity of the different factors that needs to be included in the system. The 2D Voronoi Diagrams are the precursors of the 3D VD's and we may therefore expect it to be called primitive. Whatever the case maybe, both diagrams revolutionize the way marine systems are modeled. References: Gold, Christopher and Ledoux, Hugo. (1997) The 3D Voronoi Diagram and its Dual: Simultaneous Construction and Storage. Retrieved October 20,2006 from http://homepages.ge.ucl.ac.uk Ledoux, Hugo and Gold, Christopher (1991) Modelling oceanographic data with the three-dimensional voronoi diagram. Retrieved October 20,2006 from http://www.voronoi.com Gold, Christopher (1990) An Algorithmic Approach to a Marine GIS. Retrieved October 20, 2006 http://www.voronoi.com Gold, Christopher and Edwards, Geoffrey (1992). The Voronoi spatial model: two- and three- dimensional applications in image anlaysis. Retrieved October 20,2006 from Gold, Christopher and Ledoux, Hugo (1998) 3D Topology and Data Structures Retrieved October 20,2006 from http://homepages.ge.ucl.ac.uk Devillers, O. and Teillaud, M.,( 2003). Perturbations and Vertex Removal in a 3D Delaunay Triangulation, Proc. 14th ACMSIAM Symp. Discrete Algorithms (SODA), Baltimore, MD, USA, pp. 313-319. Brown, K.Q., 1979. Voronoi diagrams from convex hulls.Information Processing Letters, 9(5): 223-228. Watson, D.F., 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. TheComputer Journal, 24(2): 167-172 Read More