This shows you the differences between two versions of the page.

algorithms [2009/07/30 15:58] hadrien |
algorithms [2009/07/30 15:58] (current) hadrien |
||
---|---|---|---|

Line 30: | Line 30: | ||

A bitmap can be vectorized to simplify its use. Many algorithms exist, they will not be developped here. The main drawback of vectorization is the possibly big complexity of the resulting polygons. | A bitmap can be vectorized to simplify its use. Many algorithms exist, they will not be developped here. The main drawback of vectorization is the possibly big complexity of the resulting polygons. | ||

- | The Douglas-Peucker algorithm simplifies a polygon by removing vertices that are not too far from the global shape of the polygon. "Not to far" is defined by a parameter (commonly named epsilon). This algorithm is defined recursively, yet its implementation in hbot is not recursive, for performance and stack size purposes. There are several version of the algorithm, the most known has a complexity of O(n²) (n is the number of input vertices). | + | The Douglas-Peucker algorithm simplifies a polygon by removing vertices that are not too far from the global shape of the polygon. "Not too far" is defined by a parameter (commonly named epsilon). This algorithm is defined recursively, yet its implementation in hbot is not recursive, for performance and stack size purposes. There are several version of the algorithm, the most known has a complexity of O(n²) (n is the number of input vertices). |

|[{{:map-occupancy.png|Occupancy grid (bitmap)}}]|[{{:map-vectorized.png|Vectorized map (107 vertices)}}]|[{{:map-dpsimplified.png|Vectorized and simplified map (96 vertices)}}]| | |[{{:map-occupancy.png|Occupancy grid (bitmap)}}]|[{{:map-vectorized.png|Vectorized map (107 vertices)}}]|[{{:map-dpsimplified.png|Vectorized and simplified map (96 vertices)}}]| |