CODEWITHSUNDEEP
algorithmline
slaviboy
slaviboy

Reputation: 1912

Fastest way to find triangles from connected line points

I want to find out a way to detect all triangles from connected lines. I have array list with all available lines called lines, and when I add another line I want to find if it creates new triangle. As shown on the image below as soon as I add new line f, that connects the points with indices 1,3. I want fast way to detect that new triangle is created and add the indices 1,3,5 to another array list called triangles.

enter image description here

// array with lines indices, each line contains two point indices
val lines: ArrayList<Int> = arrayListOf(
        0,1,  // a
        1,5,  // b
        5,4,  // c
        5,3,  // d
        5,2   // e
    )
val triangles: ArrayList<Int> = arrayListOf()

One way I came out with, is to have an array list that contains separate array lists for each point with all the indices it is connected to. For example the point with index 5 is connected to the points with indices [1,2,3,4]. So when a new line that connect the indices 3,1 is added, we can check if the array list circlesHash[3] and circlesHash[1] contains equal elements. In our case both arrays contain the index 5, that means triangle with indices 3,1,5 is created. If the array lists are sorted I can use the method Arrays.binarySearch. But if I have large amount of points for example 1000-2000 points, what is the quickest way to find if new triangle is created?

val circlesHash: ArrayList<ArrayList<Int>> = arrayListOf(  
    arrayListOf(1),               // 0   
    arrayListOf(0,5),             // 1
    arrayListOf(5),               // 2
    arrayListOf(5),               // 3
    arrayListOf(5),               // 4
    arrayListOf(1,2,3,4)          // 5
)

And another question is if there is existing algorithm to find all the existing triangles just from the indices of the existing lines. And what structure is preferable HashMaps, HashSet or some sort of Binary tree??

Upvotes: 0

Views: 218

Answers (1)

user4668606
user4668606

Reputation:

The simplest solution would be to pair edges by shared points. So two edges are paired if one end-point is the same. Then for each pair choose the two nodes that are not shared by the edges, insert an edge between and you've formed a triangle. Assuming your graph isn't a multigraph this algorithm won't produce any duplicates and finds all triangles.

Taking it from there we can create a list of edges that don't exist and will create a triangle. As pseudocode:

triangle_candidates(g):
    triangle_edges = set()

    for e1 in g.edges:
        for e2 in g.edges:
            if e1 and e2 share a node:
                a, b = nodes not shared by e1 and e2
                if a and b are not neighbors:
                    triangle_edges.add(tuple(a, b))

    return triangle_edges

creates_new_triangle(g, a, b):
    return tuple(a, b) in triangle_edges(g)

Note that tuples are assumed to be non-ordered! The above code is a demonstration of the basic principle; there's still plenty of room for optimizations in triangle_candidates.

The basic idea is to create a set of all node-pairs that are not neighbors, but would complete a cycle of length three if connected. Checking whether a new edge would create a triangle is a simple set-lookup, which should be fairly fast assuming a proper implementation.

Upvotes: 1

Related Questions