I'm really quite annoyed that algorithms described in papers do not have open implementations (the researchers don't give away their test code) or the implementations cannot be found or are unintelligible. So I'm going to provide "semi-canonical" implementations of some algorithms that interest me. And if you want the code, it should be available in vlib (available for download in the Software section) sometime soon, or as a separate download.
Of course, part of the problem in implementing algorithms is find the proper data structures. I'll provide those here too.
Data structures
- Generic graph (abandoned in favor of Boost graph library)
Pathfinding
- A* (Dijkstra's shortest path with heuristic)
- Overmars and Welzl (visibility graph computation) [OW88]
References
- [OW88]Overmars, M. H., and E. Welzl, New methods for constructing visibility graphs, in Proceedings of the 4th Annual ACM Symposium on Computational Geometry, Urbana, IL (1988), pp. 164-171.