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

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

15 голосов
/ 29 января 2011

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

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

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

Ответы [ 5 ]

28 голосов
/ 29 января 2011

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

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

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

1 голос
/ 31 июля 2013

Может быть, эта часть кода поможет вам: 

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;
    }
}
1 голос
/ 29 января 2011

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

0 голосов
/ 16 октября 2014

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

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

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

"" Зона (уровень 3) -> Район (уровень 2) -> VDC (уровень 1) "" vdcs =getVDCs ();-> выдает vdcs в массиве, который имеет имя, id и координаты многоугольника zone = getZones ();-> дает зоны в массиве с координатами имени, идентификатора и полигона 

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)}
    }
}
0 голосов
/ 29 января 2011

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

...