Offline algorithm for simplifying 2d maps

Question

I have a polygon 2d map of an environment and I want to simplify this map for some planning tests.

For example I want to close areas which can't be reached with the robot model, because the passage is to small.

The second problem is when i have two segments which a nearly parallel i want to set them parallel.

Can anyone tell me some algorithm names for that? That i know where i have to search?

thank you for your help.

Hunk

Answer 1

The first task is usually solved by applying Minkowski difference to your map and robot. This implies you know the profile of your robot.

For the second task common approach is to use 2D Snap Rounding. You can find a lot of papers on that topic at scholar.google.com. However it may also be helpful to take a look at Ramer–Douglas–Peucker algorithm for reducing a number of points in curve. It can not help with solving your problem, but it is useful to know about its existence.

Most likely your work is connected to Motion Planning, so I highly recommend you to read Computational Geometry by Kreweld, De Berg, Overmars and Schwarzkopf. It is classic of computational geometry. There you can find a lot about visibility graphs and motion planning.

Answer 2

Similarly to Mikhail's answer, for your first problem you can convert the map polygon into a binary image and apply a morphological dilation taking the size of the robot into account. Then, the areas separated by narrow paths will be disconnected components in the binary image.

Another approach is to divide the space into a grid and mark cells as empty or full depending on if some map line traverse them. Then thicken the boundaries according to the robot size and look for connected components from the cell where the robot is to find feasible paths.

Answer 3

You can use a delaunay triangulation of the map and travel the edges of the mesh for the shortest route.