algorithm - 给定点位于多边形内部或外部

Question

我正在尝试这个问题并找到了解决方案:

在每个点的右边画一条水平线，并延伸到无穷远

1) Count the number of times the line intersects with polygon edges.
2) A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.

但我认为有一个简单的解决方案:

for(all sides in same order)
find vector product of the 3 points (given point and end points of each side)

if all products are > or < 0 : point lies inside polygon or on boundary<br/>
else outside

我的解决方案不是更好更高效吗？
还有比这更简单的算法吗？

Answer 1

所提出的使用叉积检查的算法仅适用于凸多边形。对于非凸多边形，很容易找到它不起作用的示例。尝试给定多边形中的任意点 c、d 或 e。