CODEWITHSUNDEEP
algorithmlinelinear-algebraareasurface
Frank v Hoof
Frank v Hoof

Reputation: 57

Find enclosed (surface) area from set of lines

I am trying to automatically "fill" all of the areas in my code that are completely enclosed by line(segment)s.

What I have is a grid of fixed size (x,y) in 2D space, and a list of lines, defined by their start- and end-points. These lines do not necessarily enclose a space.

Visual Example .

What I am looking for is the area's shaded in the different colors of blue here (specifically their bounding points, as I'm trying to create meshes for these areas)

How could I go about algorithmically finding these areas?

Upvotes: 2

Views: 1807

Answers (2)

user1911226
user1911226

Reputation:

There is something called the 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]

Upvotes: 0

Adrian McCarthy
Adrian McCarthy

Reputation: 47956

The trick is to find complete circuits of intersecting line segments that define each area (polygon).

Let's assume the line segments are named with letters (A, B, C, ...).

I'd start by building a table that lets you find intersections by line segment.

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

(In this example, ACD forms a triangular area, and B is just a stray line segment that happens to cross A.)

Pick a line segment, say A, and check its first intersection, which happens to be with line segment B. Now we start scanning B's intersections. B connects back to A, which completes a circuit, but there were only two steps, so it's not a valid area.

Since B has no more intersections, we backtrack and look at A's next intersection, which is with C. C's first intersection is with A, which completes a circuit, but it's only two steps, so it's not a valid area. But C's next intersection is D, and D's first intersection is A, which completes a three-step circuit, so now we have valid area, specifically a triangle. The area is defined by the points of intersections we used in our circuit: Pac, Pcd, Pda.

Once you've explored all the possible paths from A, you'd start again with B. Note that you'll find areas multiple times, so you have to filter out the duplicates. But you can't skip checking B altogether, because it might be an edge of another area that you haven't already found.

Upvotes: 1

Related Questions