Python: count specific subshapes in shape with intersecting lines

Question

I want to count specific subshapes of a bigger shape with python. For expample: I draw a Triangle. I draw a diagonal line cutting the triangle in half. Now the program show draw this triangle with the intersecting line and count the amount of triangles drawn. In this case, it should return three because there is the big triangle drawn in the beginning and the two triangles created when cutting the first on in half. I have no clue where to start nor which library to choose. Has someone an idea?

Answer 1

My approach to this is to first find all the vertices and intersection of the lines (inside the triangle), and then loop through all combinations of points to see if that can form a triangle. I'm using the library shapely to check intersections.

from shapely.geometry import LineString, Point, Polygon

# define the triangle and lines
triangle = Polygon([(0,0), (5,5), (0,5)])
lines = [
    LineString([(0,0), (1,6)]),
    LineString([(-1,2), (6,6)]),
]

# infer lines of the triangle
triangle_coords = triangle.exterior.coords
triangle_lines = [
    LineString([triangle_coords[0], triangle_coords[1]]),
    LineString([triangle_coords[1], triangle_coords[2]]),
    LineString([triangle_coords[2], triangle_coords[0]]),
]

# get all lines to calculate intersections
all_lines = triangle_lines + lines

# find all vertex and intersections
# add vertices of trangle first
vertices = set([xy for l in triangle_lines for xy in l.coords])

# find intersection of lines
for i, line in enumerate(all_lines):
    # find intersection with trangle
    for line2 in all_lines:
        intersect = line2.intersection(line)
        
        if not intersect or intersect.geom_type == 'LineString':
            # intersection is not a point, line overlap
            continue
        
        for xy in intersect.coords:
            point = Point(xy)
            if not triangle.contains(point) and not triangle.touches(point):
                # line intersection outside trangle
                continue
            
            vertices.add(xy)

def linked(xy1, xy2):
    '''Check if the line (xy1, xy2) is on any lines we created'''
    my_line = LineString([xy1, xy2])
    for line in all_lines:
        intersect = my_line.intersection(line)
        if intersect and intersect.geom_type == 'LineString':
            # is intersected and the intersection is a line
            return True
    return False

# count small triangles
count = 0
for i, xy1 in enumerate(vertices):
    for j, xy2 in enumerate(vertices):
        if i >= j:
            continue
        if not linked(xy1, xy2):
            continue
        for k, xy3 in enumerate(vertices):
            if j >= k:
                continue
            if not Polygon([xy1, xy2, xy3]).is_valid:
                continue
            if not linked(xy2, xy3):
                continue
            if not linked(xy3, xy1):
                continue
            
            count += 1
            print(f'#{count}, triangle:', 
                  '({:.2f}, {:.2f})'.format(*xy1), 
                  '({:.2f}, {:.2f})'.format(*xy2), 
                  '({:.2f}, {:.2f})'.format(*xy3))

Output:

#1, triangle: (0.83, 5.00) (5.00, 5.00) (4.25, 5.00)
#2, triangle: (0.83, 5.00) (5.00, 5.00) (0.00, 5.00)
#3, triangle: (0.83, 5.00) (4.25, 5.00) (0.00, 5.00)
#4, triangle: (5.00, 5.00) (0.00, 0.00) (0.00, 5.00)
#5, triangle: (5.00, 5.00) (4.25, 5.00) (0.00, 5.00)
#6, triangle: (0.00, 0.00) (0.00, 5.00) (0.00, 2.57)

---

To visualize:

import matplotlib.pyplot as plt

for line in all_lines:
    plt.plot(*line.xy)
plt.show()

It draws: