geometry - 确定坐标是否存在于多边形内部

Question

我正在开发一个开源跟踪和地理围栏软件应用程序，并且在计算地理围栏的数学时遇到了一些困难。

我需要确定多边形内是否存在坐标。然而，棘手的部分是多边形没有固定的边数。我需要能够计算五十边或五边。

我的研究表明，最简单的方法是取我的点(我称之为 x)和多边形外的一个点(称之为 y)并确定线 ((xx, xy), (yx, yy)) 是否与多边形的边界。如果它相交奇数次，则点 x 必须在多边形内。

然而，知道这一点，我无法弄清楚如何在算法中表达这一点..我显然需要遍历构建多边形的各种线，但我所做的检查却让我望而却步。任何人都可以提供帮助吗？请知道我不一定要求解决方案。任何能帮助我找出答案的东西都是巨大的帮助。

非常感激。

Answer 1

见 here

基本上有一种方法(我认为是乔丹曲线定理)可以计算光线与构成多边形的线段相交的次数。如果结果是偶数，则该点在多边形外部，否则该点位于多边形内部。

HTH

编辑
还有另一个与此问题相关的 SO 问题可以在 here 中找到。