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

Question

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

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

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

Answer 1

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

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

如果确实有必要，您可以使用扫线算法加速线相交测试。

供参考的多边形示例：

Answer 2

首先使用脚本检查多边形中的一个角点是否位于另一个多边形内部。然后检查多边形中的任何直线是否与另一个多边形中的任何直线相交。如果没有，则该多边形位于另一个多边形内部。

Answer 3

多边形是凸的吗？因为，如果是的话，您可以为“矩形”的两个“角”运行“多边形中的点”脚本。如果两个角都在里面，并且多边形没有向内的“曲线”，那么整个矩形不就在里面了吗？

Answer 4

也许这部分代码可以帮助你：

package com.polygons;
import java.awt.Point;
import java.awt.Polygon;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.apache.commons.collections.CollectionUtils;

/**
 * Utility to Manipulate Polygons
 * 
 * @author fernando.hernandez
 *
 */

public class PolygonUtils {

    /**
     * Check if  polygon2 is inside polygon to polygon1
     * @param polygon1 polygon that contains other 
     * @param polygon2 polygon that is inner to other
     * @return true if polygon2 is inner to polygon1
     */
    public boolean isInsidePolygon(Polygon polygon1, Polygon polygon2){
        //all points in inner Polygon should be contained in polygon
        int[] xpoints = polygon2.xpoints;
        int[] ypoints = polygon2.ypoints;
        boolean result =  true;
        for (int i = 0, j = 0; i < polygon2.npoints ; i++,j++) {
             result = polygon1.contains(new Point(xpoints[i], ypoints[j]));
             if(!result) break;   
        }
        return result;
    }
}

Answer 5

我必须找到类似的解决方案。这是我到目前为止所拥有的：

1. 首先我获取了

   array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..]

中的所有 1 级多边形坐标
2. 然后获取所有 3 级多边形并绘制它们
3. 然后对于每个 1 级多边形，我使用

   google.maps.geometry.poly.containsLocation(latLng, pol)

检查每个多边形坐标是否位于绘制的 3 级坐标内
4. 如果返回

   true

   计数器会上升
5. 最后，如果计数器等于该数组的长度，则结果为 true（1 级多边形位于 3 级多边形内部）。

我的算法看起来像这样：

""区(3级)->区(2级)->VDC(1级)"" vdcs = getVDCs(); -> 以数组形式给出 vdc，其中包含名称、id 和多边形坐标 zone = getZones(); -> 在数组中给出区域，其中包含名称、ID 和 多边形坐标

foreach(zones as zone){
    drawPolygon(zone[coordinates]);
    foreach(vdcs as vdc){
        foreach(vdc[coordinates] as coordinate){
            result = checkLocation(zone, coordinate);
            if(result) counter++;
        }
        if(counter = vdc[coordinates].length){writeConsole(vdc_id+"true in"+zone_id)}
    }
}