javascript - 检查多边形是否在多边形内部

Question

昨天我想检查一个点是否在多边形内，发现了这个很棒的脚本:https://github.com/tparkin/Google-Maps-Point-in-Polygon

但是今天在工作中我被告知我们的客户需要检查一个多边形是否在另一个多边形内部。我想知道是否有一个公式让我可以采用两个坐标(而不是一个来检查一个点)，然后从这两个坐标生成一个矩形并检查该矩形是否在多边形内。

我不知道我是不是在问一个愚蠢的问题(高中老师曾经说过“没有愚蠢的问题，只有不问的傻瓜”)，但如果你不明白我完全但只是一点点，如果你能告诉我从哪里开始，我将不胜感激。

Answer 1

执行 line intersection测试每对线，每个多边形一条线。如果没有线对相交，并且多边形 A 的线端点之一在多边形 B 内部，则 A 完全在 B 内部。

以上适用于任何类型的多边形。如果多边形是凸多边形，则可以跳过线相交测试，只测试 A 的所有线端点都在 B 内。

如果真的有必要，你可以使用 sweep line algorithm 来加速线相交测试。 .