从一组线中查找封闭（表面）区域

Question

我正在尝试自动 "fill" 我的代码中完全由行（段）包围的所有区域。

我有一个固定大小 (x,y) 的二维网格 space，以及一个由起点和终点定义的线列表。这些行不一定包含 space.

Visual Example .

我正在寻找的是区域的不同颜色的蓝色阴影（特别是它们的边界点，因为我正在尝试为这些区域创建网格）

我怎样才能通过算法找到这些区域？

Answer 1

有一种东西叫做Shoelace Theorem. If I understand you want the area in the shaded region. It determines the area of a simple polygon. Once you find the intersections giving you the points you can find the enclosed area. Alternatively, there are these convex hull algorithms. This is even more efficient.

    # Area of Polygon using Shoelace formula
# http://en.wikipedia.org/wiki/Shoelace_formula
# FB - 20120218
# corners must be ordered in clockwise or counter-clockwise direction
def PolygonArea(corners):
    n = len(corners) # of corners
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += corners[i][0] * corners[j][1]
        area -= corners[j][0] * corners[i][1]
    area = abs(area) / 2.0
    return area

# examples
corners = [(2.0, 1.0), (4.0, 5.0), (7.0, 8.0)]
print PolygonArea(corners)
corners = [(3.0, 4.0), (5.0, 11.0), (12.0, 8.0), (9.0, 5.0), (5.0, 6.0)]
print PolygonArea(corners)


let N           = number of points
let points[N+1] = the array of points
swap points[1] with the point with the lowest y-coordinate
sort points by polar angle with points[1]

# We want points[0] to be a sentinel point that will stop the loop.
let points[0] = points[N]

# M will denote the number of points on the convex hull.
let M = 1
for i = 2 to N:
    # Find next valid point on convex hull.
    while ccw(points[M-1], points[M], points[i]) <= 0:
        if M > 1:
            M -= 1
            continue
        # All points are collinear
        else if i == N:
            break
        else
            i += 1

    # Update M and swap points[i] to the correct place.
    # This code is wrong as explained in the talk page. When M and i are the same, the algorithm ends up in an infinite loop.
    M += 1
    swap points[M] with points[i]

Answer 2

诀窍是找到定义每个区域（多边形）的相交线段的完整回路。

假设线段以字母（A、B、C、...）命名。

我首先构建一个 table，让您可以按线段找到交叉点。

A -> B
A -> C
A -> D
B -> A
C -> A
C -> D
D -> A

（本例中ACD形成一个三角形区域，B只是一条与A相交的杂散线段。）

选择一条线段，比如A，检查它的第一个交点，恰好与线段B。现在我们开始扫描B的交点。 B回接A，完成一个回路，但只有两步，不是有效区域

因为B已经没有路口了，我们回头看A的下一个路口，就是和C的路口。C的第一个路口是和A的，绕了一圈，但是只有两步，所以不是有效区域.但是C的下一个交点是D，D的第一个交点是A，这样就完成了一个三步循环，所以现在我们有了有效区域，具体来说就是一个三角形。该区域由我们在电路中使用的交点定义：Pac、Pcd、Pda。

探索完 A 的所有可能路径后，您将从 B 重新开始。请注意，您会多次找到区域，因此您必须过滤掉重复项。但是你不能完全跳过检查 B，因为它可能是你还没有找到的另一个区域的边缘。

从一组线中查找封闭（表面）区域

Find enclosed (surface) area from set of lines

algorithm

surface

linear-algebra

line

area