我有两个:
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)
我如何找出形状/形状上的点并返回一个真实值,以便我可以将它存储在某个地方?
我有两个:
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)
我如何找出形状/形状上的点并返回一个真实值,以便我可以将它存储在某个地方?
我将为任何可以分成直线段的形状提供通用解决方案。
因此,正如您可能已经猜到的那样,我首先将您的“形状”视为完成循环的段列表。或者简单地放置一个表示循环的点的圆形列表,例如,您的正方形将是这个点列表:
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:当长度为 0 时,您的段无效。这就是为什么我们不想要重复的点。
注2:使用导向向量而不是使用直线方程会使事情变得更容易。
现在,给定一个点 p,您可以确定该点是否在一个段中(如果它是列表中的一个点)。对于其余的情况,我们首先查看它是否在轴对齐的边界框内。这只需检查范围即可完成:
if
(
(p.x >= box.left && p.x <= box.right) &&
(p.y >= box.top && p.y <= box.bottom) // with origin at the top-left corner
)
{
//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... 则表示该段是水平的(因为距离向量始终垂直于该段),您可以跳过该段*。
*:实际上,如果段是水平的并且在垂直范围内,则表示它在该段上。段是否“成形”?
现在,您需要计算左侧的段数,如果是奇数,则该点位于形状内部。否则就不行了。这也可以通过向上、向右或向下的段来完成。我刚选了左边。
对于迭代所有段的成本很高的大型形状,您可以将段存储在一些空间分区数据结构中。这超出了本文的范围。
如果我假设你有一个Rectangle
类并且这个类有成员bottomLeft
and topRight
,你可以这样写:
bool Rectangle::isPointOnShape(int x, int y) {
if (x == bottomLeft.x || x == topRight.x)
if (y > bottomLeft.y && y < topRight.y)
return true;
if (y == bottomLeft.y || y == topRight.y)
if (x > bottomLeft.x && x < topRight.x)
return true;
}
bool Rectangle::isPointInShape(int x, int y) {
bool inX = false;
bool inY = false;
if (x > bottomLeft.x && x < topRight.x)
inX = true;
if (y > bottomLeft.y && y < topRight.y)
inY = true;
return (inX && inY);
}
如果您的形状不是矩形,则此功能当然会有所不同。