矩形中的任意二维点,但不包含在多边形中

我有一个静态矩形和dynamic多边形。 我需要在该矩形中生成一个随机的二维点,但不是在一个多边形中。 这就是我的意思:

在这里输入图像描述

绿色是可以生成随机点的地方,红色是无法生成的地方。 我不是很熟悉这个东西,所以我要求一个algorithm。 它也必须快速高效,因为它将在移动平台上运行,并可能每秒产生几次。 我可以检查点是否在多边形中,但是如何将其从多边形移开以使其仍然“随意”? 谢谢。

PS多边形将始终有4个顶点。

最简单的方法是在矩形内生成一个随机点,如果它位于多边形中,则拒绝它。 你会重复这个过程,直到你有一个有效的点。 使用相同的algorithm来统一分布区域或体积上的点,除了被认为是exception值的点被拒绝。 如果您想进一步研究,这种types的抽样被称为拒绝抽样 。

我会做多边形testing的方式是单独testing4个边缘的点。 想象一下,所有的线都在两个方向延伸到无穷大。 2d平面上的任何点都属于由单个无限行创建的两个分区之一。 例如:

A (0, 2) (4, 2) <--.----------.------> B 

两点(0, 2)(4, 2)形成y = 2的直线。点A被认为是在该线的“上方”,而点B被认为是在该线的“下方”。

现在把这个想法扩展到这4行。 如果一个点以特定的方式testing所有4条线,则该点必须位于多边形中。 这与testingAABB中的点遏制时使用的逻辑是相同的,只是简化了所有线平行于X或Y轴的情况,使得比较更简单。

在计算机上计算的方式实际上是非常简单的, 这个StackOverflow答案提供了一个函数,需要3点 – 两个形成一个线和一个testing。

如果您使用与SO答案相同的函数,则需要多边形的左边缘返回false,右边缘返回true,顶边返回false,底边返回true被认为是包含的。

在最坏的情况下,testing需要20次减法,8次乘法和4次比较。 即使在低端智能手机上,也没有什么。 即使每帧testing几个点,也不会影响性能。

这种抽样对你提出的移动点的好处是任何简单的移动点的algorithm都会使你的分布在多边形周围变得更密集。 拒绝采样保持相同的分布,它只是删除不属于的东西。

我想你所说的检查是否在多边形中移动它可能是好的,如果说你把点向上或向下移动到不在多边形中,用户不会注意到任何东西。 你可以随意移动它,所以它不会总是在你的多边形的边界上。

您也可以尝试将多边形周围的空间分开,然后随机选取一个线段,然后在该空间中指出您的位置。

伊夫之前做过一个简单的比赛,但我所避开的区域是一个静态的广场。