给定一个点的坐标,我怎么能确定它是否是任意形状内?
的形状是由点组成的数组定义的,我不知道那里的形状封闭的一部分,我真正需要帮助的是找出其中形状被关闭。
下面是一个图像来说明我的意思好一点:
解决方案
其实,如果你给出一个点的数组,你可以检查形状接近如下:
考虑点对 P [I]
和 P [I + 1]
给出的数组中 - 他们形成了一些片段你的形状的边界。如果存在两个这样的段相交,它可以在进行检查O(N ^ 2)
时间(你需要检查什么是仅仅通过检查所有可能对这类段)。如果存在的交点,这意味着你的形状是封闭的。
注意:您必须留心不要忘记检查段 P [0],P [N-1]
或者(即数组中的第一个和最后一个点)
Given a point's coordinates, how can I determine if it is within an arbitrary shape?
The shape is defined by an array of points, I do not know where the shape is 'closed', the part I really need help is to work out where the shape is closed.
Here's an image to illustrate what I mean a little better:
解决方案Actually, if you are given an array of points, you can check the closeness of the shape as follows:
Consider pairs of points P[i]
and P[i+1]
given in the array - they form some segment of the border of your shape. What you need to check is if there exist two such segments that intersect, which can be checked in O(N^2)
time (just by checking all possible pairs of such segments). If there exists an intersection, that means that your shape is closed.
Note: you must be attentive not to forget to check the segment P[0],P[n-1]
either (i.e. first and last points in the array).