[FIXED] Find aligned and nearly-aligned segments in a 2D triangular mesh

Issue

I have a cloud of 2D points with the structure (x, y, index)

example:

pts = [[0,0,1],[0,1,2],[0,2,3],[1,0,4],[1,1,5],[1,2,6],[2,0,7],[2,1,8],[2,2,9]] 

and a series of segments with the structure (index1, index2) that connect these points 2 by 2:

segs = [[1,2],[1,4],[1,5],[2,3],[2,5],[3,5],[3,6],[4,5],[4,7],[4,8],[5,6],[5,8],[5,9],[6,9],[7,8],[8,9]]

The segments always connect only two points, they never pass through a third point.

How would I detect the aligned segments and make longer segments with n indices, when I should use the segments in seg only once?

aligned = [[1,2,3],[1,4,7],[1,5,9],[2,5,8],[3,6,9],[3,5],[4,5,6],[4,8],[7,8,9]]

Now say that the points are not perfectly aligned:

pts = [[0.002,0.1,1],[0.0003,1.003,2],[-0.01,2.11,3],[1.01,0.101,4],[1.0005,1.2,5],[1.25,2.01,6],[2.007,-0.12,7],[1.996,1.1,8],[2.03,2.1,9]] 

I want to I connect nearly aligned segments if the angle between the segments is nearly null, defined by a tolerance of, for example, 3°

I have tried many methods but I couldn't succeed. This has to be done on massive nets of 10k+ points.

This code recreates my examples:

import numpy as np
import matplotlib.pyplot as plt

#pts = np.array([[0,0,1],[0,1,2],[0,2,3],[1,0,4],[1,1,5],[1,2,6],[2,0,7],[2,1,8],[2,2,9]])
pts = np.array([[0.002,0.1,1],[0.0003,1.003,2],[-0.01,2.11,3],[1.01,0.101,4],[1.0005,1.2,5],[1.25,2.01,6],[2.007,-0.12,7],[1.996,1.1,8],[2.03,2.1,9]])

indices = pts[:,2].astype(int)

seg = np.array([[1,2],[1,4],[1,5],[2,3],[2,5],[3,5],[3,6],[4,5],[4,7],[4,8],[5,6],[5,8],[5,9],[6,9],[7,8],[8,9]])

for s in seg:
    i1, i2 = s
    segment = np.array((pts[indices == i1][0], pts[indices == i2][0]))
    plt.plot(segment[:,0],segment[:,1],color="black")
plt.axis("equal")
plt.show()

aligned = np.array([[1,2,3],[1,4,7],[1,5,9],[2,5,8],[3,6,9],[3,5],[4,5,6],[4,8],[7,8,9]],dtype=object)

for a in aligned:
    p = []
    for index in a:
        p += [pts[indices == index][0]]
    p = np.array(p)
    print(p)
    plt.plot(p[:, 0], p[:, 1])

plt.axis("equal")
plt.show()

NOTE: this question is formulated differently and more universally than my previous question here Python detect aligned segments in a mesh I would appreciate that it is not considered a duplicate of it.

Solution

with these general assumption that not necessarily all indices exist.

I would try an algorithm like this: (python/pseudocode)

point_dict = dictionary( index : point )
seg_set = set( seg )
seg_endpoints = dictionary( index of point : list of segments containing this point )

result = []
while not empty(seg_set):
    segment = seg_set.pop()
    result.append(segment)
    left, right = segment.left, segment.right
    # going to the left
    while True:
        possible_lefts = seg_endpoints[left]
        additional_left = get_line_to_left(possible_lefts)
        if additional_left is None:
            break
        remove_additional_left_from_seg_set()
        remove_additional_left_from_seg_endpoints()
        left = additional_left.left
        results[-1].prepend(left) # not real syntax offcource
    # going to the right
    while True:
        possible_rights = seg_endpoints[left]
        additional_right = get_line_to_right(possible_rights)
        if additional_right is None:
            break
        remove_additional_right_from_seg_set()
        remove_additional_right_from_seg_endpoints()
        left = additional_right.right
        results[-1].append(right) # this is real syntax :)

I left out a lot of implementation details, but since you mentioned you tried different methods without too much success I hope you can at least get some ideas from this algorithm. One important implementation detail is how to store the segments in the seg_endpoints and how to delete a specific segment out of this one.

One possibility is to convert the segments to a dataclass and than you can link to these segments. Another is to keep track of where all these segments are with some extra indices.

In any case, for networks of tens of thousands of points I certainly think making these dictionaries will save your algorithm a lot of time.

Good luck!

Answered By - DwightFromTheOffice