search

vleue / polyanya

Pathfinding using Polyanya
Apache License 2.0
280 stars 20 forks source link

Rules about valid polygons? #19

Closed vultix closed 1 year ago

vultix commented 1 year ago

I'm curious about what are the requirements for a given polygon.

To clarify, why not just create a single polygon containing all of the points for the example in the README? I presume this is invalid somehow.

Polygon::new(vec![0, 1, 9, 5, 22, 6, 7, 8, 10, 15, 18, 19, 16, 17, 20, 21, 11, 13, 14, 12, 2, 3, 4], true)

image

Meyermagic commented 1 year ago

A general requirement of Polyanya is that the polygons be convex, so that within a single polygon you can navigate from any point to any other point in a straight line, knowing that it is the shortest path and will not cross into any non-traversable area.

Without pre-processing to decompose the polygons into convex polygons, this library shares that requirement.

vultix commented 1 year ago

That makes perfect sense, thank you!