Any angle pathfinding : how to cover a non-grid shape

Hello everyone.

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 ?
  • If not, how would you do this ?

Thank you for your help.


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.

1 Like

Hello, thank you for your answer.

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.