Skip to content

Instantly share code, notes, and snippets.

@hellpanderrr
Last active April 27, 2022 22:51
Show Gist options
  • Save hellpanderrr/2c08af0f07eed4782234 to your computer and use it in GitHub Desktop.
Save hellpanderrr/2c08af0f07eed4782234 to your computer and use it in GitHub Desktop.
Concave hull in python using scipy and networkx
from scipy.spatial import Delaunay, ConvexHull
import networkx as nx
 
points = [ [0,0],[0,50],[50,50],[50,0],[0,400],[0,450],[50,400],[50,450],[700,300],[700,350],[750,300],[750,350],
          [900,600],[950,650],[950,600],[900,650]
]
def concave(points,alpha_x=150,alpha_y=250):
    points = [(i[0],i[1]) if type(i) <> tuple else i for i in points]
    de = Delaunay(points)
    dec = []
    a = alpha_x
    b = alpha_y
    for i in de.simplices:
        tmp = []
        j = [points[c] for c in i]
        if abs(j[0][1] - j[1][1])>a or abs(j[1][1]-j[2][1])>a or abs(j[0][1]-j[2][1])>a or abs(j[0][0]-j[1][0])>b or abs(j[1][0]-j[2][0])>b or abs(j[0][0]-j[2][0])>b:
            continue
        for c in i:
            tmp.append(points[c])
        dec.append(tmp)
    G = nx.Graph()
    for i in dec:
            G.add_edge(i[0], i[1])
            G.add_edge(i[0], i[2])
            G.add_edge(i[1], i[2])
    ret = []
    for graph in nx.connected_component_subgraphs(G):
        ch = ConvexHull(graph.nodes())
        tmp = []
        for i in ch.simplices:
            tmp.append(graph.nodes()[i[0]])
            tmp.append(graph.nodes()[i[1]])
        ret.append(tmp)
    return ret  
    #return [graph.nodes() for graph in nx.connected_component_subgraphs(G)] - all points inside the shape
    
concave(points)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment