Ограничивающий эллипс, ограниченный горизонтальной / вертикальной осями

Question

Контекст: я пытаюсь обрезать топографическую карту в эллипс минимального размера вокруг нескольких ветряных турбин, чтобы минимизировать размер карты. Программа, выполняющая это отсечение карты, может обрезать эллипсы, но только эллипсы с осями, выровненными вдоль осей x и y.

Мне известен алгоритм для задачи ограничивающего эллипса (поиск эллипса наименьшей площади, который включает в себя множество точек).

Но как мне ограничить этот алгоритм (или создать другой алгоритм) так, чтобы в конечном эллипсе требовалось, чтобы его главная ось была ориентирована горизонтально или вертикально, в зависимости от того, что дает наименьший эллипс - и никогда не под углом?

Конечно, это ограничение делает результирующий эллипс больше, чем ему «нужно», чтобы охватить все точки, но, тем не менее, это ограничение.

Answer 1

Алгоритм, описанный здесь (на который есть ссылка, указанная вами), предназначен для решения следующей задачи оптимизации:

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

Эту систему неравенств можно расширить следующим ограничением (V - матрица вращения эллипса, подробную информацию см. По ссылке выше):

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

или

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

Решение задачи оптимизации с помощью любого из этих ограничений и вычисление квадрата получаемых эллипсов даст требуемый результат.