关于多边形的一点看法
在公共领域中存在几种算法，供 Web 服务器确定点是否在多边形内部。它们用于实现“图像地图”，包括传统的服务器端类型和更现代的客户端类型。那么，谁还需要多一种算法呢？作者希望恭敬地指出，他能找到的大多数点在多边形代码都过于复杂。作为简洁和简化的爱好者，他实在无法袖手旁观。
最终的 C 语言例程只有三个 if 语句，没有除法运算。相比之下，流行的 Apache Web 服务器中的相应例程有三个除法和十个 if 语句。获取 Apache 发行版，搜索 pointinpoly 即可查看完整代码。CERN/W3C 的 httpd 中的例程更糟糕，竟然有 19 个 if 语句！在他们的 HTImage.c 中搜索 inside_poly。（URL 在表 2 中显示。）
表 1 对比了公共领域中五种不同的点在多边形算法，用于找出点是否在多边形内。在所有情况下，多边形都指定为角点的 X,Y 坐标数组。
这是对算法的相当随意的分析。我当然没有回避以良好的角度展示我的 inpoly()。例如，C 语言中的 && 和 || 运算符通常是伪装的语句。我使用了一个这样的运算符（其他大多数人也使用了），但这根本没有在表中显示出来。此外，一些行数因注释和空行而略有膨胀。但您大致了解情况。
所有判断都有其背景，我应该解释一下我的背景。本文的首要前提是算法的简洁性。我承认，这与 Web 的实际需求几乎无关。为了防止我自说自话，Web 图像地图是一种划分图像的方式，以便点击特定区域执行一个操作，而点击其他位置执行其他操作。Web 图像地图在 Web 服务器和浏览器的工作中只占很小一部分，因此以上所有例程都很好。从一个例程更改为另一个例程不会对 Web 性能产生任何明显的影响。一旦我们确定它有效，谁还会再看代码 100 年呢？因此，我没有任何关于性能或可读性的实际考虑来证明我的理由。我只是在倡导简洁的美学。
我想表达的观点是，问题并不总是像它们看起来那样。有时存在简单的解决方案，但您必须认真审视才能找到它。我的朋友 Craig 最初开始移植 W3C 的 inside_poly()（我认为是），以便在我们的 Web 服务器上使用。当我看到所有浮点数学和 if 语句特殊情况时，我认为必须有更好的方法。因此，Craig 和我从头开始，与问题进行了较量，并提出了一个不包含浮点数学的解决方案，这对于屏幕像素来说是很荒谬的，也没有比乘法更繁琐的数学运算。我们还摆脱了所有令人讨厌的特殊情况，只有一个例外：排除边数少于三条的多边形。两条边的多边形内部能有什么？Apache 的 pointinpoly() 甚至没有检查，并且很可能对一个点的多边形造成了很大的混乱。
现在，声明的目标是简洁性，而不是性能，但我在一个问题上偏离了这一路线：避免除法。同样，性能对于图像地图应用几乎无关紧要，但有一天有人可能会将此算法用于某种 3D 隐藏表面算法或其他用途。消除除法可能实际上需要我使用额外的 if 语句。无论如何，所有这一切都表明，Kevin Kenny 的算法（见表 1）以 29 行和两个 if 语句是迄今为止最短和最简单的。但我的算法在某种意义上仍然更好，因为我的算法不需要除法，而他的算法需要。
现在让我们讨论更流行的用于确定点是否在多边形内部的算法。
图 1. 奇数个多边形交叉
想象一下，您可以通过在点上放置一只友善的训练有素的蜗牛，并告诉它前往北极来检测点是否在多边形内。（我们只关注图像地图，因此我们排除延伸到北极的多边形，并且我们忽略科里奥利力。）您会为图 1 中勇敢的朋友配备一个蜗牛大小的剪贴板，并指示他在每次穿过多边形的边缘时打勾。他会从北极给您打电话，报告交叉次数。偶数（包括零）表示他从多边形外部开始，奇数表示在内部。
这会将问题简化为检测线段是否相交。甚至更好一点，因为其中一个线段只是正 Y 轴。为了实现这一飞跃，只需将蜗牛的起点声明为原点 (0,0)，并将所有多边形角点转换为相对于该点的坐标。
我们稍后将详细介绍该算法，但请查看清单 1 中的完成代码。简直是简洁的典范，对吧？如果您还没有查看其他版本，您真的应该看看。
我们最初版本的 inpoly() 有一个细微的缺陷，测试程序使其显而易见。完整的故事包含一个令人尴尬的教训。“它会工作的，”我们嘲笑说，“我们不需要在完整的图形测试上浪费时间。再说，那会太有趣了。”在我们发现我们的图像地图有漏洞后，我们编写了测试程序。图 3 显示了缺陷的特写。
图 3. 缺陷：角点被计数两次
沿着垂直线，所有颜色都是错误的。缺陷原来是，当我们无脑的软体动物穿过底部角点时，这个小家伙正在计算两个边缘的交叉！在那之后，他总是完全错误——他认为他在内部时实际上在外部，他认为他在外部时实际上在内部。解决方案必须确保当我们尊敬的蜗牛穿过进入多边形角点时，他只计数一次交叉。两次不好，实际上，零次也同样糟糕——我们需要的是一次。从角点向上延伸缺陷的原因是正 Y 轴在屏幕坐标中向下延伸。
我怀疑这是一个固定点世界特有的问题。我确信我的点在多边形领域的同行要么是侥幸逃脱了，要么是以某种方式处理了它。至少，我希望如此。（测谎仪会在这件事上抓住我。如果我在任何其他算法中发现了泄漏的角点，这篇文章就会令人无法忍受地沾沾自喜。）就我而言，我意识到我不能盲目地将每个边缘端点的所有交叉都计为一次交叉。我的第一个想法是将每个端点与一个——且仅一个——边缘关联起来。这听起来公平合理，但像许多符合这种描述的事物一样，它根本行不通。当蜗牛特工只是轻轻地碰到他根本不在内部的多边形的角点时，问题就出现了。这被计为一次交叉，因此蜗牛报告是胡说八道。
由于我讨厌特殊情况，我寻找一种在所有情况下都适用的方法。
图 4. 仅计数每个边缘的右端
让我们的忠实朋友正确计数角点交叉的方案是始终计数每个边缘右端的交叉，但绝不计数左端（右表示正 X）。在图中，黑色圆圈表示我们的蜗牛如果穿过则会计数的点；白色圆圈表示他不会计数的点。当您将多边形放在一起时，一切最终都会如我们所愿。碰到角点意味着他计数 0 次交叉或两次交叉。我们不关心是哪种；两者都是偶数，我们的蜗牛知道他在外部。圆圈中带有数字 1 的圆圈表示蜗牛穿过它们时计数一次的点。这很好，就像穿过附近的边一样。
现在是时候分析清单 3 中 inpoly() 例程的核心了。这代表了对蜗牛指令的略微修改。他玩一点“她爱我，她不爱我”之类的游戏，而不是计算交叉次数，然后报告总数是偶数还是奇数。他一开始假设自己在外部，并用每次交叉来补充该假设。inside=!inside 语句就是这样。
这个 if 测试发生在 for 循环内部，该循环一次考虑多边形的所有边缘。每个边缘是一个线段，它在角点 (xold,yold) 和 (xnew,ynew) 之间延伸。我们已经安排它，使得 (x1,y1) 和 (x2,y2) 也表示相同的边缘，但必要时会交换点，以使 x1 <= x2。
现在，要使我们一丝不苟的蜗牛计数此边缘的交叉，必须满足两个条件。首先，线段必须跨越 Y 轴（其中右端被计数，但左端不被计数）。其次，跨越必须发生在蜗牛起点的北部。这些正是 if 语句的两部分（在 && 的两侧）确定的问题。
现在，第一个表达式很狡猾，我承认我可能更喜欢不太晦涩的代码 (x1 < xt && xt <= x2)。如果您仔细观察，您可以看到它执行相同的操作（非常仔细——我有一段时间被愚弄了）。但我不喜欢修复某些东西，除非我已经破坏了它，如果您明白我的意思。
北部计算是我引以为豪的，因为我的任何受人尊敬的多边形同行都没有做出不需要除法的计算。它确实依赖于 (x2-x1) 为正的知识。除此之外，它只是高中代数中著名的 y=mx+b 方程的变形。
顺便说一句，我遗漏了边缘线段笔直地垂直于蜗牛着陆点上方的情况。这样的边缘永远不会被蜗牛先生计数！那是因为 == 测试将始终为假，因为 xnew、xt 和 xold 都是相同的值。真正奇妙的是，这正是我们想要的。从某种意义上说，当我们只想要计数一次时，他正在穿过三个边缘。事实证明，相邻的线段交叉是我们感兴趣的全部，并且已经讨论过的规则对它们来说非常有效。
顺便说一句，谁关心图像地图中沿多边形边缘的点在技术上是在内部还是在外部？正如您在特写镜头中看到的那样，一些最初为白色的像素（代表多边形边缘）变成了红色，另一些变成了蓝色。如果浏览用户单击区域的边缘，他可能会进入，也可能不会。但是，如果您的屏幕分辨率大于 100 x 100，则偏移一个像素通常不是问题。在 inpoly() 例程中，一些边缘在内部，一些在外部。（我不介意在说服所有人认为它不应受到惩罚后承认犯罪。）
我还没有讨论伍兹霍尔海洋研究所用于其在 Matlab 中编写的算法的角度求和方法。该算法需要计算反正切，因此它主要只是一个实验室的好奇心。这个想法是，您将从目标点到多边形每个角点绘制的线所形成的角相加。如果总和是 360 度的偶数倍，则您在外部；奇数倍，则在内部。隐约熟悉？这里有一个类比：您在一个漆黑的房间里，地板上到处都是一条非常非常长的蛇。这是一种特别罕见的深海蛇（伍兹霍尔了解它们的一切），每英尺左右都有发光点。哦，而且他对光线的反应是立即以死亡的铁钳紧缩。您的问题是您是站在脚下的线圈迷宫内部还是外部。您想在打开灯之前知道，因为如果您踩到他，他会非常生气。
面对蛇头，并在视觉上追踪他的整个身体，以某种方式记录您这样做时脚的转动（我知道这有点牵强）。完成后，再次面对蛇头。现在，如果您根本不必转身，那么您就安全地在蛇的外面。如果您在任一方向转身两次，情况也很好。四次，您仍然没事。如果您在任一方向转身奇数次，那么您就完蛋了——难怪人们倾向于使用交叉计数算法。
