1

问题：

我无法生成一条穿过多边形（不一定是凸面）的随机线。这些线应该与完全随机的线（随机位置，随机角度）具有相同的分布，忽略那些完全错过多边形的线。

到目前为止我的想法：

在多边形内选择一个随机点（我已经有那个算法）并选择一个随机角度是行不通的，因为锤形物体会更频繁地穿过头部（它的面积比手柄大），其中一个完全随机的线更有可能穿过手柄。此外，角度肯定不会均匀分布。

出于同样的原因，不可能在表面内部或表面上选取两个点并生成一条穿过这两个点的线或任何类似方法。

编辑：我有两种方法可以使用，但我对其中任何一种都不完全满意。

  1. 找到一个包含多边形的圆。通过圆圈选择随机线，直到找到一条也穿过多边形的线。这基本上是我上面写的定义，只有更高的机会击中多边形。

  2. 在 n 个方向（例如 0°、10°、20° 等）上投影多边形。投影的大小与从该方向受到打击的可能性成正比。然后我选择一个方向（使用投影大小作为加权概率）。最后，我可以在角度上添加 360/n° 抖动。这应该足够近似分布，但我想知道是否有更好的方法。

Edit2 : -deleted-
我写了很多，但是在考虑了更多并发现了一些错误之后，我意识到这已经超出了我的想象。这个想法是在几个特定的​​方向上投影多边形的凸包，并找到一个函数，通过混合已知的投影来为我们提供所有其他投影。但事实证明，细节非常复杂，对我来说太多了。

4

1 回答 1

3

与图形相交的随机线的概念难以严格定义：请参阅Bertrand 悖论，了解此类概念中的歧义的一个著名示例。即使是平面中的随机线也不容易定义：您可能会尝试类似“一条以随机角度通过随机点的线”，但是如何选择随机点？平面上的点没有均匀分布。

这是一种精确定义与图形 F 相交的随机线的方法。令w (θ) 为垂直于角度 θ的图形F的宽度：

当F是一个多边形时，w (θ) 由分段正弦函数组成，具有与多边形的凸包具有对映顶点对的一样多的片段。

现在，使用p (θ) 作为概率密度函数选择一个角度 θ ，其中

p (θ) = w (θ) / ∫ w (θ) dθ

然后在区间[0, w (θ)]上均匀地选择直线的位置。

（您的方法 #2 尝试通过对少量 θ 值进行采样并构建分段常数分布来逼近p (θ)。但我们可以在没有太多额外困难的情况下获得准确的结果。）

要计算积分 ∫ <em>w(θ) dθ（以及因此p (θ)），首先找到多边形的凸包，然后使用旋转卡尺方法找到对映顶点对。在相邻的对映对之间，卡尺从 θ 0移动到 θ 1，比如说，在这个范围内w (θ) 由下式给出

w (θ) = d sin(θ − φ)

其中 φ 是对映顶点之间的连线的夹角d是它的长度，如下两图所示：

现在在 θ 0到 θ 1的范围内，不定积分为：

∫ w (θ) dθ = ∫ d sin(θ - φ) dθ = - d cos(θ - φ)

因此w (θ) 对于范围 [θ 0 , θ 1 ] 的定积分是

d (cos(θ 0 - φ) - cos(θ 1 - φ))

将所有对映点对相加，就可以计算出整个积分。

于 2013-01-22T15:30:57.423 回答