Giả sử chúng ta có các điểm bên ngoài của một đa giác theo thứ tự theo chiều kim đồng hồ. Chúng ta phải kiểm tra các điểm này có tạo thành một bao lồi hay không.
Từ sơ đồ này rõ ràng rằng với mỗi ba điểm liên tiếp, góc nội tại không quá 180°. Vì vậy nếu tất cả các góc không quá 180° thì đa giác là bao lồi.
Vì vậy, nếu đầu vào là points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)], thì đầu ra sẽ là True.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:
- n := kích thước points
- với i từ 0 đến kích thước points, thực hiện
- p1 := points[i-2] khi i > 1, ngược lại points[n-2]
- p2 := points[i-1] khi i > 0, ngược lại points[n-1]
- p3 := points[i]
- nếu góc giữa các điểm (p1, p2, p3) > 180, thì trả về False
- trả về True
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
import math
def get_angle(a, b, c):
angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
return angle + 360 if angle < 0 else angle
def solve(points):
n = len(points)
for i in range(len(points)):
p1 = points[i-2]
p2 = points[i-1]
p3 = points[i]
if get_angle(p1, p2, p3) > 180:
return False
return True
points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]
print(solve(points))
Đầu vào
[(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]
Đầu ra
True