The city Voronoi diagram with line segment obstacle is the development of the city Voronoi diagram , which is based on a plane distance L1 and requires the traffic line is on the level or vertical and a model which can pass in and out the traffic net freely . However , in the real world , the direct transit without obstruction id nearly impossible . Most of the traffic nets are divided by all kinds of obstruction , in which the segment obstacle is the most important and many obstacles can be handled as segment obstacles , thus , it is necessary to study the city Voronoi diagram with line segment obstacle .This test gives the definition , the nature some relative simple provement and crystal growth algorithm and its practice program , which is simple and needn't the complicated data structure . It can be used to any obstacle of different geometry figures . The test also provides some example to explain the practice of the city Voronoi diagram with line segment obstacle , which solves the problem of the division of the obstruction plane area based on the L1 distance , the traffic line on level and vertical and the consideration of the time distance. |