How to find closed objects among an array of lines?

Question

I have a list of tuples. Each tuple contains coordinate points (x, y, x1, y1,...) forming a line. All these lines form a drawing.

There are 5 closed objects in this picture. How can I get the number of these objects with their coordinates?

Coordinates_list = [(939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005), (939, 1002, 939, 900), (939, 900, 961, 916), (961, 916, 1031, 898), (1031, 898, 1080, 906), (1080, 906, 1190, 896), (1190, 896, 1225, 897), (1223, 1005, 1225, 897), (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)]

I tried to use the DFS (Depth First Search) Algorithm, but it always returned fewer objects than there actually were. But the data here is presented differently - here there are no more than two points in the tuple, but this does not change the drawing

def find_closed_figures(lines):
    def dfs(line_idx, visited):
        visited.add(line_idx)
        for neighbor_idx, line in enumerate(lines):
            if neighbor_idx not in visited and lines[line_idx][3:6] == line[0:3]:
                dfs(neighbor_idx, visited)

    closed_figures_count = 0
    visited_lines = set()
    for idx, line in enumerate(lines):
        if idx not in visited_lines:
            dfs(idx, visited_lines)
            closed_figures_count += 1

    return closed_figures_count

coordinates_list = [(939, 1002, 0, 984, 993, 0), (984, 993, 0, 998, 1001, 0), (998, 1001, 0, 1043, 995, 0), (1043, 995, 0, 1080, 1004, 0), (1080, 1004, 0, 1106, 994, 0), (1106, 994, 0, 1147, 1003, 0), (1147, 1003, 0, 1182, 995, 0), (1182, 995, 0, 1223, 1005, 0), (939, 1002, 0, 939, 900, 0), (939, 900, 0, 961, 916, 0), (961, 916, 0, 1031, 898, 0), (1031, 898, 0, 1080, 906, 0), (1080, 906, 0, 1190, 896, 0), (1190, 896, 0, 1225, 897, 0), (1223, 1005, 0, 1225, 897, 0), (939, 1002, 0, 1031, 898, 0), (1031, 898, 0, 1106, 994, 0), (1106, 994, 0, 1190, 896, 0), (1190, 896, 0, 1182, 995, 0)]


closed_figures_count = find_closed_figures(coordinates_list)
print(closed_figures_count)

Answer 1

Here is a condensed version of Grismar's answer, where he has a good explanation as well. I just removed the manual search for segments and treated each point as a node directly.

import networkx as nx

lines = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]
point_lists = [[pair for pair in zip(line[::2],line[1::2])] for line in lines]
edges = [segment for point_list in point_lists for segment in zip(point_list[:-1], point_list[1:])]
G = nx.from_edgelist(edges)
cycles = list(nx.chordless_cycles(G))
print('The number of chord-less cycles:', len(cycles))
print('The cycles:')
for cycle in cycles: print("\t", cycle)

Answer 2

The data you provided is provided as a series of 'lines', which are series of segments from (x, y) pair to (x, y) pair in a plane. You've provided a graphic that corresponds to the data.

Looking at the graphic, it's clear that the data can be seen as a network (or 'graph' as mathematicians would call it) and the problem you're looking to solve is to find all the chord-less cycles in this network. A cycle is a series of points (vertices) in the network that loops back on itself. A chord-less cycles is a cycle so that no line cuts across the cycle - for example, if you combined shape 1 and 2, you'd still have a shape, but it would have a line cutting across it, so it would not be chord-less.

A library like networkx has functions that do all the hard work, once you convert your data to an actual graph or network.

Look at this code:

from turtle import Turtle, setworldcoordinates
import networkx as nx
import matplotlib.pyplot as plt

# the example data
data = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]


def draw_segments(lines, llx, lly, urx, ury):
    # draw data in the format provided as a turtle graphic
    t = Turtle()

    setworldcoordinates(llx, lly, urx, ury)

    t.hideturtle()
    t.speed(0)

    for line in lines:
        start, rest = line[0:2], line[2:]
        rest = [(rest[i], rest[i + 1]) for i in range(0, len(rest), 2)]
        t.penup()
        t.setposition(*start)
        t.pendown()
        for point in rest:
            t.setposition(*point)


def lines_to_segments(lines):
    # breaks up `lines` into unique segments with a start and end point
    result = []
    for line in lines:
        assert len(line) % 2 == 0  # the number of coordinates has to be even for each 'line'
        for i in range(0, len(line) - 2, 2):
            # start always to the left of end, to be able to check for unique segments
            if line[i] < line[i + 2]:
                segment = (line[i], line[i + 1], line[i + 2], line[i + 3])
            else:
                segment = (line[i + 2], line[i + 3], line[i], line[i + 1])
            # only add the segment if it wasn't there already
            if segment not in result:
                result.append(segment)
    return result


def network_from_segments(segments):
    g = nx.Graph()
    for segment in segments:
        g.add_edge((segment[0], segment[1]), (segment[2], segment[3]))
    return g


def main():
    # to see the data as a graphic:
    # draw_segments(data, 800, 800, 1400, 1100)

    # break up the lines into individual edges
    data_segments = lines_to_segments(data)
    # and turn those into a networkx graph
    data_g = network_from_segments(data_segments)

    # show a graphic of the network using matplotlib (optional)
    # nx.draw(data_g, with_labels=True, font_weight='bold')
    # plt.show()

    print('The network is planar:', nx.is_planar(data_g))

    # all the heavy lifting is here, networkx can find the chord-less cycles
    cycles = list(nx.chordless_cycles(data_g))
    print('The number of chord-less cycles:', len(cycles))
    print('The cycles:')
    for cycle in cycles:
        print(cycle)

    input('Press Enter to continue...')


if __name__ == "__main__":
    main()

Comment out the sections that draw the original graphic or the corresponding network. If you run it as is, it will output the number of 'shapes' or rather chord-less cycles in the graph defined by the data you have.

Just the code that solves the problem:

import networkx as nx

data = [
    (939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005),
    (939, 1002, 939, 900),
    (939, 900, 961, 916),
    (961, 916, 1031, 898),
    (1031, 898, 1080, 906),
    (1080, 906, 1190, 896),
    (1190, 896, 1225, 897),
    (1223, 1005, 1225, 897),
    (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)
]


def lines_to_segments(lines):
    # breaks up `lines` into unique segments with a start and end point
    result = []
    for line in lines:
        assert len(line) % 2 == 0  # the number of coordinates has to be even for each 'line'
        for i in range(0, len(line) - 2, 2):
            # start always to the left of end, to be able to check for unique segments
            if line[i] < line[i + 2]:
                segment = (line[i], line[i + 1], line[i + 2], line[i + 3])
            else:
                segment = (line[i + 2], line[i + 3], line[i], line[i + 1])
            # only add the segment if it wasn't there already
            if segment not in result:
                result.append(segment)
    return result


def network_from_segments(segments):
    g = nx.Graph()
    for segment in segments:
        g.add_edge((segment[0], segment[1]), (segment[2], segment[3]))
    return g


def main():
    # break up the lines into individual edges
    data_segments = lines_to_segments(data)
    # and turn those into a networkx graph
    data_g = network_from_segments(data_segments)

    # all the heavy lifting is here, networkx can find the chord-less cycles
    cycles = list(nx.chordless_cycles(data_g))
    print('The number of chord-less cycles:', len(cycles))


if __name__ == "__main__":
    main()