我正在解决一个问题 . 我想有效地平铺多边形 .

  • 多边形是随机的 . 它可以是从三角形（边数= 3）到圆形（边数=无穷大）的任何形状 . 它可以是凹的或凸的 .

  • 所有瓷砖都是固定尺寸的矩形 .

  • 所有瓷砖都具有相同的方向 .

  • 如果它使对话更容易，我们可以使用正方形作为平铺形状 .

  • 瓷砖平行/垂直于多边形的最长腿，无论如何 .

  • I 'm running in JavaScript on the browser, and I' m仅使用一个多边形 . 实际上，多边形是由用户手动生成的 .

  • 我不想在这里寻找NP难解决方案..）

  • 我只会填充一个多边形，我怀疑瓷砖计数会超过100 .

我发现了测试多边形到多边形干涉的出色参考 . 代码从Paul Bourke写的this posting,中闪闪发光 .

两个多边形之间的一般交叉测试如下：

/*
   Return FALSE if two polygon intersect.
   Polygon p1[] is of length n1 and polygon p2[] is of length n2.
   Polygons are define with vertices ordered clockwise.
*/
int PolygonPolygon(XY *p1,XY *p2,int n1,int n2)
{
   int i,j;
   // Reject if a vertex of p1 is inside p2, And visa versa
   for (i=0;i<n2;i++) {
      if (InsidePolygon(p1,n1,p2[i]))
         return(FALSE);
   }
   for (i=0;i<n1;i++) {
      if (InsidePolygon(p2,n2,p1[i]))
         return(FALSE);
   }
   // Reject any intersecting edges
   for (j=0;j<n1;j++) {
      for (i=0;i<n2;i++) {
         if (LineIntersect(p1[j].x,p1[j].y,p1[(j+1)%n1].x,p1[(j+1)%n1].y,
                           p2[i].x,p2[i].y,p2[(i+1)%n2].x,p2[(i+1)%n2].y))
            return(FALSE);
      }
   }
   return(TRUE);
}

这里给出了这些测试的支持功能：LineIntersect.c和这里：InsidePolygon.c . （更新：显然我需要稍微修改这三个函数，看看是否瓷砖是多边形的完全OUTSIDE还是与多边形相交的边缘 . 抱歉最初将它留下......不用说我必须转换它们也适用于JavaScript . ）

我在这里的问题涉及一个合理的算法来进行平铺 .

方法1（盲人领导盲人）

  • 转到多边形外边界的左上角 . 使用图块的网格布局，直到所有边界都被图块覆盖 . 测试干扰或超出范围 .

  • 如果干扰，删除瓷砖 .

  • 我必须修改此方法的交集测试以包含测试"Are all four vertices of the tile located outside of the polygon?"如果是，请删除该图块 .

方法2（滑动直至停止）

  • 选择质心为点到多边形的边界 .

  • 将瓷砖居中 . 测试干扰 .

  • 如果干扰， grab 距离质心的另一个随机点XYZ距离，再试一次 . 在不同方向尝试X次，如果失败，则再次增加半径y并再次尝试 . 如果完全没有去，叹气，并提示用户在多边形内的最大开放区域中单击鼠标 .

  • 从该点开始，向多边形最长边的中心滑动，即设置平铺边界的边界 .

我的直觉说方法2会产生更好的结果，但是就是这个用例：
tile into polygon

我似乎真的很合适 . 这是一个很好的参考，Solving the 2D Packing Problem by Rod Stephens瓷砖上有很多东西/包装一个矩形，在包装多边形时根本没有多少东西 .

有更好的算法吗？我的两种算法都有漏洞吗？以前有人来过这里吗？非常感谢 .

编辑：我收到一条评论，询问显示所需输出的图像 . 在我准备解决方案时，我在原始陈述的问题中意识到了一些错误（涉及所需的干扰测试） . 我添加了一个带有标记图块的所需输出图像，以简化接下来的对话 . 我也意识到我应该添加第三种方法 .

方法＃3，一次一条 . 滑动并检查 .

  • 从多边形最长边的左侧开始 . 添加一个磁贴，查看它是否合适，如果干扰，请将其滑动"right"直到没有干扰 .

  • 添加更多图块以完成该行 .

  • 从起始行的正上方开始下一行 . 将瓷砖推到尽可能远的地方"left" .

  • 添加更多图块以完成该行 .

  • 继续添加行，向左滑动，然后向右滑动 .

  • 所示示例的顶行有一个真正的技巧 . 瓦片＃11和＃12让人感到惊讶，我想添加了一个修改......当行结束时，你应该继续增量滑动并重新测试，直到到达多边形的外边界 .

建议的完整解决方案：

square tiles contained within a polygon

注意：我没有一种能够识别瓷砖＃13的方法，除非它只适用于使用盲运的方法一 .

algorithm polygon tile bin-packing