Python - geospatial vector problem
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

We have an image and on top of it we have some boxes we have mapped on top of the image. We want to subtract the good from the bad and just have the remaining bad part left. Ideally the output of your python lib is the line polygon left remaining. This reminds me of a geojson type of issue or some spatial analysis but we are looking for a simple elegant solution.

Here an example of the “good” and “bad” visually. In your code you could assume they are polygons as well.

So to recap we have an image along with a number of polygons, some polygons are good and some bad. We want your code to output the bad after the good has been removed. I think output could be expressed like this

I need lines that are (if walking clockwise):

(x1,y1) to (a1,y1)
(a1,y1) to (a1,b2)
(a1,b2) to (x2,b2)
(x2,b2) to (x2,d1)
(x2,d1) to (c1,d1)
(c1,d1) to (c1,f1)
(c1,f1) to (x1,f1)
(x1,f1) to (x1,y1)

Thx for the list. I’ll comb through these Monday and see which solutions we ended up using. The gap is because by the time we get the concept snippet in to production code I’ve usually not come back to award. Thx for the reminder. I need to get better at that.
Qdev 1 month ago
awarded to CyteBode

Crowdsource coding tasks.

1 Solution

Winning solution


Python Script

from Polygon import *

def add_and_sub(to_add, to_sub):
    to_add = set(Polygon(poly) for poly in to_add)
    to_sub = set(Polygon(poly) for poly in to_sub)

    # Merge the good polygons that overlap together,
    # but keep them separate otherwise
    added_polys = []
        poly = to_add.pop()

        to_remove = set()
        for other in to_add:
            if poly.overlaps(other):
                poly = poly | other
        to_add = to_add.difference(to_remove)


    # Remove the bad polygons from the good merged polygons
    subbed_polys = []
    for poly in added_polys:
        for other in to_sub:
            poly = poly - other
        assert(int(poly.orientation()[0]) != 0)

    # Reverse the polygons if they're not clockwise
    return [list(poly)[0][::int(poly.orientation()[0])]
            for poly in subbed_polys]

def rectangle(a, b):
    x1, y1 = a
    x2, y2 = b
    return [(x1, y1), (x2, y1), (x2, y2), (x1, y2)]

def main():
    from PIL import Image, ImageDraw

    def draw_polygons(size, to_add, to_sub = []):
        image ="RGB", size, "white")
        draw = ImageDraw.Draw(image)

        for poly in to_add:
            draw.polygon(poly, "rgb(200, 0, 0)", "rgb(0, 0, 200)")

        for poly in to_sub:
            draw.polygon(poly, "rgb(0, 200, 0)", "rgb(0, 0, 200)")

        return image

    def bounty_test():
        w , h  = 360, 324
        x1, y1 =  58,  84
        x2, y2 = 240, 212
        a1, b1 = 103,  20
        a2, b2 = 296, 122
        c1, d1 = 116, 148
        a2, d2 =  a2, 260
        e1, f1 =  28, 181
        e2, f2 = 148, 302

        to_add = [rectangle((x1, y1), (x2, y2))]
        to_sub = [rectangle((a1, b1), (a2, b2)),
                  rectangle((c1, d1), (a2, d2)),
                  rectangle((e1, f1), (e2, f2))]

        result = add_and_sub(to_add, to_sub)

        draw_polygons((w, h), to_add, to_sub).save("bounty_input.png")
        draw_polygons((w, h), result).save("bounty_output.png")


if __name__ == '__main__':

add_and_sub takes two lists of polygons, one of the good polygons that will be added together, and the other of the bad polygons that will be removed from the good polygons. The polygons are represented as lists of (x, y) points: [(x1, y1), (x2, y1), ...]. The output is a list of polygons represented the same way.

The output of bounty_test as an image:

It also works with arbitrary polygons, as long as they're well-formed. However, it doesn't work if a bad polygon is entirely surrounded by a good polygon, which should create a hole. I could add that functionality if you need it.