python - Python：用相交线计算形状中的特定子形状

Question

我想用 python 计算更大形状的特定子形状。例如：我画了一个三角形。我画了一条对角线，将三角形切成两半。现在程序显示用相交线绘制这个三角形并计算绘制的三角形数量。在这种情况下，它应该返回三个，因为在开始时绘制了一个大三角形，并且在将第一个三角形切成两半时创建了两个三角形。我不知道从哪里开始，也不知道选择哪个库。有人有想法吗？

Answer 1

我的方法是首先找到所有的顶点和线的交点（在三角形内部），然后遍历所有点的组合，看看是否可以形成一个三角形。我正在使用库来检查交叉点。

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))

输出：

#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)

---

可视化：

import matplotlib.pyplot as plt

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

它绘制：