检查，如果多边形是多边形内 [英] Check if polygon is inside a polygon

问题描述

昨天我一直在寻找，检查点是一个多边形内，发现这个伟大的脚本：<一href="https://github.com/tparkin/Google-Maps-Point-in-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是完全内湾

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的都在里面湾

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.

如果确有必要，可以使用扫描线算法加快线相交测试

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

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