I'm trying to implement the Explicit Corridors method to generate a navmesh for a large city. The algorithm takes a list of convex polygons representing the obstacles as input.

The paper only briefly describes the process of obtaining this "footprint". It looks like all the obstacles are rendered in a texture with an orthographic projection, and then each obstacle is decomposed in convex polygons. They use the CGAL library to do this, but I want do it on my own.

Here's an example of the footprint. Ignore the lines between buildings, but notice how each building (in red) is segmented in convex polygons.

enter image description here

So what I'm looking for is an algorithm that takes an image as input, and gives me a list of segments representing the contour of each shape.

I checked stuff like Harris corner detection, but I'm not sure if this is the best way to do it. I also looked at Delaunay triangulation, but this will create a lot of unused segments (the ones you see inside the buildings in the picture above).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.