检查多边形是否在多边形内

Question

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

但今天在工作中我被告知我们的客户需要检查一个多边形是否在另一个多边形内.我想知道是否有一个公式我可以采取,比方说,两个坐标(而不是一个检查一个点),并从这两个坐标生成一个矩形,并检查该矩形是否在多边形内.

我不知道我是不是在问一个愚蠢的问题(高中的一位老师常说"没有愚蠢的问题,只有傻瓜不问"),但如果你完全不了解我,只是一点点,如果你告诉我从哪里开始,我将不胜感激.

Answer 1

对每对线执行线交叉测试,每个线对应一个.如果没有线对相交并且多边形A的一个线端点在多边形B内,则A完全在B内.

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

如果确实有必要,可以使用扫描线算法加速线路交叉测试.