I have a pathfinding problem that I must solve, but I don’t really know how to do it. Maybe you could help me, please.
Bascially, I have a random simple closed 2D polygon. I want to find a path in that polygon for a simple shape (let us say a 9-pixels diameter circle) to cover as much as possible of the entire polygon area, while following the shortest any-angle path possible.
(Of course, the shape cannot cross the edges)
So, my questions are :
Do you know of any c++ implemented function that would allow me to do this ?
That sounds like a very hard problem… like NP-hard.
It sounds like a harder version of finding the hamiltonian path (in your example that would be sort of the same as using a 1px circle, though in your case the path can cross itself).
I am not aware of any algorithms that can solve this efficiently.
Finally, since my problem isn’t very important, I’ve approximated it by finding the convex hull of the polygon, and then I sweep it by selecting an edge and drawing parallels until the convex hull is filled.
In the real problem, the polygon isn’t convex et can have holes, but for now I will go for simple.