9

我正在寻找一种算法来在多边形内生成均匀分布的点。

这是场景：

我有一个多边形，由每个点的角（x，y）处的点的坐标指定。而且我有在多边形内生成的点数。

例如，假设我有一个包含 5 个点的多边形： (1, 1) ; (1, 2) ; (2, 3) ; (3, 2) ; 和 (3, 1)

我需要在该多边形内生成 20 个等距的点。

注意：某些多边形可能不支持均匀分布的点，但我希望以一种尽可能一致地覆盖多边形所有区域的方式分布点。（我的意思是我不想要一个分数比另一个多的部分）

有没有算法可以做到这一点？或者图书馆

我正在开发一个 C# 应用程序，但任何语言都可以，因为我只需要算法并且可以翻译它。

非常感谢您的帮助

4

7 回答 7

14

我使用的简单方法是：

  1. 对多边形进行三角剖分。剪耳是完全足够的，因为您所需要的只是将多边形分解成一组不重叠的三角形。

  2. 计算每个三角形的面积。从每个三角形中采样与该三角形相对于整体的面积成比例。每个样本只需一个统一的随机数。

  3. 一旦确定一个点来自给定的三角形，就在三角形上均匀采样。这本身比你想象的要容易。

所以实际上这一切都归结为如何在三角形内采样。这很容易做到。一个三角形由 3 个顶点定义。我称它们为 P1、P2、P3。

  1. 选择三角形的任何边。生成一个沿该边缘均匀分布的点 (P4)。因此，如果 P1 和 P2 是相应端点的坐标，则如果 r 在区间 [0,1] 上均匀分布，则 P 将是沿该边缘的均匀采样点。

    P4 = (1-r)*P1 + r*P2

  2. 接下来，沿 P3 和 P4 之间的线段进行采样，但这样做不均匀。如果 s 是区间 [0,1] 上的均匀随机数，则

    P5 = (1-sqrt(s))*P3 + sqrt(s)*P4

r 和 s 当然是独立的伪随机数。然后 P5 将被随机采样，在三角形上均匀。

好消息是它不需要拒绝方案来实现，所以长而细的多边形不是问题。而对于每个样本，成本只是需要为每个事件生成三个随机数。由于剪耳是相当简单的完成并且是一项高效的任务，因此采样将是有效的，即使对于看起来令人讨厌的多边形或非凸多边形也是如此。

于 2012-06-24T16:04:04.750 回答
4

一个简单的方法是：

  1. 计算边界框
  2. 在该框中生成点
  3. 丢弃不在感兴趣多边形中的所有点

这种方法会产生一定数量的浪费点。对于三角形，它永远不会超过 50%。对于任意多边形，这可以任意高，因此您需要查看它是否适合您。

对于任意多边形，您可以首先将多边形分解为三角形，这样您就可以得到保证的浪费点上限：50%。

对于等距的点，从空间填充曲线生成点（并丢弃不在多边形中的所有点）。

于 2012-06-24T15:27:08.543 回答
2

您可以使用劳埃德算法：

https://en.m.wikipedia.org/wiki/Lloyd%27s_algorithm

于 2020-02-26T21:51:09.857 回答
1

您可以尝试 {spatialEco} 包（https://cran.r-project.org/web/packages/spatialEco/index.html）并应用功能 sample.poly （https://www.rdocumentation.org/packages /spatialEco/versions/1.3-2/topics/sample.poly )

你可以试试这段代码：

library(rgeos)
library(spatialEco)

mypoly = readWKT("POLYGON((1 1,5 1,5 5,1 5,1 1))")
plot(mypoly)
points = sample.poly(mypoly, n= 20, type = "regular")
#points2 = sample.poly(mypoly, n= 20, type = "stratified")
#another type which may answer your problem
plot(points, col="red", add=T)
于 2020-11-16T10:28:45.463 回答
0

简单的答案来自一个更简单的问题：如何从均匀分布中生成给定数量的随机分布点，这些点都适合给定多边形内？

简单的答案是：找到多边形的边界框（假设它是 [a,b] x [c,d]），然后继续生成实数对，一个来自 U(a,b)，另一个来自U(b,c)，直到你有 n 个坐标对适合你的多边形。这很容易编程，但是，如果您的多边形非常锯齿，或者很薄且倾斜，则非常浪费和缓慢。

为了获得更好的答案，找到最小的旋转矩形边界框，并在转换后的坐标中执行上述操作。

于 2012-06-24T17:57:04.337 回答
-2

  1. 遗传算法可以相当快地做到这一点参考
    遗传算法用于具有几何约束的图形布局

  2. 你可以使用 Force-Directed Graph 来解决这个问题......
    看看http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
    它绝对会让你大吃一惊。

我从来没有尝试过，
但我记得有可能为图中的某些顶点设置修复

你的算法最终会像

  1. 创建图 G = V 中顶点的闭合路径
  2. 将顶点固定到位
  3. 将 N 个顶点添加到图形中，并将它们与具有相等张力值 1.0 的边完全连接
  4. Run_force_graph(G)

将图缩放到有界框

虽然它不是绝对的，因为一些凸形可能会产生奇怪的结果（拿一颗星）

最后：没读过，但标题和摘要似乎相关，
请查看 Consistent Graph Layout for Weighted Graphs

希望这可以帮助...

于 2012-06-24T16:00:16.593 回答
-4

更好的答案来自更好的问题。假设您要放置一组 n 个瞭望塔来覆盖一个多边形。您可以将其视为一个优化问题：找到 n 个点的 2n 个坐标，以最小化适合您目标的成本函数（或最大化价值函数）。一个可能的成本函数可以为每个点计算到其最近邻居或多边形边界的距离，以较小者为准，并计算该序列的方差作为“不均匀性”的度量。您可以使用如上所述获得的一组随机 n 点作为初始解决方案。

我在某本书中看到过这样的“瞭望塔问题”。算法、微积分或优化。

@Youssef：抱歉耽搁了；一个朋友来了，网络中断了。

@others：有一些耐心，不要那么高兴。

于 2012-06-24T18:10:06.470 回答