สมมติว่าเรามีรายการจุดที่เรียงลำดับแล้ว แทนจุดปลายของรูปหลายเหลี่ยมแบบง่าย (Simple Polygon) บนระนาบ 2 มิติ เราต้องหาพื้นที่ของรูปหลายเหลี่ยมนั้น
ตัวอย่างเช่น หาก points = [(0, 0), (0,5), (3, 5), (3,0)] ผลลัพธ์จะเป็น 15.0
ขั้นตอนการแก้ปัญหา (ใช้สูตร Shoelace Formula)
- กำหนดฟังก์ชัน getInfo(x1, y1, x2, y2): คืนค่า x1*y2 - y1*x2
- จากฟังก์ชันหลัก:
- N := จำนวนจุด
- (firstx, firsty) := points[0]
- (prevx, prevy) := (firstx, firsty)
- res := 0
- for i ในช่วง 1 ถึง N-1:
- (nextx, nexty) := points[i]
- res := res + getInfo(prevx, prevy, nextx, nexty)
- prevx := nextx, prevy := nexty
- res := res + getInfo(prevx, prevy, firstx, firsty)
- คืนค่า |res| / 2.0
ตัวอย่างโค้ด
def getInfo(x1, y1, x2, y2):
return x1*y2 - y1*x2
def solve(points):
N = len(points)
firstx, firsty = points[0]
prevx, prevy = firstx, firsty
res = 0
for i in range(1, N):
nextx, nexty = points[i]
res = res + getInfo(prevx, prevy, nextx, nexty)
prevx = nextx
prevy = nexty
res = res + getInfo(prevx, prevy, firstx, firsty)
return abs(res)/2.0
points = [(0, 0), (0,5), (3, 5), (3,0)]
print(solve(points))
อินพุต
[(0, 0), (0,5), (3, 5), (3,0)]
เอาต์พุต
15.0
