Come ottenere l’elenco dei punti all’interno di un poligono in python?

Ho cercato un sacco e cant trovare qualsiasi risposta concreta alla mia domanda. Ho un poligono. Per esempio:

    [(86, 52), (85, 52), (81, 53), (80, 52), (79, 48), (81, 49), (86, 53),
     (85, 51), (82, 54), (84, 54), (83, 49), (81, 52), (80, 50), (81, 48),
     (85, 50), (86, 54), (85, 54), (80, 48), (79, 50), (85, 49), (80, 51),
     (85, 53), (82, 49), (83, 54), (82, 53), (84, 49), (79, 49)]

Voglio ottenere un elenco di tutti i punti all’interno di questo confine poligono. Ho sentito un sacco di poligono triangolazione tecniche o lineare/flood/intersezione/… algoritmi di riempimento. ma davvero non riesco a venire con un modo efficiente di applicazione del presente. Questo poly è piccolo, immaginare un poligono con 1 miliardo di punti. Io ora sto usando il PIL disegnare un poligono per riempire i poli di colore rosso e loop all’interno di esso per trovare i punti rossi. Questo è un terribilmente lenti tecnica:

def render(poly, z):
    xs = [i[0] for i in poly]
    ys = [i[1] for i in poly]
    minx, maxx = min(xs), max(xs)
    miny, maxy = min(ys), max(ys)
    X = maxx - minx + 1
    Y = maxy - miny + 1
    newPoly = [(x - minx, y - miny) for (x, y) in polygons]
    i = Image.new("RGB", (X, Y))
    draw = ImageDraw.Draw(i)
    draw.polygon(newPoly, fill="red")
    # i.show()
    tiles = list()
    w, h = i.size
    print w, h
    for x in range(w):
        for y in range(h):
            data = i.getpixel((x, y))
            if data != (0, 0, 0):
                tiles.append((x + minx, y + miny))

    return tiles

Sto cercando una Divinatori modo per risolvere questo problema.
Grazie a tutti voi.

  • non shapely hanno nulla da offrire? pypi.python.org/pypi/Shapely
  • Ho usato formosa, ma i cant trovare nulla per questo problema. Grazie, farò delle ricerche che.
  • Probabilmente stai cercando: rosettacode.org/wiki/Ray-casting_algorithm.
  • Beh, La funzione nel tuo link dà e punto e da un foglio di verificare se il suo interno o non. Non è quello di cui ho bisogno. Posso creare manualmente una griglia e loop per tutti gli elementi. ma Im in cerca di una più straight-forward metodo. Grazie btw.
  • Hai trovato una risposta alla tua domanda? Ora sto cercando una soluzione simile, ho le coordinate di 100.000 punti e le coordinate di alcuni poligoni. Ho bisogno di rimuovere quei punti che sono all’interno di questi poligoni
  • Sì, ho scritto in Python C modulo basato su un PiintInPoly algoritmo. Formosa ha anche la funzione.

InformationsquelleAutor Farsheed | 2014-01-24



