Controllare se poligono è all'interno di un poligono

Question

Ieri stavo cercando di verificare se un punto è stato all'interno di un poligono e ha trovato questa grande script: https://github.com/tparkin/Google-Maps-Point-in-Polygon

Ma oggi al lavoro mi è stato detto che il nostro cliente ha bisogno di controllare se un poligono è dentro un altro poligono. Mi chiedo se ci sia una formula in cui posso prendere, diciamo, due coordinate (invece di una per controllare un punto), e da quelle due coordinate generare un rettangolo e verificare se quel rettangolo si trova all'interno di un poligono.

Non so se sto facendo una domanda stupida (un insegnante in liceo diceva "non ci sono domande stupide, ci sono solo sciocchi che non chiedono"), ma se non lo fai capiscimi totalmente ma solo un po ', sarei grato se mi dicessi solo da dove cominciare.

Answer 1

Eseguire i test line intersection per ciascuna coppia di linee, una per ciascun poligono. Se nessuna coppia di linee si interseca e uno dei punti finali della linea del poligono A è all'interno del poligono B, allora A è interamente dentro B.

Quanto sopra funziona per qualsiasi tipo di poligono. Se i poligoni sono convessi, è possibile saltare i test di intersezione della linea e verificare che tutti gli endpoint della linea A siano all'interno B.

Se davvero necessario, è possibile accelerare i test di intersezione della linea utilizzando sweep line algorithm.

Answer 2

Il poligono è convesso? Perché, se lo è, puoi semplicemente eseguire lo script "Punto in poligono" per entrambi gli "angoli" del tuo "rettangolo". Se entrambi gli angoli sono dentro e il poligono non ha "curve" verso l'interno, allora non dovrebbe essere l'intero rettangolo?

Answer 3

Prima verifica che uno dei punti d'angolo nel poligono sia all'interno dell'altro poligono utilizzando lo script. Quindi controlla se una qualsiasi delle linee nel poligono attraversa una delle linee nell'altro poligono. Se non lo fanno, il poligono si trova all'interno dell'altro poligono.

Answer 4

Forse questa parte del codice può aiutare a:

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

perché non utilizzare JTS? Ha un sacco di porte per altre lingue, tra cui C++, JavaScript e .NET.

Answer 6

Ho dovuto trovare una soluzione simile. Ecco quello che ho finora:

1. Prima Presi tutto il livello coordinate 1 poligono in un array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..]
2. poi recuperato tutti i livello 3 poligoni e tracciati
3. Quindi, per ogni livello 1 poligono, i controllato se ciascuna delle coordinate del poligono era all'interno del livello 3 tracciata coordinata con google.maps.geometry.poly.containsLocation(latLng, pol)
4. Se restituito true contatore salirebbe
5. Infine se il contatore è uguale alla lunghezza di detta matrice, il risultato sarebbe vero (il poligono di livello 1 si trova all'interno del poligono di livello 3).

mio algoritmo simile a questa:

"" Zone (livello 3) -> Distretto (livello 2) -> VDC (livello 1) "" VDC = getVDCs(); -> fornisce vdcs in una matrice che ha zone coordinate id, nome e poligono = getZones(); -> dà zone in una matrice che ha nome, id e poligono coordina

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