Generating Polygons from Image (Filled Shapes)

问题:

I'm trying to generate polygons from a preprocessed world map, What i have done so far is:

1: Generated a contour map for each of the countries, it looks like this:

2. From here i filled each of these countries with an random color like this:

So far ive tried to just select a random pixel in the countour image and followed the line around until i hit the start point. This did give me a relatively good result, without about 90% accuracy on the polygons, However some countries dissapeared totally.

So what i wish to do is to have a array of coordinates for each of the countries in this map in a sorted manner so it can be represented as a Polygon. Do anyone know how to achieve this?

I have not found any algorithms suited for my problem.

Thanks!

回答1:

there are vectorizing tools out there but if you want to code it (it is a hard task) do this:

1. scan image for black points

   store all points in some list of (x,y) coordinates

2. add connection info to all points

   this will need huge amount of memory if not coded properly so add grouping info to which points is each point connected (remember just indexes).

3. add usage flag to point

4. find polylines between joints

   joint is point with more then 2 connected points so

   1. find such point i
   2. go through its connected points until another join point j is hit without going twice through any point. That is why you need the usage flag. Store this path as polyline

5. find closed loops

   It is similar to #4 but you need to step through polylines to go back to the start point. Remember polylines as polygons

So you will need structures similar to this:

struct pnt
 {
 int x,y; // coordinate fo point
 int used; // usage flag for later use
 List<int> ix; // list of indexes of all points connected to this point
 };

struct polylin
 {
 List<int> ix; // list of point indexes
 };

struct polygon
 {
 List<int> lin; // list of polyline indexes
 List<int> dir; // direction of polyline (forward/backward)
 };

List<pnt> pnts;
List<polylin> plins;
List<polygon> faces;

If your image points has holes inside then you will need to handle them by additional image processing or by connected points finding with some treshold distance.