5 Replies
  1. 8

    Suggerisco di utilizzare matplotlib contains_points()

    from matplotlib.path import Path
    
    tupVerts=[(86, 52), (85, 52), (81, 53), (80, 52), (79, 48), (81, 49), (86, 53),
     (85, 51), (82, 54), (84, 54), (83, 49), (81, 52), (80, 50), (81, 48),
     (85, 50), (86, 54), (85, 54), (80, 48), (79, 50), (85, 49), (80, 51),
     (85, 53), (82, 49), (83, 54), (82, 53), (84, 49), (79, 49)]
    
    
    x, y = np.meshgrid(np.arange(300), np.arange(300)) # make a canvas with coordinates
    x, y = x.flatten(), y.flatten()
    points = np.vstack((x,y)).T 
    
    p = Path(tupVerts) # make a polygon
    grid = p.contains_points(points)
    mask = grid.reshape(300,300) # now you have a mask with points inside a polygon
    • è possibile utilizzare np.indici() per creare un array con le coordinate
  2. 2

    È possibile utilizzare un numpy matrice come un immagine binaria, che può essere utilizzato con Opencv, ad esempio, o altri di elaborazione delle immagini librerie,
    Soluzione 1
    Così una matrice di dimensioni L x H dove

    L=max(x) - min (x)
    H=max(y) - min (y)

    Come entry che avete la vostra lista di tuple(x,y) che hai dato al di sopra della quale nome è poly per esempio :

    import numpy as np
    matrix =np.zeros((L,H),dtype=np.int32) # you can use np.uint8 if unsigned x ,y

    Così ora abbiamo una matrice di Dimensioni L x H riempito con 0, abbiamo messo 1 ora al poligono punti

    Penso che si può facilmente fare che

    matrix[poly]=1  # which will put 1 at each (x,y) of the list **poly**

    dobbiamo interpretare questo come un file binario (nero/bianco) immagine che hanno un contorno disegnato su di esso
    Immaginiamo di voler rilevare questo nuovo contorno

    import cv2 # opencv import
    ContoursListe,hierarchy = cv2.findContours(self.thresh,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_NONE)
    poly2=ContoursListe[0] # we take the first only contour

    Nota : poly2 è che contiene un elenco di punti del poligono e tutti i punti che la compongono, intendo tutti i punti di ogni vertici del poligono che è quello che avete bisogno può trovare utile
    !! è possibile utilizzare cv2.CHAIN_APPROX_SIMPLE parametro per ottenere poly2 contenente solo fine i punti del poligono di linee che è più leggero e che è stato il nostro contributo 🙂
    importante :il tipo di poly2 è array numpy ,la sua forma è (n,1,2) e non (n,2)

    Ora dobbiamo tracciare questo profilo è su questa immagine(matrice) e riempiono troppo 🙂

    cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1)
    thickness=-1

    ora abbiamo una matrice in cui c’è 1 su ogni punti di formatura e riempimento il poligono , lo “spessore=-1” è costretto a riempire questo profilo, si può mettere insieme spessore = 1 per ottenere solo i confini
    se si desidera tradurre, è possibile farlo aggiungendo il parametro offset(xtran,ytrans)

    per ottenere gli indici di tutti questi punti di chiamare semplicemente

    list_of_points_indices=numpy.nonzero(matrix)

    Soluzione 2

    Che è più intelligente è quello di trasformare direttamente la tua lista di punti (poli) per un contorno formato (poly2) e disegnare la matrice

    poly2=poly.reshape(-1,1,2).astype(np.int32)

    e disegnare sulla Matrice matrice

    matrix =np.zeros((L,H),dtype=np.int32)
    
    cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1)

    E ottenere l’elenco di questi punti con :

    list_of_points_indices=numpy.nonzero(matrix)

    Giocare con spessore compilare o meno il poligono , vedere la soluzione 1 per ulteriori dettagli.

  3. 2

    Edificio su RemcoGerlich risposta ecco una convalidato funzione:

    import numpy as np
    import mahotas
    
    def render(poly):
        """Return polygon as grid of points inside polygon.
    
        Input : poly (list of lists)
        Output : output (list of lists)
        """
        xs, ys = zip(*poly)
        minx, maxx = min(xs), max(xs)
        miny, maxy = min(ys), max(ys)
    
        newPoly = [(int(x - minx), int(y - miny)) for (x, y) in poly]
    
        X = maxx - minx + 1
        Y = maxy - miny + 1
    
        grid = np.zeros((X, Y), dtype=np.int8)
        mahotas.polygon.fill_polygon(newPoly, grid)
    
        return [(x + minx, y + miny) for (x, y) in zip(*np.nonzero(grid))]

    Esempio:

    poly = [
        [0, 0],
        [0, 10],
        [10, 10],
        [10, 0]
    ]
    
    plt.figure(None, (5, 5))
    x, y = zip(*render(poly))
    plt.scatter(x, y)
    x, y = zip(*poly)
    plt.plot(x, y, c="r")
    plt.show()

    Come ottenere l'elenco dei punti all'interno di un poligono in python?

  4. 2

    Penso che il disegno del poligono e di riempimento è un buon inizio, si sta andando a bisogno di qualcosa di simile e comunque tali algoritmi sono solitamente regolati in c, Ma non usare una immagine RGB, utilizzare un bianco/nero, di immagini, e utilizzare numpy.where() per trovare il pixel in cui è 1.

    Secondo questa domanda, il mahotas biblioteca dispone di una fill_polygon una funzione che funziona con array numpy.

    Sto iniziando il codice riportato di seguito da una funzione (vorrei sottrarre il minx e maxx troppo), ma di notare che non posso provarlo a tutti, io non sono sul mio computer dello sviluppatore.

    import numpy as np
    import mahotas
    
    def render(poly): # removed parameter 'z'
        xs = [i[0] for i in poly]
        ys = [i[1] for i in poly]
        minx, maxx = min(xs), max(xs)
        miny, maxy = min(ys), max(ys)
        X = maxx - minx + 1
        Y = maxy - miny + 1
        newPoly = [(x - minx, y - miny) for (x, y) in poly]           
    
        grid = np.zeros((X, Y), dtype=np.int8)
        mahotas.polygon.fill_polygon(newPoly, grid)
    
        return [(x + minx, y + miny) for (x, y) in np.where(grid)]
    • Io la sto sperimentando. Il primo punto dovrebbe essere “da mahotas importazione poligono”. Mi permetta di testare più.
    • Ok, il Tuo codice è 38% più lento del PIL il metodo di riempimento. testato con i suoi 1,3 M di poligoni. Ci vuole 5.6 sec per il PIL e il 6,7 sec per np+mahotas.
    • Ah, interessante. Che è di meno che il 38% di differenza, però :-). Si può riempire il poligono con il PIL e l’uso np.dove trovare i punti? Penso PIL le immagini di array numpy troppo?
    • ok, mi permetta di eseguire il test.
    • Mi chiedo quanto tempo è trascorso sottraendo minx e miny e aggiungere in un secondo momento. Non si può davvero pensare a un modo per evitare, però, se il tuo poligoni sono arbitrarie indici.
    • Il mio problema è ora come posso utilizzare np.dove con un img. Siamo in grado di utilizzare np.aaray(img) ha ottenuto la conversione di immagine matrice. ma come utilizzare dove e come posso convertire normale elenco delle piastrelle?
    • Per ottenere velocità, si dovrebbe fare quei loop con numpy matrici: newPoly = poly + [minx, miny]

  5. 0

    Provare questo codice. poly_coords sono le coordinate del poligono, ‘coord’ è coordinata del punto che si desidera controllare se è all’interno del poligono.

    def testP(coord, poly_coords):
        """
        The coordinates should be in the form of list of x and y
        """
        test1 = n.array(poly_coords)
        test2 = n.vstack((poly_coords[1:], poly_coords[:1]))
        test  = test2-test1
        m = test[:,1]/test[:,0]
        c = test1[:,1]-m*test1[:,0]
        xval = (coord[1]-c)/m
        print 'xVal:\t'; print xval
        print (test1[:,0]-xval)*(test2[:,0]-xval)
        check = n.where((xval>=coord[0])&((test1[:,0]-xval)*(test2[:,0]-xval)<0))[0]
        print check
        print len(check)
        if len(check)%2==0:
            return False
        else:
            return True

    Se volete rendere ancora più veloce, prendere la parte di algo relative al poligono, slope e offset e il resto del codice, utilizzando la ‘mappa’ della funzione. Qualcosa di simile a questo:

    test1 = n.array( your polygon)
    test2 = n.vstack((test1[1:], test1[:1]))
    test  = test2-test1
    m = test[:,1]/test[:,0]
    c = test1[:,1]-m*test1[:,0]
    
    def testP(coord):
        """
        The coordinates should be in the form of list of x and y
        """
        global test, test1, test2, m,c
        xval = (coord[1]-c)/m
        check = n.where((xval>=coord[0])&((test1[:,0]-xval)*(test2[:,0]-xval)<0))[0]
        if len(check)%2==0:
            return False
        else:
            return True
    coords = n.array(( your coords in x,y ))
    map (testP, coords)

    È possibile rimuovere ‘la stampa’ i comandi, se si desidera. Questo codice è per python 2.7

    • Per favore, spiegare il your polygon e your coords in x,y? Sembra che il your polygon significa qualcosa come poly = [[0, 0], [0, 10], [10, 10], [10, 0]]. Ma non so cosa e come è your coords in x,y esattamente!
    • Per il poligono, hai assolutamente ragione. ‘coords x,y’ si riferisce alle coordinate del punto di controllo per essere all’interno di un poligono. Le coordinate devono essere un array numpy come (5,6) dove la posizione di un punto dell’asse x è 5 e l’asse y è 6

Lascia un commento