International Journal of Fuzzy Logic and Intelligent Systems 2023; 23(3): 259269
Published online September 25, 2023
https://doi.org/10.5391/IJFIS.2023.23.3.259
© The Korean Institute of Intelligent Systems
JunTak Lee^{1}, TaeWon Kang^{2}, YongSik Choi^{2}, and JinWoo Jung^{1}
^{1}Department of Computer Science and Engineering, Dongguk University, Seoul, Korea
^{2}Department of Artificial Intelligence, Dongguk University, Seoul, Korea
Correspondence to :
JinWoo Jung (jwjung@dongguk.edu)
This is an Open Access article distributed under the terms of the Creative Commons Attribution NonCommercial License (http://creativecommons.org/licenses/bync/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
The Voronoi diagram is one of the most wellknown methods in clearancebased pathfinding. The generalized Voronoi diagram, which is derived from the Voronoi diagram, accepts a polygon as input. This study proposes a method for generating and simplifying a generalized Voronoi diagram. A generalized Voronoi diagram is generated by creating a Voronoi diagram with points representing polygons. The DouglasPeucker line simplification algorithm is used to simplify the diagram, and the Astar algorithm is used to determine the optimal path. By comparing the simplified and nonsimplified versions, we determine that the simplifying process decreases the run time while preserving most of the clearance; however, the distance inefficiency of the Voronoi diagram is not overcome. Additional research is required to determine a more distanceefficient path.
Keywords: Generalized Voronoi diagram, Path finding, DP algorithm, Astar algorithm
Path planning in a dynamic environment for autonomous robots is one of the most important tasks in robotics and is considered a core problem in modern robotics [1–4]. It aims to determine a collisionfree or distanceefficient path for a robot to reach its target location. These conflicting characteristics are defined as clearance and optimality. Focusing on clearance, the Voronoi diagram is one of the most wellknown methods because it guarantees a maximum clearance [4].
A Voronoi diagram is a partition of a plane, and each partition is called a Voronoi polygon and is associated with a unique point [4]. These convex polygons are called Voronoi polygons [5]. In local areas, obstacles are represented by polygons or line segments. The Voronoi diagram, which is generated using points, is inappropriate for these situations. A generalized Voronoi diagram (GVD) is generated using polygons [6]. Because a GVD is generated using polygons, it is suitable in obstacle contained environments. Similar to the Voronoi diagram, in which each Voronoi polygon is associated with a unique point, the Voronoi polygons in the GVD are associated with unique polygons. Because the Voronoi diagram maximizes the distance to the points, the GVD maximizes the distance to the polygons. This feature makes the GVD appropriate for clearancebased path planning in obstaclecontained environments.
Unlike the Voronoi diagram, which has straight line segments, the Voronoi polygons in the GVD consist of parabolic curved segments [7]. This requires many vertices to be represented and renders path planning inefficient. To overcome this inefficiency, utilization is required. Simplifying the line segments requires a diagram because it reduces the number of vertices. However, excessive line simplification may result in a nonoriginal deformity, and the path can intersect with obstacles. This can lead to a path planning failure because the path that intersects with obstacles is unreachable. The DouglasPeucker linesimplification (DP) algorithm provides the best perceptual representation of the original lines [8]. This approach is suitable for path planning because it results in the smallest changes in terms of the diagram shape.
The Astar (A*) algorithm is the bestfirst search algorithm and is widely used in path planning. This algorithm guarantees the optimal path in a static environment and improves the efficiency using a heuristic function [9]. In twodimensional (2D) nodebased maps, the A* algorithm uses an evaluation function to identify the next node. The evaluation function can be defined as
where
In this study, we constructed a GVD and simplified its diagram using the DP algorithm. The results of the simplified GVD are represented by nodes and their connections. To obtain the shortest path based on the simplified GVD (SGVD), we used the A* algorithm, whose heuristic function is defined as the Euclidean distance. Because the DP algorithm requires a tolerance value, we simulated multiple situations to determine a moderate value. The SGVD and GVD were compared to show differences in the clearance and performance. The minimum distance from obstacles was measured to represent the clearance of the diagram. The execution time was measured to represent the performance. To measure the efficiency, their visibility graph were compared.
A GVD can be constructed using multiple methods [1, 6, 7, 11]. However, to preserve the details and remain capable of producing any polygon, we decided to adopt a different perspective. The main idea of our method involves representing polygons using points, which is accomplished by following four steps:
1. Triangulate polygons.
2. Generate points at regular interval along the line segments in each triangle.
3. Create Voronoi diagram with the generated points.
4. Delete the nodes that exist inside the polygons.
We triangulated the polygons using Seidel’s algorithm, which triangulates polygons regardless of their concaveness and convexity [12]. We then generate points at regular intervals along the line segments of each triangle. For the polygon vertices shown in Figure 1, Figure 2 presents their conversion results.
By considering only the polygons, the generation of the Voronoi diagram fails. Therefore, a boundary is required [4]. In addition, an independent space is required for each endpoint to ensure clearance at each endpoint. This can be solved by adding endpoints to the Voronoi diagram, which generates a unique Voronoi polygon that ensures that no other polygons intersect the area. After adding all required points, we generated a Voronoi diagram using the Python SciPy library. Figure 3 shows the Voronoi diagram results.
Points in the polygon are unreachable. These points must be removed to generate a passable path. To delete unreachable nodes, determining whether each node is in the polygon is necessary. This was determined by testing the order of the points. The order of three points in the same plane can be expressed as clockwise (CW) or counterclockwise (CCW). The order of points (
If a single point
Testing only a single vertex can yield unreliable results. Therefore, every vertex in the triangle must be tested.
After specifying the nodes in the polygons, we delete them and reorganize the diagram. Consequently, the GVD can be obtained, as shown in Figure 4.
Because the DP algorithm relies only on the distance between points and lines, it uses a polyline and a tolerance
From a neighborhood perspective, nodes can be classified into three types: deadend, feature, and chained. Because the GVD does not contain independently existing nodes, we did not consider them. A deadend node is at the dead end of the diagram and has a neighbor count of one. A feature node is a diverging point in the diagram, with a neighbor count greater than 2. Finally, a chained node is in the middle of the chain, and is not a deadend or feature node, with a neighbor count of 2.
The algorithm begins by specifying the first starting node, which is a deadend node. Subsequently, a chain is created. After creating the chain, neighbors from the end node are specified as newly discovered starting nodes, and it is pushed into the starting node queue. The entire diagram can be searched by looping the procedure from creating the chain and adding newly discovered starting nodes.
The singlechain generation algorithm is executed according to the number of neighbors. Two scenarios are possible for deadend nodes: either at the end of the line or at the beginning of the algorithm. The first situation indicates that no newly discovered start nodes remain and that this is the end of the chain. Therefore, the algorithm exits. However, the second scenario should not result in the algorithm exiting, and it should continue searching for the end of the chain. Feature nodes have only one possible scenario at the end of the chain. The algorithm must terminate and notify unvisited neighbors. Finally, chained nodes have two possible scenarios. If the algorithm has visited every neighbor, it is at the end of the line, and the algorithm must exit. Otherwise, if the algorithm has visited only one neighbor, then the chain is incomplete, and the algorithm continues. Algorithms 1 and 2 show how chains were generated in this study.
After generating the chains in the diagram, we can now use the DP algorithm to simplify the polyline. Because the simplified polyline differs according to the index, we reorganized the GVD. Figure 5 show the results of the SGVD.
Because the start and end nodes are included in the diagram generation, the diagram has its own Voronoi polygon. Therefore, paths containing deadend nodes are not passed through. This renders such lines unnecessary. Therefore, we implemented a pruning procedure to eliminate such lines. Figure 6 shows the pruning procedure results.
To execute the A* algorithm, a connection must be made between the endpoints and adjacent nodes. To achieve this, the node adjacent to the endpoints must be determined. The folloing features were used to determine the corresponding nodes. We assumed that a line is created using one of the endpoints of the diagram and one of the nodes as both ends. If the node is adjacent to the endpoint, it should not intersect all lines in the diagram. Therefore, we can identify adjacent nodes by checking the intersection of line segments. The intersection of two lines (
Figure 7 shows the connecting of all adjacent nodes to each endpoint.
The algorithm starts at the start node. It then expands to its neighboring nodes. Each neighboring node calculates its evaluation function using the Euclidean distance as a heuristic function. After selecting the closest node, the algorithm repeats from the expansion stage. This loops until the goal node is reached. Algorithm 3 shows this procedure [14].
Figure 8 shows the results of searching the path using the A* algorithm.
Because the DP algorithm executes based on the
We determined that the performance increases with
To test the SGVD in various environments, we tested seven maps of various environments. Table 1 lists the characteristics of each map, and Figure 11 shows images of the maps used for testing.
Based on Maps 1–4, we tested four paths. Paths 1 and 2 were intended to cross diagonally, whereas paths 3 and 4 were intended to cross the center. Because Maps 5–7 were mazelike environments, we tested a single path with the intended endpoints. Using a 2D coordinate system on the map, we defined the lower left corner as (0, 0) and the upper right corner as (1, 1), where the horizontal axis is
Various aspects of the GVD and SGVD were compared. The minimum distance from the obstacle in the path was measured to determine the extent to which clearance was maintained. The execution time was measured to determine the extent of the performance improvement. Table 3 lists the minimum distances from obstacles measured in the experiment. For Maps 1–4, we averaged the values of all paths.
In the experiment, we observed that the computational time was reduced by simplifying the GVD. Moreover, the time reduction tends to be inversely proportional to the complexity. We determined it to be up to six times faster on lowcomplexity maps, such as Maps 1 or 5, whereas it was only two times faster on highcomplexity maps, such as Map 7. We also noticed that the minimum distance, which represents the clearance, was reduced when simplifying the diagram. In the lowcomplexity map, this decrease was less than 3%, whereas in the highcomplexity map, it was approximately 5%. On a mazelike map, the reduction reached 10%. These results indicate that clearance is affected when the complexity increases.
In terms of distance, the shortest path can be obtained using a visibility graph (Vgraph) [15]. Therefore, we compared the total distances of the paths generated on the SGVD, GVD, and Vgraph. Table 4 lists the values measured during the experiments.
As the focus was on clearance, no significant difference was observed between the SGVD and GVD methods. In addition, it was less than 1%. However, the difference between the Vgraph and the other graphs indicated that the GVDbased method was approximately 23% longer. This value appears to be similar to that of Masehian’s previous work, which showed that the Voronoi diagram method was approximately 26% longer than that of the Vgraph method [7].
In this study, we proposed the SGVD method for the clearancebased path planning problem. We successfully created an SGVD and its paths. The path generated by the SGVD is similar to that generated by the GVD, with fewer points. The comparison shows that the SGVD has positive affects the runtime efficiency without losing clearance. This is more effective for lowcomplexity maps but is still useful for highcomplexity maps. However, the distance inefficiency of the SGVD is similar to that of the GVD because the paths are similar. This shows that the distance inefficiency of the SSVD has not been overcome. Therefore, further studies are required to increase the path efficiency.
JinWoo Jung serves as (an) editor(s) of the International Journal of Fuzzy Logic and Intelligent Systems, but has no role in the decision to publish this article. Except for that, no potential conflict of interest relevant to this article was reported.
Images of maps used in the experiment: (a) Map 1, (b) Map 2, (c) Map 3, (d) Map 4, (e) Map 5, (f) Map 6, and (g) Map 7.
Table 1. Map characteristics.
Map  Characteristic 

Various polygons  
Low complexity  
Middle complexity  
High complexity  
Winding route  
Spiral route  
Maze route 
Table 2. Endpoints of each map.
Map  Start point (  End point ( 

(0.05, 0.05)  (0.9, 0.9)  
(0.05, 0.95)  (0.95, 0.05)  
(0.55, 0.05)  (0.4, 0.95)  
(0.05, 0.6)  (0.95, 0.45)  
(0.1, 0.075)  (0.1, 0.915)  
(0.05, 0.05)  (0.5, 0.5)  
(0.05, 0.93)  (0.9, 0.06) 
Table 3. Clearance and performance comparisons.
Map  SGVD  GVD  

Mindistance  %  Time  %  Mindistance  %  Time  %  
0.06896  98.1  0.219  16.4  0.07032  100  1.334  100  
0.07623  97.7  0.221  19.2  0.07806  100  1.154  100  
0.04500  94.4  0.523  18.9  0.04768  100  2.760  100  
0.02550  96.4  1.448  25.3  0.02645  100  5.716  100  
0.02793  91.2  2.076  29.3  0.03061  100  7.077  100  
0.05649  96.0  0.685  15.6  0.05884  100  4.381  100  
0.01973  91.0  5.150  46.6  0.02168  100  11.043  100 
Table 4. Comparison in terms of the total path distance.
Map  SGVD  GVD  Vgraph  

Distance  %  Distance  %  Distance  %  
1.34513  124.9  1.34772  125.1  1.07690  100  
1.25439  116.4  1.25599  116.6  1.07717  100  
1.35510  126.1  1.35997  126.5  1.07493  100  
1.47251  123.8  1.48138  124.6  1.18900  100  
5.61097  116.1  5.62432  116.4  4.83239  100  
3.61396  123.8  3.62261  124.1  2.91889  100  
4.24498  131.0  4.26918  131.7  3.24158  100  
2.69958  122.6  2.70874  123.0  2.20155  100 
Algorithm 1. Generating chains.
Find (  
GC: generate a single chain given a starting node  
 
 
 
push (−1, Find(1)) to  
 
 
 
 
append  
 
append begin of  
 
append end of  
push all  

Algorithm 2. Generating chain.
Find (  
 
 
append  
 
 
 
 
 
 
 
 
 
 
 
append  
 
append  
 
 
 
 
 
 
 
 
 
 
append  

Algorithm 3. A* Algorithm.
Find (  
 
push  
 
 
 
 
 
 
 
append  
 
 
 
push 
International Journal of Fuzzy Logic and Intelligent Systems 2023; 23(3): 259269
Published online September 25, 2023 https://doi.org/10.5391/IJFIS.2023.23.3.259
Copyright © The Korean Institute of Intelligent Systems.
JunTak Lee^{1}, TaeWon Kang^{2}, YongSik Choi^{2}, and JinWoo Jung^{1}
^{1}Department of Computer Science and Engineering, Dongguk University, Seoul, Korea
^{2}Department of Artificial Intelligence, Dongguk University, Seoul, Korea
Correspondence to:JinWoo Jung (jwjung@dongguk.edu)
This is an Open Access article distributed under the terms of the Creative Commons Attribution NonCommercial License (http://creativecommons.org/licenses/bync/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
The Voronoi diagram is one of the most wellknown methods in clearancebased pathfinding. The generalized Voronoi diagram, which is derived from the Voronoi diagram, accepts a polygon as input. This study proposes a method for generating and simplifying a generalized Voronoi diagram. A generalized Voronoi diagram is generated by creating a Voronoi diagram with points representing polygons. The DouglasPeucker line simplification algorithm is used to simplify the diagram, and the Astar algorithm is used to determine the optimal path. By comparing the simplified and nonsimplified versions, we determine that the simplifying process decreases the run time while preserving most of the clearance; however, the distance inefficiency of the Voronoi diagram is not overcome. Additional research is required to determine a more distanceefficient path.
Keywords: Generalized Voronoi diagram, Path finding, DP algorithm, Astar algorithm
Path planning in a dynamic environment for autonomous robots is one of the most important tasks in robotics and is considered a core problem in modern robotics [1–4]. It aims to determine a collisionfree or distanceefficient path for a robot to reach its target location. These conflicting characteristics are defined as clearance and optimality. Focusing on clearance, the Voronoi diagram is one of the most wellknown methods because it guarantees a maximum clearance [4].
A Voronoi diagram is a partition of a plane, and each partition is called a Voronoi polygon and is associated with a unique point [4]. These convex polygons are called Voronoi polygons [5]. In local areas, obstacles are represented by polygons or line segments. The Voronoi diagram, which is generated using points, is inappropriate for these situations. A generalized Voronoi diagram (GVD) is generated using polygons [6]. Because a GVD is generated using polygons, it is suitable in obstacle contained environments. Similar to the Voronoi diagram, in which each Voronoi polygon is associated with a unique point, the Voronoi polygons in the GVD are associated with unique polygons. Because the Voronoi diagram maximizes the distance to the points, the GVD maximizes the distance to the polygons. This feature makes the GVD appropriate for clearancebased path planning in obstaclecontained environments.
Unlike the Voronoi diagram, which has straight line segments, the Voronoi polygons in the GVD consist of parabolic curved segments [7]. This requires many vertices to be represented and renders path planning inefficient. To overcome this inefficiency, utilization is required. Simplifying the line segments requires a diagram because it reduces the number of vertices. However, excessive line simplification may result in a nonoriginal deformity, and the path can intersect with obstacles. This can lead to a path planning failure because the path that intersects with obstacles is unreachable. The DouglasPeucker linesimplification (DP) algorithm provides the best perceptual representation of the original lines [8]. This approach is suitable for path planning because it results in the smallest changes in terms of the diagram shape.
The Astar (A*) algorithm is the bestfirst search algorithm and is widely used in path planning. This algorithm guarantees the optimal path in a static environment and improves the efficiency using a heuristic function [9]. In twodimensional (2D) nodebased maps, the A* algorithm uses an evaluation function to identify the next node. The evaluation function can be defined as
where
In this study, we constructed a GVD and simplified its diagram using the DP algorithm. The results of the simplified GVD are represented by nodes and their connections. To obtain the shortest path based on the simplified GVD (SGVD), we used the A* algorithm, whose heuristic function is defined as the Euclidean distance. Because the DP algorithm requires a tolerance value, we simulated multiple situations to determine a moderate value. The SGVD and GVD were compared to show differences in the clearance and performance. The minimum distance from obstacles was measured to represent the clearance of the diagram. The execution time was measured to represent the performance. To measure the efficiency, their visibility graph were compared.
A GVD can be constructed using multiple methods [1, 6, 7, 11]. However, to preserve the details and remain capable of producing any polygon, we decided to adopt a different perspective. The main idea of our method involves representing polygons using points, which is accomplished by following four steps:
1. Triangulate polygons.
2. Generate points at regular interval along the line segments in each triangle.
3. Create Voronoi diagram with the generated points.
4. Delete the nodes that exist inside the polygons.
We triangulated the polygons using Seidel’s algorithm, which triangulates polygons regardless of their concaveness and convexity [12]. We then generate points at regular intervals along the line segments of each triangle. For the polygon vertices shown in Figure 1, Figure 2 presents their conversion results.
By considering only the polygons, the generation of the Voronoi diagram fails. Therefore, a boundary is required [4]. In addition, an independent space is required for each endpoint to ensure clearance at each endpoint. This can be solved by adding endpoints to the Voronoi diagram, which generates a unique Voronoi polygon that ensures that no other polygons intersect the area. After adding all required points, we generated a Voronoi diagram using the Python SciPy library. Figure 3 shows the Voronoi diagram results.
Points in the polygon are unreachable. These points must be removed to generate a passable path. To delete unreachable nodes, determining whether each node is in the polygon is necessary. This was determined by testing the order of the points. The order of three points in the same plane can be expressed as clockwise (CW) or counterclockwise (CCW). The order of points (
If a single point
Testing only a single vertex can yield unreliable results. Therefore, every vertex in the triangle must be tested.
After specifying the nodes in the polygons, we delete them and reorganize the diagram. Consequently, the GVD can be obtained, as shown in Figure 4.
Because the DP algorithm relies only on the distance between points and lines, it uses a polyline and a tolerance
From a neighborhood perspective, nodes can be classified into three types: deadend, feature, and chained. Because the GVD does not contain independently existing nodes, we did not consider them. A deadend node is at the dead end of the diagram and has a neighbor count of one. A feature node is a diverging point in the diagram, with a neighbor count greater than 2. Finally, a chained node is in the middle of the chain, and is not a deadend or feature node, with a neighbor count of 2.
The algorithm begins by specifying the first starting node, which is a deadend node. Subsequently, a chain is created. After creating the chain, neighbors from the end node are specified as newly discovered starting nodes, and it is pushed into the starting node queue. The entire diagram can be searched by looping the procedure from creating the chain and adding newly discovered starting nodes.
The singlechain generation algorithm is executed according to the number of neighbors. Two scenarios are possible for deadend nodes: either at the end of the line or at the beginning of the algorithm. The first situation indicates that no newly discovered start nodes remain and that this is the end of the chain. Therefore, the algorithm exits. However, the second scenario should not result in the algorithm exiting, and it should continue searching for the end of the chain. Feature nodes have only one possible scenario at the end of the chain. The algorithm must terminate and notify unvisited neighbors. Finally, chained nodes have two possible scenarios. If the algorithm has visited every neighbor, it is at the end of the line, and the algorithm must exit. Otherwise, if the algorithm has visited only one neighbor, then the chain is incomplete, and the algorithm continues. Algorithms 1 and 2 show how chains were generated in this study.
After generating the chains in the diagram, we can now use the DP algorithm to simplify the polyline. Because the simplified polyline differs according to the index, we reorganized the GVD. Figure 5 show the results of the SGVD.
Because the start and end nodes are included in the diagram generation, the diagram has its own Voronoi polygon. Therefore, paths containing deadend nodes are not passed through. This renders such lines unnecessary. Therefore, we implemented a pruning procedure to eliminate such lines. Figure 6 shows the pruning procedure results.
To execute the A* algorithm, a connection must be made between the endpoints and adjacent nodes. To achieve this, the node adjacent to the endpoints must be determined. The folloing features were used to determine the corresponding nodes. We assumed that a line is created using one of the endpoints of the diagram and one of the nodes as both ends. If the node is adjacent to the endpoint, it should not intersect all lines in the diagram. Therefore, we can identify adjacent nodes by checking the intersection of line segments. The intersection of two lines (
Figure 7 shows the connecting of all adjacent nodes to each endpoint.
The algorithm starts at the start node. It then expands to its neighboring nodes. Each neighboring node calculates its evaluation function using the Euclidean distance as a heuristic function. After selecting the closest node, the algorithm repeats from the expansion stage. This loops until the goal node is reached. Algorithm 3 shows this procedure [14].
Figure 8 shows the results of searching the path using the A* algorithm.
Because the DP algorithm executes based on the
We determined that the performance increases with
To test the SGVD in various environments, we tested seven maps of various environments. Table 1 lists the characteristics of each map, and Figure 11 shows images of the maps used for testing.
Based on Maps 1–4, we tested four paths. Paths 1 and 2 were intended to cross diagonally, whereas paths 3 and 4 were intended to cross the center. Because Maps 5–7 were mazelike environments, we tested a single path with the intended endpoints. Using a 2D coordinate system on the map, we defined the lower left corner as (0, 0) and the upper right corner as (1, 1), where the horizontal axis is
Various aspects of the GVD and SGVD were compared. The minimum distance from the obstacle in the path was measured to determine the extent to which clearance was maintained. The execution time was measured to determine the extent of the performance improvement. Table 3 lists the minimum distances from obstacles measured in the experiment. For Maps 1–4, we averaged the values of all paths.
In the experiment, we observed that the computational time was reduced by simplifying the GVD. Moreover, the time reduction tends to be inversely proportional to the complexity. We determined it to be up to six times faster on lowcomplexity maps, such as Maps 1 or 5, whereas it was only two times faster on highcomplexity maps, such as Map 7. We also noticed that the minimum distance, which represents the clearance, was reduced when simplifying the diagram. In the lowcomplexity map, this decrease was less than 3%, whereas in the highcomplexity map, it was approximately 5%. On a mazelike map, the reduction reached 10%. These results indicate that clearance is affected when the complexity increases.
In terms of distance, the shortest path can be obtained using a visibility graph (Vgraph) [15]. Therefore, we compared the total distances of the paths generated on the SGVD, GVD, and Vgraph. Table 4 lists the values measured during the experiments.
As the focus was on clearance, no significant difference was observed between the SGVD and GVD methods. In addition, it was less than 1%. However, the difference between the Vgraph and the other graphs indicated that the GVDbased method was approximately 23% longer. This value appears to be similar to that of Masehian’s previous work, which showed that the Voronoi diagram method was approximately 26% longer than that of the Vgraph method [7].
In this study, we proposed the SGVD method for the clearancebased path planning problem. We successfully created an SGVD and its paths. The path generated by the SGVD is similar to that generated by the GVD, with fewer points. The comparison shows that the SGVD has positive affects the runtime efficiency without losing clearance. This is more effective for lowcomplexity maps but is still useful for highcomplexity maps. However, the distance inefficiency of the SGVD is similar to that of the GVD because the paths are similar. This shows that the distance inefficiency of the SSVD has not been overcome. Therefore, further studies are required to increase the path efficiency.
Polygons vertices.
Generated points.
Generated Voronoi diagram.
Generalized Voronoi diagram.
SGVD result.
Pruning procedure results.
Connecting all adjacent nodes to each endpoint.
Shortest path found using the A* algorithm.
Minimum distance from an obstacle measured at various
Time spent on the algorithm at various
Images of maps used in the experiment: (a) Map 1, (b) Map 2, (c) Map 3, (d) Map 4, (e) Map 5, (f) Map 6, and (g) Map 7.
Results of Map 1: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
Results of Map 2: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
Results of Map 3: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
Results of Map 4: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
Results of (a) Map 5, (b) Map 6, and (c) Map 7.
Table 1 . Map characteristics.
Map  Characteristic 

Various polygons  
Low complexity  
Middle complexity  
High complexity  
Winding route  
Spiral route  
Maze route 
Table 2 . Endpoints of each map.
Map  Start point (  End point ( 

(0.05, 0.05)  (0.9, 0.9)  
(0.05, 0.95)  (0.95, 0.05)  
(0.55, 0.05)  (0.4, 0.95)  
(0.05, 0.6)  (0.95, 0.45)  
(0.1, 0.075)  (0.1, 0.915)  
(0.05, 0.05)  (0.5, 0.5)  
(0.05, 0.93)  (0.9, 0.06) 
Table 3 . Clearance and performance comparisons.
Map  SGVD  GVD  

Mindistance  %  Time  %  Mindistance  %  Time  %  
0.06896  98.1  0.219  16.4  0.07032  100  1.334  100  
0.07623  97.7  0.221  19.2  0.07806  100  1.154  100  
0.04500  94.4  0.523  18.9  0.04768  100  2.760  100  
0.02550  96.4  1.448  25.3  0.02645  100  5.716  100  
0.02793  91.2  2.076  29.3  0.03061  100  7.077  100  
0.05649  96.0  0.685  15.6  0.05884  100  4.381  100  
0.01973  91.0  5.150  46.6  0.02168  100  11.043  100 
Table 4 . Comparison in terms of the total path distance.
Map  SGVD  GVD  Vgraph  

Distance  %  Distance  %  Distance  %  
1.34513  124.9  1.34772  125.1  1.07690  100  
1.25439  116.4  1.25599  116.6  1.07717  100  
1.35510  126.1  1.35997  126.5  1.07493  100  
1.47251  123.8  1.48138  124.6  1.18900  100  
5.61097  116.1  5.62432  116.4  4.83239  100  
3.61396  123.8  3.62261  124.1  2.91889  100  
4.24498  131.0  4.26918  131.7  3.24158  100  
2.69958  122.6  2.70874  123.0  2.20155  100 
Algorithm 1. Generating chains.
Find (  
GC: generate a single chain given a starting node  
 
 
 
push (−1, Find(1)) to  
 
 
 
 
append  
 
append begin of  
 
append end of  
push all  

Algorithm 2. Generating chain.
Find (  
 
 
append  
 
 
 
 
 
 
 
 
 
 
 
append  
 
append  
 
 
 
 
 
 
 
 
 
 
append  

Algorithm 3. A* Algorithm.
Find (  
 
push  
 
 
 
 
 
 
 
append  
 
 
 
push 
Polygons vertices.
@~(^,^)~@Generated points.
@~(^,^)~@Generated Voronoi diagram.
@~(^,^)~@Generalized Voronoi diagram.
@~(^,^)~@SGVD result.
@~(^,^)~@Pruning procedure results.
@~(^,^)~@Connecting all adjacent nodes to each endpoint.
@~(^,^)~@Shortest path found using the A* algorithm.
@~(^,^)~@Minimum distance from an obstacle measured at various
Time spent on the algorithm at various
Images of maps used in the experiment: (a) Map 1, (b) Map 2, (c) Map 3, (d) Map 4, (e) Map 5, (f) Map 6, and (g) Map 7.
@~(^,^)~@Results of Map 1: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
@~(^,^)~@Results of Map 2: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
@~(^,^)~@Results of Map 3: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
@~(^,^)~@Results of Map 4: (a) path 1, (b) path 2, (c) path 3, and (d) path 4.
@~(^,^)~@Results of (a) Map 5, (b) Map 6, and (c) Map 7.