确定一组点在正方形内部还是外部 [英] Determining if a set of points are inside or outside a square

问题描述

我有两个:

bool isPointOnShape(int a, int b)
{

}

bool isPointInShape(int a, int b)
{

}

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

Say I have a square, first point (bottom left corner) is x,y (0,0) second point (top left) is (0,2), third is (2,2) and fourth is (0,2).

形状点为(0,1)(1,2)(2,1)(1,0)，形状点为(1,1)

The Points on shape would be (0,1) (1,2) (2,1) (1,0) and Points in shape is (1,1)

如何找出形状/形状上的点并返回真实值，以便将其存储在某处?

How do I find out the points on shape / in shape and return a true value so that I can store it somewhere?

推荐答案

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

I'll offer a general solution for any shape that can be divided in straight segments.

因此，正如您可能已经猜到的那样，我首先将您的形状"视为完成循环的线段列表.或简单地放置一个表示循环的点的圆形列表，例如，您的正方形就是该点列表:

So, as you may have guessed, I'll start by consider your "shape" as a list of segments that completes a loop. Or simply put a circular list of points that represents a loop, for example, your square would be this list of points:

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

请注意，我们认为从每个点到下一个点都有线段，并且最终点连接到第一个点.此外，我们要求连续的点都不相等，也不要第一个和最后一个相等.如果有的话，必须先删除这些内容.

Note that we consider that there are segments from each point to the next and that the final point connects to the first. Also, we require that no consecutive points are equal, nor the first and last. If there are any, those must be removed before proceeding.

现在，对于每个线段，我们都可以确定边界框.例如，给出此段:

Now, for each segment we can determinate the bounding box. For example given this segment:

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

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

Then the range of values in x is [0, 2] and in y is [2, 2] and that is your bounding box for that segment.

下一步，您需要的是该段线的导向向量.为此，首先计算段的长度:

The next thing you need is the director vector of the line of the segment. To get that, first calculate the length of the segment:

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:当then长度为0时，那么您有一个无效的段.这就是为什么我们不想重复点.

Note 1: when then length is 0, then you have an invalid segment. That's why we don't want repeated points.

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

Note 2: Using the director vector instead of using the equation of the line will make things easier.

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

Now, given a point p, you can determinate if that point is in a segment (if it is one of the points in the list). For the rest of cases we start by looking if it is inside of the axis aligned bounding box. This is done simply by checking the range:

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是一个非常小的数字.

And if it is, then we calculate the distance from the point to the line, if it is 0 then it is on the line. Now, because of floating point arithmetics, you could test if the distance is less or equal to epsilon, where epsilon is a very small number.

我们使用以下公式:

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

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

Where "·" denotes a dot product and "*" denotes an scalar product.

剩下的就是迭代这些片段，为每个片段计算距离，如果对于任何人，该距离小于epsilon，则该点位于形状上".

All that rests is to iterate over the segments, for each one calculate the distance and if for anyone the distance is less than epsilon then the point is "on the shape".

好吧，那形状"呢?

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

Well, with a little help of a trick from topology we can determinate if a point is inside or not. This is the same algorithm Windows would use to fill a polygon or polyline (such as deciding what is inside a selected area with free hand in Microsoft Paint).

它是这样的:

计算从外部到达终点所必须经过的路段数.如果数字是一对，那么它在外面，如果是奇数，然后在里面.

Count the number of segments you have to cross to get to the point from outside. If the number is pair, then it is outside, if it is odd then inside.

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

You can choose from what direction to reach the point. I choose left.

再一次，您将遍历这些段.对于每一个，我们需要确定它是否在垂直范围内.为此，请使用边界框:

Once more, you are going to iterate over the segments. For each one we need to decide if it is at the vertical range. For that use the bounding box:

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

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

Now, determinate if the segment is at left, or right:

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
}

在线段很近的情况下，我们需要计算到该线段的矢量距离并检查其方向.

In the case that the segment is close we need to calculate the vector distance to that segment and check it's direction.

矢量距离?好吧，我们已经有了它，我们正在采用其规范来确定距离.现在，而不是使用范数，而是验证x坐标的符号.如果小于0，则为右；如果大于0，则为左.如果为0 ...，则表示线段是水平的(因为距离矢量始终垂直于线段)，因此可以跳过该线段*.

The vector distance? Well, we already have it, we are taking its norm to determinate the distance. Now, instead of taking the norm, verify the sign of the x coordinate. If it is less than 0, it is right, if it is more than 0 then it is left. If it is 0... it means that the segment is horizontal (because the distance vector is always perpendicular to the segment), you can skip that segment*.

*:实际上，如果线段是水平的并且在垂直范围内，则表示它在线段上.分段是否成形"?

*: In fact, if the segment is horizontal and it is in vertical range, it means that it is at the segment. Are segments "in shape" or not?

现在，您需要计算左侧的段数，如果该段为奇数，则该点位于形状内.否则.这也可以使用向上，右侧或下方的细分来完成.我刚选左.

Now, you need to count the number of segments at the left, and if it odd, the point is inside the shape. It is out otherwise. This can also be done with the segments that are up, or right, or below. I just picked left.

对于在所有段上进行迭代都比较昂贵的大型形状，可以将这些段存储在某些空间分区数据结构中.这超出了本文的范围.

For large shapes where iterating over all the segments is expensive, you can store the segments in some space partitioning data structure. That is beyond the scope of this post.

这篇关于确定一组点在正方形内部还是外部的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！