确定一个点是否位于任意形状内？
给定一个点的坐标，如何确定它是否在任意形状内？
形状是由点数组定义的，我不知道形状在哪里“闭合”，我真正需要帮助的部分是找出形状在哪里闭合。
这是一张图片，可以更好地说明我的意思：
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:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
最简单的方法是从该点投射一条射线并计算它穿过边界的次数。如果是奇数，则该点在内部，如果是偶数，则该点在外部。
Wiki： http://en.wikipedia.org/wiki/Point_in_polygon
请注意，这仅适用于多种形状。
Easiest way to do it is cast a ray from that point and count how many times it crosses the boundary. If it is odd, the point is inside, even the point is outside.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Note that this only works for manifold shapes.
如果您想确定点 P 是否处于任意形状，我只需从 P 开始运行洪水填充。如果您的洪水填充留下了预先确定的边界框，则您位于该形状之外。否则，如果你的洪水填充终止，那么你就在形状内:)
我相信这个算法是 O(N^2)，其中 N 是点数，因为最大面积与 N^2 成正比。
维基百科：洪水填充
If you want to determine whether or not a point P is in an arbitrary shape, I would simply run a flood fill starting at P. If your flood fill leaves a pre-determined bounding box, you are outside the shape. Otherwise if your flood fill terminates, then you're within the shape :)
I believe this algorithm is O(N^2) where N is the number of points, since the maximum area is proportional to N^2.
Wikipedia: Flood Fill
实际上，如果给定一个点数组，您可以按如下方式检查形状的接近度：
考虑数组中给出的点对
P[i]和P[i+1]- 它们形成形状边界的某些部分。您需要检查的是是否存在两个这样的线段相交，这可以在 O(N^2) 时间内检查（只需检查所有可能的此类线段对）。如果存在交叉点，则意味着您的形状是封闭的。注意：您必须注意不要忘记检查段
P[0],P[n-1]（即数组中的第一个和最后一个点）。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]andP[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 inO(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).