确定一组点是在方形内部还是外部

Question

我有两个:

bool isPointOnShape(int a, int b)
{

}

bool isPointInShape(int a, int b)
{

}

假设我有一个正方形,第一个点(左下角)是x,y(0,0)第二个点(左上角)是(0,2),第三个是(2,2),第四个是(0,2) .

形状上的点将是(0,1)(1,2)(2,1)(1,0)并且形状中的点是(1,1)

如何找出形状/形状上的点并返回真值,以便我可以将它存储在某个地方？

Answer 1

我将为任何可以分成直线段的形状提供通用解决方案.

所以,正如您可能已经猜到的那样,我将首先将您的"形状"视为完成循环的段列表.或者简单地放一个表示循环的圆点列表,例如,你的方格就是这个点列表:

0, 0
0, 2
2, 2
2, 0

请注意,我们认为从每个点到下一个点都有段,并且最后一个点连接到第一个点.此外,我们要求没有连续的点相等,也不要求第一个和最后一个.如果有,那么必须在继续之前将其删除.

现在,对于每个段,我们可以确定边界框.例如,鉴于此细分:

a = (0, 2)
b = (2, 2)

然后x中的值范围是[0,2],y中的值是[2,2],这是该段的边界框.

接下来你需要的是段的线的导向矢量.为此,首先计算段的长度:

length = sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))

然后:

director.x = (a.x - b.x)/length
director.y = (a.y - b.y)/length

注1:当length为0时,则表示无效段.这就是为什么我们不想重复点.

注意2:使用导向矢量而不是使用直线方程将使事情变得更容易.

现在,给定一个点p,您可以确定该点是否在一个段中(如果它是列表中的一个点).对于其他情况,我们首先查看它是否在边界框内.只需检查范围即可完成此操作:

if
(
    (p.x >= box.left && p.x <= box.right) &&
    (p.y >= box.top && p.y <= box.bottom)
)
{
     //It is inside of the bounding box
}

如果是,那么我们计算从点到线的距离,如果它是0那么它就在线上.现在,由于浮点算术,你可以测试距离是否小于或等于epsilon,其中epsilon是一个非常小的数字.

我们使用这个公式:

distance vector = (a - p) - ((a - p) · director) * director
distance = the norm of distance vector

其中"·"表示点积,"*"表示标量积.

所有这些都是迭代段,每个都计算距离,如果对于任何人,距离小于epsilon,那么点就是"在形状上".

好的,但是"在形状上"怎么样？

好吧,在拓扑技巧的帮助下,我们可以确定一个点是否在内部.这与Windows用于填充多边形或折线的算法相同(例如在Microsoft Paint中用自由手决定选定区域内的内容).

它是这样的:

计算您必须跨越的段数以从外部到达该点.如果数字是对,那么它在外面,如果它是奇数然后在里面.

您可以选择从哪个方向到达该点.我选择了左.

再一次,您将迭代细分.对于每一个,我们需要确定它是否在垂直范围内.为此使用边界框:

if ((p.y >= box.top && p.y <= box.bottom))
{
     //In the vertical range
}

现在,确定该段是左侧还是右侧:

if (p.x < box.left)
{
     //The segment is at the left
}
else if (p.x > box.right)
{
     //The segment is at the right
}
else
{
     //The segment is close, need further calculation
}

在段接近的情况下,我们需要计算到该段的向量距离并检查它的方向.

矢量距离？好吧,我们已经拥有它,我们正在采取常规来确定距离.现在,不是采用标准,而是验证x坐标的符号.如果它小于0,则它是正确的,如果它大于0则保留它.如果它是0 ......这意味着该段是水平的(因为距离矢量始终垂直于该段),您可以跳过该段*.

*:实际上,如果段是水平的并且它在垂直范围内,则意味着它在段中.细分是否"形状"？

现在,您需要计算左侧的段数,如果是奇数,则该点位于形状内.否则就是这样.这也可以通过向上,向右或向下的段来完成.我刚刚离开了.

对于迭代所有段的大型形状来说很昂贵,您可以将段存储在某些空间分区数据结构中.这超出了这篇文章的范围.