ค้นหาพื้นที่ปิดล้อม (พื้นผิว) จากชุดของเส้น

เคล็ดลับคือการหาวงจรที่สมบูรณ์ของส่วนของเส้นที่ตัดกันซึ่งกำหนดแต่ละพื้นที่ (รูปหลายเหลี่ยม)

สมมติว่าส่วนของเส้นตรงตั้งชื่อด้วยตัวอักษร (A, B, C, ...)

ฉันจะเริ่มต้นด้วยการสร้างตารางที่ให้คุณค้นหาทางแยกตามส่วนของเส้นตรง

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 ไปได้เลย เพราะอาจเป็นขอบของพื้นที่อื่นที่คุณยังไม่พบ

มีบางสิ่งที่เรียกว่า ทฤษฎีเชือกผูกรองเท้า ถ้าฉันเข้าใจว่าคุณต้องการพื้นที่ใน ภูมิภาคที่แรเงา จะกำหนดพื้นที่ของ รูปหลายเหลี่ยม เมื่อคุณพบทางแยกที่ให้จุดต่างๆ แล้ว คุณจะพบจุดปิดล้อม พื้นที่. อีกทางหนึ่ง มี อัลกอริธึมตัวถังแบบนูน เหล่านี้ยิ่งกว่า มีประสิทธิภาพ

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