🔒 How to extract polygons from image

[sand sandal]

I have this map of Europe and I need to grab each province individually and make a Province object of them, with the list of points stored within each object. Currently I have a script that can get all points that are neighboring different colors. But I don't know how to go from here.

def getNeighboringPixels(x, y, width, height):
    neighbors = []
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height and (dx, dy) != (0, 0):
                neighbors.append((nx, ny))
    return neighbors

def generatePoints(image_path):
    points = []
    image = p.image.load(image_path)
    width = image.get_width()
    height = image.get_height()
    for y in range(height):
        for x in range(width):
            pixel = image.get_at((x, y))
            neighboring_pixels = [image.get_at(pos) for pos in getNeighboringPixels(x, y, width, height)]
            if any(pixel != neighbor for neighbor in neighboring_pixels):
                points.append([x, y])

    return points

I am using pygame

[vapid flicker]

@sand sandal

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[jovial marlin]

Try flood fill?

[sand sandal]

I'll look into it

[jovial marlin]

Basically, loop through every pixel, if it hasn't already been painted, start a flood fill there

[unborn moth]

you flood fill with increasing integer values, this way you can extract segments by value and get contours

[sand sandal]

I'm pretty sure I get the main idea of the different methods to flood fill, but I'm struggling to understand:

• What I need to get out of a flood-fill function (list of points?)
• How I would use that to separate each region as a separate object

[jovial marlin]

The flood fill algo will return nothing, instead we're looking for the side effects - painting a region, which leads to your second point
This "paint" can be an int like tunecx briefly mentioned
A very high level overview might look something like this

paint: list[list[int]] # same size as the image, where paint[x][y] will denote which region that pixel belongs to; We'll use an int for this, and two points (a, b) and (u, v) belong to the same region if paint[a][b] == paint[u][v]

def flood(start: tuple[int, int], color: int):
    'paints the region that includes the starting point'

color = 1
for y in range(height):
    for x in range(width):
        if not paint[x][y]:
            flood( (x, y), color)
            color += 1

At the end, paint should look something like

[
    [1, 1, 1, 2, 2, 2],
    [1, 2, 2, 2, 2, 2],
    [2, 2, 2, 3, 3, 3],
]

Where the same numbers mean 1 region. E.g. in the above map, there's three regions, that looks like this

Region 1:
###...
#.....
......

Region 2:
...###
.#####
###...

Region 3:
......
......
...###

[sand sandal]

Ah I see

[sand sandal]

Could you just explain what the first paint exactly is? I don't quite get it. Also did you mean to have the same name for the nested list and the function parameter?

[jovial marlin]

oops, didn't realize that there's a name clash

[jovial marlin]

The first paint (2d list) should be the

[
    [1, 1, 1, 2, 2, 2],
    [1, 2, 2, 2, 2, 2],
    [2, 2, 2, 3, 3, 3],
]

[sand sandal]

and how would I know what it is?

[jovial marlin]

You initialize it with something like

[
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
]

Then in this loop, we check every pixel for if it has been painted or not. If not, we start a flood fill:

for y in range(height):
    for x in range(width):
        if not paint[x][y]:  # <--
            flood( (x, y), color)
            color += 1
```So if we use the example map, then your code should call `flood` 3 times in total, and these are what `paint` will look like after each call:

[
[1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
]

[
[1, 1, 1, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[2, 2, 2, 0, 0, 0],
]

[
[1, 1, 1, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[2, 2, 2, 3, 3, 3],
]

[sand sandal]

ah right

I will try to make it now

[vapid flicker]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.