1

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: Countour of each of the world countries

  1. From here i filled each of these countries with an random color like this: Filled World map

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.

Drawing generated polygons

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!

Per Arne Andersen
  • 494
  • 5
  • 17
  • have you considered creating a svg image? You would specify the contour lines, indicate that they should form a closed curve and be filled with a color of your choice. – collapsar Feb 05 '15 at 18:00
  • I can sadly not use SVG in my application, But could the SVG give me desired result automaticly, or would i have to define these manually? – Per Arne Andersen Feb 05 '15 at 18:02
  • the color-fill would be produced automatically (just add a `fill` attribute to your contour polyline ). – collapsar Feb 05 '15 at 18:07
  • Which countries did disappear? Were they swallowed by others or did they remain uncolored? Of course you will never match everything, e.g.: islands to their mainlands.. – TaW Feb 05 '15 at 18:16
  • Primarily Russia dissapeared. We had some troubles following the countour lines because some countries have lines that would create a endless loop. We solved this by backtracing stepes and selecting a alternative route (Avoiding this loop). Im not sure why russia dissapeared, But im primarily looking for a algorithm which is known to solved the problem im facing :) – Per Arne Andersen Feb 05 '15 at 18:27

1 Answers1

4

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.

Spektre
  • 49,595
  • 11
  • 110
  • 380