CODEWITHSUNDEEP
pythonrectangles
sanjay
sanjay

Reputation: 717

Calculate boundary of adjacent rectangles

I would like to obtain the outer boundary of several overlapping rectangles.

I have written a function to calculate neighbors of a given rectangle but I would like to see if there is a way to obtain the outer boundary of adjacent rectangles.

Here is what I have:

def get_neighboring_rectangles (r, rectList):
overlapDict = {}
rminX, rmaxX, rminY, rmaxY = return_bbox_of_rectangle(r)
for rectCheck,ri in rectList:
    if r == rectCheck: continue
    rcminX, rcmaxX, rcminY, rcmaxY = return_bbox_of_rectangle(rectCheck)
    for d in ['E', 'W', 'N', 'S']:
        if not ((rcmaxY < rminY or rcminY > rmaxY) or (rcmaxY == rminY) or (rcminY == rmaxY)):
            if d == 'W' and rcmaxX == rminX:
                if d not in overlapDict: overlapDict[d] = []
                overlapDict[d].append((rectCheck,ri))
            if d == 'E' and rcminX == rmaxX:
                if d not in overlapDict: overlapDict[d] = []
                overlapDict[d].append((rectCheck,ri))
        if not ((rcmaxX < rminX or rcminX > rmaxX) or (rcmaxX == rminX) or (rcminX == rmaxX)):
            if d == 'S' and rcmaxY == rminY:
                if d not in overlapDict: overlapDict[d] = []
                overlapDict[d].append((rectCheck,ri))
            if d == 'N' and rcminY == rmaxY:
                if d not in overlapDict: overlapDict[d] = []
                overlapDict[d].append((rectCheck,ri))
return overlapDict

The above program returns the neighbors for each direction: E,W,N,S.

Here is the cases that this function covers:

Adjacent rectangle in S direction

The function only returns what is the immediate neighbor but I want to have a functionality to return the outer boundary of all abutting rectangles:

Abutting rectangles

In this case, the input would be a list of the boundaries of all 3 rectangles:

[[(0,0) (7,0) (7,4) (0,4)] [(4,4) (7,4) (7,6) (4,6)] [(1,6) (7,6) (7,10) (1,10)]]

Expected output - [(0,0) (7,0) (7,10) (1,10) (1,6) (4,6) (4,4) (0,4)]

Also, please note that there could be a fourth rectangle that is not abutting the 3 rectangles above. The boundary of the fourth should ideally be returned as it is. (I can accomplish using my neighbor detecting algorithm)

I am a little lost as to how I can approach this problem. Is there a Python library that has this kind of functionality?

Upvotes: 0

Views: 499

Answers (1)

ewcz
ewcz

Reputation: 13087

I don't know if you insist on a custom solution, but if not, then perhaps the shapely package could provide a practical tool to approach this:

from shapely.geometry import MultiPolygon, Polygon, box
from shapely.ops import unary_union

L = [box(0, 0, 7, 4), box(4, 4, 7, 6), box(1, 6, 7, 10), box(100, 100, 110, 110)]
P = unary_union(L)
if P.geom_type == 'Polygon':
    P = MultiPolygon([P])

for Q in P:
    print(list(Q.exterior.coords))

This gives:

[(110.0, 100.0), (110.0, 110.0), (100.0, 110.0), (100.0, 100.0), (110.0, 100.0)]
[(7.0, 4.0), (7.0, 0.0), (0.0, 0.0), (0.0, 4.0), (4.0, 4.0), (4.0, 6.0), (1.0, 6.0), (1.0, 10.0), (7.0, 10.0), (7.0, 6.0), (7.0, 4.0)]

Here, L contains a list of rectangles (boxes) from your question together with one which doesn't touch any of the others. The function unary_union calculates an union of all of them so in general, the result is a MultiPolygon the components of which are easily accessible as shown in the code above. You could then filter the component which for example contains your reference rectangle, etc.

Upvotes: 2

Related Questions