计算 Google 地图上的多边形内有多少特定大小的形状

Question

我希望用户在 google 地图上绘制一个多边形形状 - 这不是问题并已将其排序。然后当用户单击一个按钮时，我需要计算出这个多边形内可以容纳多少个特定大小的矩形。

我遇到的问题是，如果多边形是例如 6m x 4m，而需要适合的形状是 2m x 3m，那么您只能适合 3 个形状（如果形状并排，则面积总计 6m x 3m侧）并留下 6m x 1m 的区域。

剩余面积与形状面积相同，但大小不对

如何查看多边形内有多少 "whole" 个形状？

我会上传一张图片来说明我的意思

Answer 1

这实际上是一个难题 packing problems 完整解决方案的特定情况会变得非常复杂，可能是 NP-hard。

导出次优解应该相当容易。我们可以考虑两种可能的解决方案，将矩形水平或垂直放置在一个统一的网格中。

设大矩形的大小为A X B，小矩形的大小为a X b。对于未旋转的版本，我们可以水平放置 m=floor(A/a)，垂直放置 n=floor(B/b)，总共放置 n*m 个项目。旋转 90º，我们有 p=floor(A/b) 和 q=floor(B/a)总共 p*q 项。

有些上面没有给出最佳解决方案，比如将 2X3 矩形放入 5 X 4。如果两个水平，一个垂直，那么你可以放入 3 英寸。

对于不规则多边形边界，您可以将它们排成行，每行之间的距离等于较小矩形的高度。

伪代码解决方案可能会像

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)
    }
}

计算 Google 地图上的多边形内有多少特定大小的形状

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

google-maps

math

geometry

shape