Research On Crystal Growth Of City Voronoi Diagram With General Transportation Networks

The Voronoi diagram of a set of n given point sites in the plane is a basic data structure about spatial subdivision, which partitions the plane into the Voronoi regions of the sites with respect to a certain metric according to neighborhood. The result represents important spatial relative information including the neighborhood among sites and the domain of sites. It plays a significant role in the process of solving the problems of sites or other objects relative to distance. The city Voronoi diagram is a new type of Voronoi diagram which takes the shortest time between two points under the L1 plane as the distance. It answers the question how people move faster with transportation such as streets in a city or subway. Finding a shortest (time) path using such transportation is very important, because people tend to move with the shortest duration. In this situation, let us imagine a set of sites or service stations, for example, post office or supermarket, and suppose that any of them can satisfy us, then using the Voronoi diagram can solve the problem how to arrive at the service site which takes the least time by making use of the transportation.However, the traffic lines of the city in the city Voronoi diagram are required to be horizontal or vertical, and this limits its application to some extent, because there are a lot of traffic lines being inclined in impersonal world, and curves are more generally. To make the theory of the city Voronoi diagram more practical, we extend the traffic lines from straight lines to curves, then, we gain the city Voronoi diagram with general transportation networks. Here are some works in this thesis:1. Based on the city Voronoi diagram, we extend the traffic lines from straight lines to curves, then, we gain the city Voronoi diagram with general transportation networks, and introduce the definition and characters.2. Giving a thought and an algorithm of constructing the city Voronoi diagram with general transportation on the basis of crystal growth, and accomplishing it with VC++. To meet the request of the distance under the L1 plane and to trace the curve transportation, we combine the rhombus-shaped crystal growth with square-shaped crystal growth. The arithmetic is clear, readable and understandable. 3. Giving a simple method for seeking the shortest path. Shortest path map is a partition of space, which allows finding the shortest path from a source point to a query point. There is a fact that during the crystal growth of the Voronoi diagram with general transportation the shortest path from the source point to every growth point is formed, so as long as we start tracing the growth processing from the query point to the source point reversely, the shortest path from the source point to the query point is gained.4. Giving an application of the Voronoi diagram with general transportation.