检查多边形是否在多边形内 [英] Check if polygon is inside a polygon

问题描述

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

Yesterday I was looking to check if a point was inside a polygon and found this great script: https://github.com/tparkin/Google-Maps-Point-in-Polygon

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

But today at work I was told that our client needs to check if one polygon is inside another polygon. I am wondering if is there a formula where I can take, let's say, two coordinates (instead of one to check a point), and from those two coordinates generate a rectangle and check if that rectangle is inside a polygon.

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

I don't know if I'm asking a stupid question (a teacher in highschool used to say "there are no stupid questions, there is only fools who don't ask"), but if you don't understand me totally but just a bit, I'd be grateful if you just tell me where to start.

推荐答案

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

Perform line intersection tests for each pair of lines, one from each polygon. If no pairs of lines intersect and one of the line end-points of polygon A is inside polygon B, then A is entirely inside B.

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

The above works for any type of polygon. If the polygons are convex, you can skip the line intersection tests and just test that all line end-points of A are inside B.

如果真的有必要，您可以使用 sweep line 加速线相交测试算法.

If really necessary, you can speed up the line intersection tests using the sweep line algorithm.

这篇关于检查多边形是否在多边形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！