numpymatplotlibgeometrypolygonsconvex-polygon

Polygons from network of connected points


Given an array of 2D points (#pts x 2) and an array of which points are connected to which (#bonds x 2 int array with indices of pts), how can I efficiently return an array of polygons formed from the bonds?

There can be 'dangling' bonds (like in the top left of the image below) that don't close a polygon, and these should be ignored.

Here's an example: an example image

import numpy as np
xy = np.array([[2.72,-2.976], [2.182,-3.40207],
[-3.923,-3.463], [2.1130,4.5460], [2.3024,3.4900], [.96979,-.368],
[-2.632,3.7555], [-.5086,.06170], [.23409,-.6588], [.20225,-.9540],
[-.5267,-1.981], [-2.190,1.4710], [-4.341,3.2331], [-3.318,3.2654],
[.58510,4.1406], [.74331,2.9556], [.39622,3.6160], [-.8943,1.0643],
[-1.624,1.5259], [-1.414,3.5908], [-1.321,3.6770], [1.6148,1.0070],
[.76172,2.4627], [.76935,2.4838], [3.0322,-2.124], [1.9273,-.5527],
[-2.350,-.8412], [-3.053,-2.697], [-1.945,-2.795], [-1.905,-2.767],
[-1.904,-2.765], [-3.546,1.3208], [-2.513,1.3117], [-2.953,-.5855],
[-4.368,-.9650]])

BL= np.array([[22,23], [28,29], [8,9],
[12,31], [18,19], [31,32], [3,14],
[32,33], [24,25], [10,30], [15,23],
[5,25],  [12,13], [0,24],  [27,28],
[15,16], [5,8],   [0,1],   [11,18],
[2,27],  [11,13], [33,34], [26,33],
[29,30], [7,17],  [9,10],  [26,30],
[17,22], [5,21],  [19,20], [17,18],
[14,16], [7,26],  [21,22], [3,4],
[4,15],  [11,32], [6,19],  [6,13],
[16,20], [27,34], [7,8],   [1,9]])

Solution

  • I can't tell you how to implement it with numpy, but here's an outline of a possible algorithm:

    1. Add a list of attached bonds to each point.
    2. Remove the points that have only one bond attached, remove this bond as well (these are the dangling bonds)
    3. Attach two boolean markers to each bond, indicating if the bond has already been added to a polygon in one of the two possible directions. Each bond can only be used in two polygons. Initially set all markers to false.
    4. Select any initial point and repeat the following step until all bonds have been used in both directions:
    5. Select a bond that has not been used (in the respective direction). This is the first edge of the polygon. Of the bonds attached to the end point of the selected one, choose the one with minimal angle in e.g. counter-clockwise direction. Add this to the polygon and continue until you return to the initial point.

    This algorithm will also produce a large polygon containing all the outer bonds of the network. I guess you will find a way to recognize this one and remove it.