CODEWITHSUNDEEP
google-mapsmathgeometryshapes
john avison
john avison

Reputation: 56

Calculating how many shapes of specific size fit inside polygon on Google Maps

I would like the user to draw a polygon shape on google maps - this isnt an issue and have this sorted. When the user then clicks a button, I need to work out how many rectangular shapes of a specific size will fit inside this polygon.

The issue I have is if the polygon is for example 6m x 4m and the shape that needs to fit is 2m x 3m, then you can only fit 3 shapes (area totalling 6m x 3m if the shapes are side by side) and leaves 6m x 1m area remaining.

The remaining area is the same area as the shape, but its the wrong size.

How do I see how many "whole" shapes fit inside the polygon?

I will upload an image to show what I mean enter image description here

Upvotes: 1

Views: 6987

Answers (1)

Salix alba
Salix alba

Reputation: 7824

This is actually a difficult problem a particular case of a packing problems a full solution would turn out to be quite complex, possibly NP-hard.

It should be fairly easy to derive a sub-optimal solution. We can consider two possible solutions with the rectangles horizontal or vertical with them in a uniform grid.

Let the size of the big rectangle be A X B and the small rectangle be a X b. For the unrotated version we can fit m=floor(A/a) horizontally and n=floor(B/b) vertically giving a total of n*m items fitted in. Rotating by 90º we have p=floor(A/b) and q=floor(B/a) with a total of p*q items.

There will be some which the above does not give the best solution, say a fitting 2X3 rectangles into 5 X 4. If two are horizontal and one is vertical then you can fit 3 in.

For an irregular polygon boundary you could arrange them in rows with the distance between each row equal to the height of the smaller rectangles.

A pseudocode solution might work something like

poly = getPolygon() // get the input polygon
a = rectangle.height // size of rectangle we are trying to fit
b = rectangle.width  // size of rectangle
row_height = 10
bounds = poly.getBoundingBox()
offset_top = a/2 // y coord of the first row

// loop from top to bottom
for(y = bounds.top + offset_top ; y < bounds.bottom; y += a )
{
    // find all the solutions of the polygon with a horizontal line
    sols1 = poly.intersectWithHorizontalLine(y)

    // find sols of bottom line
    sols2 = poly.intersectWithHorizontalLine(y+a)

    // find the left most and right most points
    left = min(sols1,sols2) 
    right = max(sols1,sols2)

    // now can draw the rectangles
    for(x=left; x < right; x += b)
    {
        drawRectangle( x , y, width=b, height=a)
    }
}

Upvotes: 4

Related Questions