trace boundary

trace_boundary.py

import numpy as np
import cv2
import random
import math
from shapely import LineString

width, height = None, None


def line_segments_intersection(l1, l2):
    # 两个有长线段求交点
    x1, y1, x2, y2 = l1
    x3, y3, x4, y4 = l2
    a = LineString([[x1, y1], [x2, y2]])
    b = LineString([[x3, y3], [x4, y4]])
    if a.intersects(b):
        p = a.intersection(b)
        return [p.x, p.y]
    else:
        return None


def show(lines, filename, rand=False):
    image = np.zeros((width, height, 3))
    image.fill(255)
    for line in lines:
        if rand:
            color = (
                random.randint(10, 235),
                random.randint(10, 235),
                random.randint(10, 235),
            )
        else:
            color = (0, 255, 0)
        cv2.line(
            image, (int(line[0]), int(line[1])), (int(line[2]), int(line[3])), color, 1
        )
    cv2.imwrite(f"output/{filename}", image)


def polar_angle(point, pole):
    x, y = point[0] - pole[0], point[1] - pole[1]
    return math.atan2(y, x)


def intersect_and_split_segments(lines):
    intersection_points = [set() for _ in lines]
    for i, l1 in enumerate(lines):
        for j, l2 in enumerate(lines):
            if j <= i:
                continue
            p = line_segments_intersection(l1, l2)
            if p is None:
                continue
            intersection_points[i].add((p[0], p[1]))
            intersection_points[j].add((p[0], p[1]))
    intersection_points = [sorted(list(i)) for i in intersection_points]
    segments = []
    for points in intersection_points:
        for i in range(len(points) - 1):
            segments.append(
                [points[i][0], points[i][1], points[i + 1][0], points[i + 1][1]]
            )
    return segments

def angle_between_vectors(vector1, vector2):
    dot_product = vector1[0] * vector2[0] + vector1[1] * vector2[1]
    cross_product = vector1[0] * vector2[1] - vector1[1] * vector2[0]
    angle_radians = math.atan2(cross_product, dot_product)
    angle_degrees = math.degrees(angle_radians)
    if angle_degrees < 0:
        angle_degrees += 360
    return angle_degrees


def trace_boundary(lines):
    graph = dict()

    # 1. 建图
    for line in lines:
        x1, y1, x2, y2 = line
        p1, p2 = (x1, y1), (x2, y2)
        if p1 not in graph:
            graph[p1] = []
        if p2 not in graph:
            graph[p2] = []
        graph[p1].append(p2)
        graph[p2].append(p1)

    # 2. 删除悬挂点
    tmps = [p for p in graph if len(graph[p]) == 1]
    while len(tmps) > 0:
        for tmp in tmps:
            graph[graph[tmp][0]].remove(tmp)
            del graph[tmp]
        tmps = [p for p in graph if len(graph[p]) == 1]

    # 3. 最左下点
    points = sorted(list(graph.keys()))
    if len(points) == 0:
        return None
    start = points[0]

    # 4. 极角排序
    next = sorted(graph[start], key=lambda x: polar_angle(x, start))[0]
    result = [start, next]
    while next != start:
        next = sorted(
            graph[result[-1]],
            key=lambda x: -angle_between_vectors(
                np.array(x) - np.array(result[-1]),
                np.array(result[-2]) - np.array(result[-1]),
            ),
        )[0]
        result.append(next)
    return [
        [result[i][0], result[i][1], result[i + 1][0], result[i + 1][1]]
        for i in range(len(result) - 1)
    ]


def main():
    global width, height
    points = (np.random.rand(100, 2) * 500).astype(np.int32)
    width, height = np.max(points[:, 1]), np.max(points[:, 0])

    lines = points.reshape(-1, 4)
    show(lines, "1.png")

    # 1. 按照交点拆分直线段
    lines = intersect_and_split_segments(lines)
    show(lines, "2.png", True)

    # 2. 建图，最左下点，极角排序
    lines = trace_boundary(lines)
    show(lines, "3.png")


if __name__ == "__main__":
    main()