# A Topology Map Generation Algorithm for Optimal Path Finding for Image-Based Maps
## 3 Corner Node Algorithm
### Node Connection  
The algorithm uses vector subtraction to connect nodes. The equation below describes the vector subtraction performed on any two vectors separated by (x,y) from zero:  
\[\overset{\rightarrow}{OA}-\overset{\rightarrow}{OB}=\overset{\rightarrow}{BA} \tag{4}\]  
As in the above equation, by performing subtraction on two vectors, a vector connecting the two vectors can be generated. Therefore, using the coordinate of the node to generate a vector separated by (x,y) from the zero point, each node can be connected in a straight line, as shown in Figure 5.  
Figure 4: Node creation process. (**a**) Select one of the obstacle data lists, and then select free space data adjacent to the diagonal direction. (**b**) Select node 10 and search for adjacent data. (**c**) Create a node in the detected corner. (**d**) Select node 2 in the adjacent data, and search for the adjacent data for node 2. (**e**) Select node 12 in the adjacent data and search for adjacent data for node 12. (**f**) Corner detection is now complete for this obstacle. Algorithm 1 is pseudocode for corner detection and node generation. ```
mapData[][] = data in 2-dimension array wallList[] = obstacle data PathNodeList[] = a list containing the generated nodes direction = [North, Northeast, East, Southeast, South, Southwest, West, Northwest] diagonalDirection = { Northeast, Southeast, Southwest, Northwest } for wallList.begin to wallList.end do if more than one of the data points of the wallList did not participate in the corner detection process, then  Execute 'Generate node based on the obstacle data' endif endfor function 'Generate node based on the obstacle data { for i = 0 to 4 do if Point(x,y) of direction diagonalDirection[i] == 'Free space' then  Execute 'Detect corner node' endfor } function Detect corner node {  wallCount = 0 for i = 0 to 8 do if Point(x,y) of direction direction[i] == 'obstacle' then  wallCount += 1 endif  if wallCount == 1 then  Create node at Point(x,y)  Add node to PathNodeList endfor }
```  
**Algorithm 1**Pseudocodes for corner detection and node generation  
By normalising the newly created Vector 3, Vector 4 with only a direction value for the target node can be generated, as shown in Figure 6.  
Figure 5: Result of vector subtraction between two vectors. The generated Vector 4 determines whether the start node and target node can be connected in a straight line. The scalar product process is repeated until multiples of Vector 4 (shown as green arrows in Figure 7) connect with the target node. As shown in Figure 7a, if an obstacle other than the target node is encountered on the way, the algorithm determines that the two nodes cannot be connected. The algorithm connects the two nodes when Vector 4 reaches the target node without encountering an obstacle. At this time, Vector 4 may be used by adjusting the size by a \(k\) multiple. As \(k\) decreases, the obstacle recognition accuracy increases. Conversely, as \(k\) increases, the accuracy decreases, but the speed increases. We recommend using a \(k\) of 1 because when \(k>1\), as shown in Figure 8, adjacent data may cross. Figure 8: Comparison between \(k=1\) and \(k=2\). Figure 6: Result of vector normalisation: (**a**) result of vector subtraction between Node 1 and Node 2; and (**b**) result of Vector 3 normalisation. Figure 7: Connecting two nodes: (**a**) when there is an obstacle between Nodes 1 and 2, (**b**) when there is no obstacle between Nodes 1 and 2, and (**c**) the result of connecting the nodes. Figure 9 shows a scenario in which overlapping paths may be generated when multiple nodes are placed on a straight line. In Figure 9a, it is possible to generate a connection even though the movement paths overlap, because the node lies on a vertical line. However, in Figure 9b, when a node is recognised as an obstacle, it is possible to prevent a connection that creates a duplicate path. The algorithm is terminated when all nodes have been processed for node connectivity. Each node has connected node information and a weight (linear distance).