检查多边形是否在另一个多边形内部。

Question

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

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

我不知道我是否在问一个愚蠢的问题（高中时老师曾说“没有愚蠢的问题，只有不问问题的傻瓜”），但如果你能理解我一点点，就算不能完全理解，我也会感激你告诉我从哪里开始。

- chuysbz

---

检查多边形A的所有顶点是否位于多边形B内部。 - user216441

我首先会检查一个多边形的边界框角落是否在另一个多边形内部；这将是一个快速的测试。在此之后，按照@M28的建议，检查一个多边形中的每个点是否在另一个多边形内部。 - Phrogz

@M28 仅检查顶点是不起作用的。如果B不是凸的，则存在（许多）情况，其中所有A顶点都在B中，但A的一部分仍然越过B的外部。 - payne

@payne 是的，但他说他只会使用矩形。 - user216441

@M28：他说他正在检查一个矩形是否在多边形内部。考虑一个星形的多边形：矩形的所有角落都可能在星形内部，但矩形的某些部分可能位于星形外部。 - payne

@payne 是的，现在我注意到他说的是一个多边形内部的矩形。 - user216441

Answer 1

对于每对线段，一个来自多边形A，一个来自多边形B，执行线段交叉测试。如果没有线段相交，并且多边形A的一个线段端点在多边形B内部，则A完全在B内部。

上述方法适用于任何类型的多边形。如果多边形是凸多边形，可以跳过线段交叉测试，只需测试A的所有线段端点是否在B内部。

如果确实有必要，可以使用扫描线算法加快线段交叉测试的速度。

参考示例多边形：

- moinudin

---

如果没有线段相交，那么你只需要检查一个点，对吗？ - sdleihssirhc

我这边脑子有点抽了，这就是周五下午试图思考的结果。边...而不是点。由于某种原因，我认为你必须检查多边形中的每条可能的线路...而不是实际构成多边形的线路。今天真是个糟糕的一天，感谢你纠正我 :) - brian-d

@marcog：如果一个多边形与另一个多边形共享一些顶点并且仅仅是相互接触，那么如果你选择了一个错误的（共享的）顶点进行测试，你会得出错误的结论，即一个多边形实际上在另一个多边形内部。 - Igor Brejc

在某些应用程序中，多边形可能会有洞。在这种情况下，上述算法需要进行调整。此外，根据应用程序的不同，计算退化情况（例如在线上的点）的交点时，您应该注意数值精度。 - Pablo H

此算法仅适用于没有任何空洞的多边形，并且只适用于一个多边形完全包含另一个多边形的情况。共享边缘的多边形（示例）不能正确检测，需要所有一个多边形的点都在另一个多边形内（如果存在任何重叠的边缘）。据我所知。 - kelunik

Answer 2

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

- Guffa

---

不行，那只适用于矩形或正方形。 - NickG

@NickG：我不明白你从哪里得出这个限制。如果多边形的一个点在另一个多边形内部，并且没有多边形的线穿越到另一个多边形外部，那么整个多边形显然是在另一个多边形内部的。 - Guffa

是的，我想我误读了 - 抱歉 :) - NickG

Answer 3

我必须找到一个类似的解决方案。这是我目前的进展：

1. 首先，我将所有一级多边形坐标都存储在一个array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..]中
2. 然后获取所有三级多边形并绘制它们
3. 然后对于每个一级多边形，我检查每个多边形坐标是否在绘制的三级坐标内，使用google.maps.geometry.poly.containsLocation(latLng, pol)
4. 如果返回true，计数器会增加
5. 最后，如果计数器等于该数组的长度，则结果为true（一级多边形在三级多边形内）。

我的算法大致如下：

“区域（三级）->地区（二级）->村庄发展委员会（一级）” vdcs = getVDCs(); ->以数组形式给出具有名称、ID和多边形坐标的vdcs zones = getZones(); ->以数组形式给出具有名称、ID和多边形坐标的zones

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)}
    }
}

- crazartist

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;
    }
}

- zeta

---

这仅适用于凸外形。凹外形可以包含内部形状的所有点，但具有重叠的边缘。 - thelastshadow

Answer 5

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

- sdleihssirhc