algorithm - 如何将一个矩形分成大小相等的部分，每个部分都连接到周边？

Question

我在 map reduce 设置中执行 Viewshed 算法并考虑了一个非常可靠的算法 ( http://www.geoinfo.info/proceedings_geoinfo2013.split/paper9.pdf )，为了让它工作，我需要在以下算法的行中包含一些内容，我将解释现在:

输入:所需区域的数量N，一个栅格(只是一个矩阵)R，以及栅格/矩阵中的一个点P

输出:N个区域，每个区域都是一个多边形(三角形或4角多边形)，其中一个角在P，其他角连接到R 的周长。

让我给你举个例子:

输出可能是这样的，其中 P 位于中心:

显然 P 不需要位于中心。

有人知道这方面的任何好的算法吗？

Answer 1

一般的算法可以是这样的:

• 求出 N 个多边形中每一个的面积(显然是 R 除以 N 的面积)
• 创建从 P 到 R 左上角的垂直线段
• 将这条线段作为新多边形的第一条边沿R边界以给定的小步顺时针移动并计算新多边形的面积
• 如果面积接近于每个多边形的面积，则创建它
• 使用最后一条边作为新多边形的第一条边并重复。

如果您需要完美的精度，您还可以计算新点的确切位置，因为您拥有所有必要的数据。这些多边形中的每一个都是凸的，可以分割为多个三角形。

下面是一些插图，希望对您有所帮助: