How to vectorize a raster image edges into SVG paths?

Question

I'm having a lot of trouble figuring out how to convert a 2D list of points into an SVG Path representing a political map border. I have completed all parts of a 2D terrain generator, including climate simulation, rivers, lakes, rainfall, temperature, biomes, and finally territories. This last part is where the problem lies. The entire script is written in Python.

I have a list of territories, which are represented as dicts with several properties. One of which is Color, used as an ID and to output a pretty map. Another is a list of Pixels, list of Borders, and list of Neighbors. Pixels refers to all points in the territory. Territories can be thought of a polygons. They have Border pixels, which are defined as any outside (meaning not part of the Pixels list) pixel not belonging to this territory (whether it be a River, Ocean, or Unowned pixel). I also keep a list of neighboring territories.

Now, I can't store an array of ~3000 coordinates in a database efficiently when I only really need the border. I aim to draw only the world map with the borders of each territory drawn in a layer above. So I need to convert the border to an SVG Path string.

The Borders list is unordered when the generator finishes. For each border pixel, I go clockwise around the pixel and look for another, and progressively create a SVG Path string. I can't seem to efficiently parse the borders without getting stuck. Another problem is that there may be "lakes" in the middle of the Territory, and Borders are added around those as well. These don't have to be included in the path string.

Territories can also wrap around horizontally (like Google Maps for instance), splitting the territory in two.

So the final result of my algorithm would ideally be an LIST of SVG Paths, each representing individual parts of the territory polygons.

But, how do I do this efficiently? Is there another way to efficiently store a list of potentially thousands of coordinates representing the shape of the territory?

Each white line that sticks out from the coastline is a river. You can also see a lake in the middle of the lower green territory.

PS: I was unsure of a title, if a mod would like to change it.

Answer 1

The question

I have an image with multiple regions, that I need to efficiently convert to vector graphics.

The problem

This is a common non trivial problem in image processing -prepare to get your hands dirty-. I can categorize it as an image segmentation problem. The extra step you want to make is to convert it into vector graphics which is also non-trivial.

My solution is a variation of common techniques, but it's an algorithm that I just came up with, so don't expect 100% correct results. I hope it will put you on the right track..

The solution

1- At first we should detect regions and their edges (connected components).

This can be done using a region growing algorithm. Start with random points taken accross the image -or in your case from each already known region-.

Grow each point neighbors across all directions, if the pixel is within color range add them to the region. When the region reaches an edge with (given that it has a distinctive color, white for example in your image add that pixel to the region.

This way you have each region and it's edge. Since you said you already know about the regions you can only use this to add the edges for each region's list.

For different approach you may want to check this wiki page.

Three things to keep in mind when doing this step:

1. You should copy each region's pixel to a seperate image, this will make dealing with each region in the later steps more
2. you don't need a fully colored image, you can get away with grayscale.
3. A lot of the region growing can be optimized by removing the recursion but that's not easy.

2- Build a bounding box for each region.

Make sure the in the first step to keep track of the min and max pixel position.

One you detected the region build a box using min and max. This box will contain each region and it's white edges. This is an important step what we have done here and the first step is to isolate each connected component. So we can study each region separately.

How to detect the lakes ?

Using the bouding boxes. If a bounding box is contained in another then it's a lake.

I can see this step might have some edge cases, you can divide the box more. For more accuracy. more on that in the next step

3- Vectorization.

This is in my opinion the hardest part. Now we have each region and its edges bounded in a box. What you can do is subdivide the box into a grid and sort each edge pixels for each grid block counter clock wise. Once you sorted them you can convert each pixel to a point and connect them. In order to connect separate curves in every grid block, just connect it with the neighbor grid block.

Bonus Fun Fact

Because of digital image representation, images lose most visual information once the signal is digitized, your brain rocks, it will fill the information for you. Notice this image under the black arrow, you can zoom the image to specifically get my point.

Who else other than your brain can know that those 5 pixels are actually a car, see!