Search code examples
pythondelaunay

How to select edges by criterion?

I'm using Python 3.7.

There is a set of points. I generate Delaunay triangulation through these points.

import numpy as np
points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1], [1.5, 0.6], [1.2, 0.5], [1.7, 0.9], [1.1, 0.1]])
from scipy.spatial import Delaunay
tri = Delaunay(points)

Calculating edge lengths as dict1:

simplices = points[tri.simplices]
edge_lengths = {}
for point in points:
    key = tuple(point)
    vertex_edges = edge_lengths.get(key,[])
    adjacency_mask = np.isin(simplices, point).all(axis=2).any(axis=1)
    for simplex in simplices[adjacency_mask]:
        self_mask = np.isin(simplex, point).all(axis=1)
        for other in simplex[~self_mask]:
            dist = np.linalg.norm(point - other)
            if dist not in vertex_edges:
                vertex_edges.append(dist)
    edge_lengths[key] = vertex_edges

Calculating mean of the edge lengths (connected to the same point) as dict2:

local_mean_edge_lengths = {}
for point in points:
    key = tuple(point)
    local_mean_edge_lengths[key] = np.mean(edge_lengths[key])

I get two dicts:

In[1]:edge_lengths

Out[1]: 
{(0.0, 0.0): [1.4142135623730951, 1.1, 1.3, 1.0],
 (0.0, 1.1): [1.004987562112089, 1.3416407864998738, 1.4866068747318506],
 (1.0, 0.0): [1.4866068747318506,0.5385164807134504,0.7810249675906654,1.140175425099138,0.14142135623730956],
 (1.0, 1.0): [1.004987562112089,1.4142135623730951,0.5385164807134504,0.6403124237432849,0.7071067811865475],
 (1.5, 0.6): [0.6403124237432849, 0.36055512754639896, 0.31622776601683794, 0.6403124237432848],
 (1.2, 0.5): [0.5385164807134504, 1.3, 0.31622776601683794, 0.41231056256176607],
 (1.7, 0.9): [0.7071067811865475, 0.36055512754639896],
 (1.1, 0.1): [0.14142135623730956, 0.41231056256176607, 0.6403124237432848]}


In[2]:local_mean_edge_lengths

Out[2]: 
{(0.0, 0.0): 1.2035533905932738,
 (0.0, 1.1): 1.2777450744479377,
 (1.0, 0.0): 0.8175490208744828,
 (1.0, 1.0): 0.8610273620256933,
 (1.5, 0.6): 0.4893519352624517,
 (1.2, 0.5): 0.6417637023230136,
 (1.7, 0.9): 0.5338309543664732,
 (1.1, 0.1): 0.3980147808474535}

How to select edges by criterion?

Like,

for the key(0.0, 0.0),

there are 4 edge lengths(1.4142135623730951, 1.1, 1.3, 1.0) and 1 mean edge length( 1.2035533905932738)

edge_length1 = 1.4142135623730951 > 1.2035533905932738, remove this edge;

edge_length2 = 1.1 < 1.2035533905932738, remain this edge;

edge_length3 = 1.3 > 1.2035533905932738, remove this edge;

edge_length4 = 1.0 < 1.2035533905932738, remain this edge;

Same as other keys.

How to plot the new Delaunay triangulation (after remove the edges)?

Solution

  • Have a look at my previous answer on identifying large edges in a Delaunay triangulation and plotting the results. The figure below was taken from there, where the large edges are colored in cyan. With small modifications it is suitable for your problem. enter image description here

    Note that you cannot remove edges from the Delaunay triangulation itself, as this will invalidate the triangulation. The set of edges passing your criterion will therefore need to be represented in a separate data structure. In my answer they are represented as a set of (i, j) pairs, i.e., an edge list, which you can then construct a graph with, for example with the networkx library using the G.add_edges_from method.