Basic RobotPathFinding

Path planning (with space configuration) algorithms (Trapezoid decomposition, Visibility graph and QuadTree)

• All algorithnms implemented in the project are using naive implementation. Further requirement needed to optimize and correctly finish trapezoid decomposition.
• After finding configuration space and setting starting and ending points inside the space you are able to run DFS, BFS, Djisktra and AStar algorithms to find the path.
• Maximum vertices for each osbstacle is 5 (you can change it)
• I'm using shortest euclidean distance to connect the start, end nodes. For better results you would add these in the graph.
• Project is written in Croatian/Bosnian/Serbian, all variables are set with that in mind.

TODO

• More efficient implementation (faster time complexity with sweep-line and radial sweep)
• Check if the start/end can be directly linked before the path finding algorithms
• Adjust how start/end are inserted (during the creation of the graph)

Visibility graph

Quadtree with all path algorithms

Generating obstacles

Trapezoid decomposition graph (needs further work, optimizing algorithm might help)

Trapezoid decomposition process

Trapezoid decomposition path with Djikstra

Quadtree process