Ràng buộc hình elip bị ràng buộc theo trục ngang/dọc

Question

Bối cảnh: Tôi đang cố gắng cắt bản đồ địa hình vào hình elip có kích thước tối thiểu xung quanh một số tua-bin gió, để giảm thiểu kích thước của bản đồ. Chương trình thực hiện thao tác cắt bản đồ này có thể cắt trong hình elip, nhưng chỉ các hình elip có các trục thẳng hàng dọc theo trục x và y.

Tôi biết số algorithm for the bounding ellipse problem (tìm hình elip có diện tích nhỏ nhất bao quanh một tập hợp các điểm).

Nhưng làm cách nào để hạn chế thuật toán này (hoặc tạo một thuật toán khác) sao cho hình elip kết quả được yêu cầu để trục chính của nó được định hướng theo chiều ngang hoặc chiều dọc, tùy theo cái nào cho hình elip nhỏ nhất - và không bao giờ ở một góc?

Tất nhiên, hạn chế này làm cho hình elip kết quả lớn hơn nó "nhu cầu" được gửi kèm tất cả các điểm, nhưng đó là khó khăn không kém.

Answer 1

Các thuật toán được mô tả here (tham chiếu trong liên kết mà bạn cung cấp) là về giải quyết vấn đề tối ưu hóa sau đây:

minimize log(det(A)) 
s.t. (P_i - c)'*A*(P_i - c)<= 1 

Người ta có thể mở rộng hệ thống này của sự bất bình đẳng với các hạn chế sau đây (V là ma trận xoay hình elip, để biết chi tiết tham khảo liên kết ở trên):

V == [[1, 0], [0, 1]] // horizontal ellipse 

hoặc

V == [[0, -1], [1, 0]] // vertical ellipse 

Giải quyết vấn đề tối ưu hóa với một trong các ràng buộc này và tính bình phương của các elip kết quả sẽ cho bạn kết quả được yêu cầu.