编程练习：铺瓷砖

已知一个多边形区域。请用正方形的瓷砖，铺满整个区域（如下图所示）：

如果你觉得不过瘾，还可以用正三角形瓷砖：

甚至用正六边形瓷砖：

你可以从中间铺，也可从角落铺；可以水平铺，还可斜着铺；只要你喜欢，想怎么铺就怎么铺。

如果你觉得不过瘾，还可以在地图上铺，让瓷砖铺满祖国的万里河山。

比如在杭州西湖区，铺六边形的砖，六通四达。

换个四边形，四平八稳。

试试三角形，三位一体。

如果你觉得不过瘾，可以把这个铺砖的方法，用来划分地盘。

有些业务场景，需要在地图上划分标准的作业单元。例如，划分共享自行车的骑行范围、快递网点的配送范围、外卖骑手的接单范围等等。

问题描述

为了便于编程实现，下面用更精确的语言描述一下这个问题。

1、已知多边形

，其顶点集合记作

：

代表被填充的区域。

2、用正

边形填充

，其中

。换句话说，要求返回一个多边形的集合

：

其中

覆盖了区域

，且两个不同的多边形不能重叠（可以有公共边，但不能有公共面积）。

3、已知初始点

，要求从

开始填充。即，第一个填充的正

边形的中心点是

。

4、已知初始角度

， 代表多边形的旋转角度（如下图所示）。

5、考虑到

的边界是不规则的，可以把

超出

边界的

取交集（效果参考前面的图片）。

算法实现

我们用 Python 实现。如下所示， 定义输入与输出； 用来设置多边形的参数。

接下来实现多边形填充算法。

从初始点开始，填充第一个多边形，然后绕着它一圈一圈地填充，直到填满整个区域。

上面代码展示了用宽度优先搜索（Breadth-First-Search）的实现思路，其中省略了部分函数的细节。

算法需要生成多边形对象，因此我们定义了一个类PolyGetter来实现相关功能。

实现细节需要用到一些初中的几何知识，请自行推导，这里我们不展开。

可视化

行政区域可以通过高德提供的 API 免费获取。值得注意的是，地理位置是球面的经纬度信息，但地图是平面。因此，我们需要做一个变换，然后应用上面的算法。

具体来说，执行如下步骤：

1、把球面坐标投影到平面上，得到平面上的多边形区域

；

2、用上述算法对

进行填充，得到多边形的集合

；

3、把

中的坐标映射成球面的经纬度；

下面的函数可以做上述变换。

最后用高德提供的数据可视化 API 做个小前端，用来展示结果（需要一点点 Html 和 JavaScript 知识）。

【回复铺瓷砖获取完整代码】

镶嵌的艺术

你如果觉得不过瘾，可以搜索关键词密铺、多边形镶嵌。

然后你会看到让人眼花缭乱的铺砖方式，比如这些（图片来自维基百科）。

如果你觉得不过瘾，可以试着找一个五边形，然后用它填满整个平面，像下面这样。

有趣的是，迄今为止（据我所知），数学家一共只找到上图所示的15种五边形。最新的进展在2015年，Mann、McLoud 和 Von Derau 用计算机发现了第15个五边形。

如果你觉得不过瘾，还可以研究希尔伯特二十三问中的第十八个问题：用全等多面体构造空间。

详细内容不展开，因为我不懂，这里只为铺砖引玉。

作为码农，搬砖是基本功，铺砖是加分项。铺得一手好砖，躺平的时候才舒服。