Temukan luas (permukaan) tertutup dari kumpulan garis

Caranya adalah dengan mencari rangkaian lengkap segmen garis berpotongan yang mendefinisikan setiap luas (poligon).

Misalkan ruas garis diberi nama dengan huruf (A, B, C, ...).

Saya akan mulai dengan membuat tabel yang memungkinkan Anda menemukan perpotongan berdasarkan segmen garis.

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

(Dalam contoh ini, ACD membentuk luas segitiga, dan B hanyalah ruas garis nyasar yang kebetulan memotong A.)

Pilih ruas garis, katakanlah A, dan periksa perpotongan pertamanya, yang kebetulan berada dengan ruas garis B. Sekarang kita mulai memindai perpotongan B. B terhubung kembali ke A, yang menyelesaikan suatu rangkaian, tetapi hanya ada dua langkah, jadi ini bukan area valid.

Karena B sudah tidak mempunyai persimpangan lagi, kita mundur dan melihat persimpangan A berikutnya, yaitu dengan C. Perpotongan pertama C adalah dengan A, yang menyelesaikan suatu rangkaian, tetapi hanya dua langkah, jadi itu bukan daerah yang valid. Namun perpotongan C berikutnya adalah D, dan perpotongan pertama D adalah A, yang menyelesaikan rangkaian tiga langkah, jadi sekarang kita mempunyai luas valid, khususnya segitiga. Luas ditentukan oleh titik perpotongan yang kita gunakan di sirkuit kita: Pac, Pcd, Pda.

Setelah Anda menjelajahi semua kemungkinan jalur dari A, Anda akan mulai lagi dengan B. Perhatikan bahwa Anda akan menemukan area beberapa kali, jadi Anda harus memfilter duplikatnya. Tapi Anda tidak bisa melewatkan pemeriksaan B sama sekali, karena mungkin itu adalah sisi dari area lain yang belum Anda temukan.

Ada sesuatu yang disebut Teorema Tali Sepatu. Jika saya mengerti Anda ingin area tersebut masuk wilayah yang diarsir. Ini menentukan luas poligon. Setelah Anda menemukan persimpangan yang memberi Anda titik, Anda dapat menemukan titik terlampir daerah. Alternatifnya, ada algoritme convex lambung ini. Ini bahkan lebih efisien.

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