This repo contains the source code for my shortest path algorithm project. This project involves concepts from vector analysis, computational geometry, and graph theory which are used to create an algorithm for finding the shortest path through a set of planar Cartesian coordinates. I plan to fully develop this algorithm in the hopes of finding a polynomial time solution to the traveling salesman problem.
This project builds off of the principles of vector analysis I explored pixarninja/contour_construction_algorithm, which is an algorithm that generates garunteed shortest paths given that the datapoints are arranged in a convex shape.
This shortest path algorithm was created to aide in my solution for the 3D geometric reconstruction of object data from sparse point-clouds. There already exist algorithms to generate mesh from point-clouds, however the object is not generated correctly in the case of sparse data. It is my theory that the best possible reconstruction of any given point-cloud will be the most convex planar mesh that can be generated from a given contour of the point-cloud; these contours would then be joined together to create the reconstructed 3D object. My study of this conjecture has lead me to also theorize that this shape is in fact the shortest halmotonian path for each planar contour.
cmake .
make
./shortest_path -f <datapoint_file> [-o <output_file>]
Use the run_tests.sh
script to generate random test files
and plot the segments generated from the shortest_path
and
brute_force
executables for comparison. The number of points to generate
for each file is hard-coded at 10 to provide feasible random test cases.
Alternatively, you can enter one of the following files containing pre-defined datapoint information to run the algorithm on and plot the segments:
- 2000.dat
- 1000.dat
- 500.dat
- 50.dat
- arrow.dat
- bigstar.dat
- bird.dat
- box.dat
- butterfly.dat
- c.dat
- center.dat
- circle.dat
- complex.dat
- donut.dat
- ellipse.dat
- flyingfish.dat
- frog.dat
- glob.dat
- halfbigstar.dat
- halffrog.dat
- halfkey.dat
- halfnested.dat
- halfseaweed.dat
- key.dat
- nested.dat
- offcenter.dat
- overlap.dat
- pill.dat
- random.dat
- seaweed.dat
- simple.dat
- square.dat
- star.dat
- test.dat
- threecircles.dat
- tree.dat
- triangle.dat
- two_circles.dat
Please note: the GNUplot plotting utility must be installed for the path to be plotted.
I need to finish implementing the algorithm; currently, the algorithm calculates "optimal shapes" within a set of datapoints. I will complete my work on creating these optimal shapes, and then implement an algorithm that connects them using Dynamic Programming.