6

Context: I'm trying to clip a topographic map into the minimum-size ellipse around a number of wind turbines, to minimize the size of the map. The program doing this map clipping can clip in ellipses, but only ellipses with axes aligned along the x and y axes.

I know the algorithm for the bounding ellipse problem (finding the smallest-area ellipse that encloses a set of points).

But how do I constrain this algorithm (or make a different algorithm) such that the resulting ellipse is required to have its major axis oriented either horizontally or vertically, whichever gives the smallest ellipse -- and never at an angle?

enter image description here

Of course, this constraint makes the resulting ellipse larger than it "needs" to be to enclose all the points, but that's the constraint nonetheless.

Community
  • 1
  • 1
Jean-François Corbett
  • 37,420
  • 30
  • 139
  • 188
  • and what about making the algorithm more general: allowing more ellipses and looking for solution with highest information criterion (equivalent to smallest AIC value)? – Tomas Sep 22 '11 at 09:44

1 Answers1

2

The algorithm described here (referenced in the link you provided) is about solving the following optimization problem:

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

One can extend this system of inequalities with the following constraint (V is the ellipse rotation matrix, for detailed info refer the link above):

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

or

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

Solving the optimization problem with either of these constraints and calculating the square of the resulting ellipses will give you the required result.

Andrei
  • 55,890
  • 9
  • 87
  • 108