Проверьте, находится ли многоугольник внутри многоугольника

Вчера я смотрел, чтобы проверить, находится ли точка внутри многоугольника, и нашел этот замечательный script: https://github.com/tparkin/Google-Maps-Point-in-Polygon

Но сегодня на работе мне сказали, что нашему клиенту нужно проверить, находится ли один полигон внутри другого полигона. Мне интересно, есть ли там формула, где я могу взять, скажем, две координаты (вместо одной, чтобы проверить точку), и из этих двух координат генерирует прямоугольник и проверяет, находится ли этот прямоугольник внутри многоугольника.

Я не знаю, задаю ли я глупый вопрос (учитель в старшей школе говорил "нет глупых вопросов, есть только дураки, которые не спрашивают" ), но если вы не понимаете я полностью, но немного, я был бы признателен, если бы вы просто сказали мне, с чего начать.

Ответ 1

Выполните пересечение линий для каждой пары линий, по одному от каждого полигона. Если пары линий не пересекаются, а одна из конечных точек линии многоугольника A находится внутри многоугольника B, то A полностью внутри B.

Вышеупомянутое работает для любого типа многоугольника. Если многоугольники выпуклые, вы можете пропустить тесты пересечения линий и просто проверить, что все конечные точки линии A находятся внутри B.

Если это действительно необходимо, вы можете ускорить тесты пересечения линий, используя алгоритм развертки линии.

Ответ 2

Сначала проверьте, что одна из угловых точек в многоугольнике находится внутри другого полигона с помощью script. Затем проверьте, не пересекается ли какая-либо из линий в многоугольнике ни одна из линий другого полигона. Если они этого не делают, полигон находится внутри другого полигона.

Ответ 3

Возможно, эта часть кода может вам помочь:

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

Ответ 4

Является ли многоугольник выпуклым? Потому что, если это так, вы можете просто запустить "точку в полигоне" script для обоих "углов" вашего "прямоугольника". Если оба угла находятся внутри, а полигон не имеет "кривых" внутрь, то не будет ли весь прямоугольник?

Ответ 5

Почему бы не использовать JTS? Он имеет множество портов для других языков, включая С++, JavaScript и .NET.

Ответ 6

Мне пришлось найти подобное решение. Вот что я до сих пор:

Сначала я выбрал все координаты многоугольника уровня 1 в array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..]
Затем извлекли все многоугольники уровня 3 и построили их
Затем для каждого уровня 1 многоугольник, я проверил, была ли каждая из координат многоугольника внутри построенной координаты уровня 3 с google.maps.geometry.poly.containsLocation(latLng, pol)
Если он вернет счетчик true, он поднимется вверх
Наконец, если счетчик был равен длине этого массива, результат был бы правдой (полигон уровня 1 находится внутри многоугольника уровня 3).

Мой алгоритм выглядит примерно так:

"Зона (уровень 3) → Район (уровень 2) → VDC (уровень 1)" " vdcs = getVDCs(); → дает vdcs в массиве, который имеет имена, id и полигональные координаты зоны = 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)}
    }
}