สมมติว่าเรามีรายการของจุดที่เรียงลำดับแทนจุดสิ้นสุดรูปหลายเหลี่ยมอย่างง่ายบนระนาบ 2 มิติ เราต้องหาพื้นที่ของรูปหลายเหลี่ยมนี้
ดังนั้น หากอินพุตเหมือนกับคะแนน =[(0, 0), (0,5), (3, 5), (3,0)] ผลลัพธ์จะเป็น 15
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน getInfo() นี่จะใช้เวลา x1, y1, x2, y2
- ผลตอบแทน x1*y2 - y1*x2
- จากวิธีหลัก ให้ทำดังนี้
- N :=ขนาดของจุด
- (firstx, firsty) :=คะแนน[0]
- (prevx, prevy) :=(firstx, firsty)
- res :=0
- สำหรับผมอยู่ในช่วง 1 ถึง N-1 ทำ
- (nextx, nexty) :=คะแนน[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
