3

要检测一个点是否在多边形中,您可以从该点投影一条线到无穷远,并查看它与多边形的多少个顶点相交......足够简单。我的问题是,如果光线在其中一个点上与多边形相交,则它被视为与两个线段相交,并被视为在多边形之外。我更改了我的函数,使其仅在光线与多边形的一个点相交时计算其中一个线段,但在某些情况下,一条线也可以与该点相交,同时仍然在外面。以这张图片为例:

穿过多边形顶点的光线的两个示例

如果您假设左上角的点是“无穷大”,并向其他点中的任何一个投射一条射线,它们都在多边形的一个点处相交,并且即使一个在内部,也会被视为与相同数量的顶点相交,一个在外面。

有没有办法弥补这一点,还是我只需要假设那些边缘案例不会弹出?

4

3 回答 3

2

如果光线恰好在一个顶点上穿过一侧,则仅当另一个顶点位于光线上方时才计算该侧。这将解决你的角落案例。

例如,在您发布的图片中,较低的射线在左上角顶点处穿过正方形的两侧,但一侧在射线上方,另一侧在下方,因此贡献为 1,并且发现目标点在内部。上面的射线在右上角的顶点处穿过两侧,两侧都在射线下方,因此它们对计数的贡献为 0,并且发现目标点在外面。

更新

我记得读过一篇文章,它描述了一种处理一般情况的技术。如果有兴趣,请阅读我的其他答案。

于 2013-01-02T23:37:14.377 回答
0

向另一个方向发送光线。

如果您尝试n+1不同的方向(n是多边形点的数量),其中一个肯定不会通过任何顶点。

与考虑极端情况相比,这将简化代码。

最坏的情况成为O(n)*CheckComplexity(n)可能O(n^2)。如果不可接受,您可以按从点到它们的方向对所有顶点进行排序,然后选择某个区间的中间。这会给O(n*log n).

于 2013-01-04T21:10:32.977 回答
0

虽然我的第一个答案应该可以解决这个简单的问题,但我不得不提到存在处理这些特殊情况的通用技术。

本文介绍了一种处理此类问题的技术。他们提供的第一个示例恰好是您询问的算法!

这个想法是应用自动微分又名对偶数来计算符号扰动。

顺便说一句,同样的技术也可以用来避免在程序中将 0/0 作为特殊情况处理!

是我最初从中学到的博客文章,它为该技术提供了一些很好的背景,并且作者在博客中写了很多关于自动微分 (AD) 的文章。

尽管看起来 AD 是一种非常实用的技术,尤其是在对运算符重载有很好支持的语言中(例如:C++、Haskell、Python ...),我已经在“现实生活”中使用过它(C++ 中的工业应用程序)。

于 2013-01-03T12:01:07.863 回答