确定一个点是否坐在任意形状内？

给定一个点的坐标，我怎么能确定它是否是任意形状之内？确定一个点是否坐在任意形状内？

的形状是由点的数组定义，我不知道在哪里形状“封闭”，我真的需要帮助制定出其中的形状被关闭的部分。

这里有一个形象说明我的意思好一点：这样做是从点投下光线又算什么多少次跨越边界

enter image description here

来源

2011-06-26 gibo

形状不开......我只是不知道它是封闭的。 – gibo

你必须知道形状是如何由一系列点定义的。如果你的意思是点的数组是形状内的一组点，那么问题是微不足道的。 – sawa

在我张贴的图片或许可以解释这一点更好。我知道沿着蓝线的点，但不知道在哪里交收形状 – gibo

最简单的方法。如果它很奇怪，那么点就在里面，即使这点在外面。

百科：http://en.wikipedia.org/wiki/Point_in_polygon

请注意，这仅适用于歧管的形状。

来源

2011-06-26 20:23:29 Mikola

太棒了。谢谢你提醒我！ – ambrus

其实，如果你给出点的数组，你可以检查形状的接近程度如下：
考虑点P[i]和P[i+1]的对数组中给定的 - 它们形成的形状边界的一些片段。如果（只是通过检查所有可能对这样的段）存在两个这样的段相交，可以在O(N^2)及时检查什么，你需要检查的。如果存在交叉点，则表示您的形状已关闭。
注意：您必须留心，不要忘记（数组中，即第一和最后一个点），来检查段P[0],P[n-1]无论是。

来源

2011-06-26 20:51:52

什么时候p [i]，p [i + 1]和p [j]，p [j + 1]相交？我想它会告诉我们这个形状是一个简单的多边形还是一个复杂的多边形。此外，您没有回答关于如何查找点是否位于多边形中的原始问题。 –

@logic_max：嗯，我回答了关于如何检查形状是否关闭的问题，根据问题声明，它不一定是多边形，它可以是任意多段线。存在任何p [i]，p [i + 1]和p [j]，p [j + 1]交集只会告诉我们形状有一个闭合部分。关于这点 - 米科拉的回答是正确的。 –

这不起作用。如果你拿一个封闭的多边形，然后添加一个悬挂边缘呢？事实上，我不确定你正在测试的是什么，以及它与这个问题有什么关系？ – Mikola

如果要确定点P是否处于任意形状，我只需从P处开始进行填充填充。如果填充填充离开预定义的边界框，则表明形状不在其中。否则，如果你的颜色填充终止，那么你的形状:)

内，我相信这个算法是O（N^2），其中N是点的数量，因为最大面积正比于N^2。

百科：Flood Fill

来源

2011-06-27 18:16:28 tskuzzy

确定一个点是否坐在任意形状内？

回答

相关问题