如何在Google地图V2上将不规则多边形分成相等的区域

Question

我正在开发一个用于农业目的的采样Glebe应用程序。在该应用程序中，用户可以通过点击地图选择一个Glebe，这将根据点击次数创建一个多边形。我能够创建该多边形并获得多边形的面积。但现在我需要将其分成相等的区域。

例如，如果多边形的面积为50平方米，则它将被分成50个1平方米的区域。在Agri Precision App中已完成相同的功能。请查看下面的图片。我需要像下面的图片一样划分多边形并显示其中的点。

为了获得面积，我使用Google Map Utilty Lib。它还具有网格聚类算法。我想要像上面的图像那样。在上面的图像中，他们将每5公顷划分一次。由于整个区域是85公顷，因此应该显示的总点数将为17个。这就是它的工作原理。

所以我的问题是：

如何根据地图上的多边形面积找到这些点，以便我可以在地图上绘制这些点？

- TheLittleNaruto

---

我看不出这17个孤立点与将四边形分成17个相等面积的瓷砖之间的联系。这个图形并不是所查询问题的解决方案，请提供更好的解释。 - user1196549

仅供参考，我已经放置了那张图片。主要问题是将多边形分成相等的面积。这正是我目前的实际需求。 - TheLittleNaruto

抱歉，但这张图片与主题无关且具有误导性。 - user1196549

对于那张无关的图片，我很抱歉。我会立即更新它。请给我一分钟。 - TheLittleNaruto

我相信这个链接可以帮到你。这是一个关于用于空间目的的算法的演示。 - Yordan Lyubenov

Answer 1

没有对地块的形状做出限制，因此以下解决方案可以通过构建星形分解来实现问题陈述。它假设多边形是凸多边形：

• 任意选择一个主顶点。

• 通过依次连接主顶点到每条边来三角剖分多边形，得到面积为A1、A2、A3...的三角形。

• 从主顶点开始绕着多边形旅行。如果第一个三角形大于所需面积（A1 > A），则在沿着边线找到一个点，使它将三角形分成所需面积的子三角形。使用剩余的子三角形（面积为A1-A）继续旅行。否则，将第一个三角形的面积从所需面积中减去并继续旅行（A现在为A-A1）。

这与将实线上的N个间隔划分为K个相等长度的间隔非常相似。

我猜星形分解可能不适合你。

- user1196549

---

谢谢Yves，你的想法非常好。我想知道如何实现与你提到的算法相同的方程式？ - TheLittleNaruto

你所需要的只是三角形面积的公式（http://en.wikipedia.org/wiki/Triangle#Using_coordinates）。而要将三角形分成给定面积的子三角形，只需按相同比例划分边缘（使用线段的参数方程式）。 - user1196549

@YvesDaoust 您的答案非常好，但如果您添加基本方程式和代码以实现该目标，那将更好，这样提问者就可以了解从何处开始。 - Chintan Khetiya

@YvesDaoust 如果您不介意，我们可以在这里讨论：http://chat.stackoverflow.com/rooms/19132/java-and-android-era - TheLittleNaruto

谢谢，我能够根据这个算法开发公式。但由于某些谷歌地图的限制，我不能完全按照我想要的方式进行。 - TheLittleNaruto

Answer 2

如果你的多边形是凸的，那么可以通过解决以下子问题来得到解答：“给定面积为A的凸多边形，找到将其分割成各自具有面积B和A-B的两部分的水平线。”

这可以通过沿着移动的水平线从上到下扫描顶点并计算覆盖面积（这形成了将多边形分解成梯形的过程）来轻松完成。在某些时候，您将超出面积B。通过当前和前一个顶点之间的线性插值，您将确定水平线的确切纵坐标。

您可以如下使用子问题的解决方案：

1）计算所需瓷砖数量的整数平方根N，让M等于此数。

2）将多边形切片N次，每次获得N个瓷砖的面积。将剩余的M-N^2个瓷砖作为余数。

3）使用垂直线切割每个切片以将最终瓷砖分离。

当瓷砖不与任何边缘相遇时，它们会具有更可接受的形状（矩形）。

- user1196549

---

同一个问题有两个答案？确定你没有忘记编辑你的答案吗？ - rekire

这是两个独立的答案。 - user1196549