CODEWITHSUNDEEP
algorithmlanguage-agnosticgeometry
Jean-François Corbett
Jean-François Corbett

Reputation: 38530

Bounding ellipse constrained to horizontal/vertical axes

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.

Upvotes: 6

Views: 735

Answers (1)

Andrei
Andrei

Reputation: 56716

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.

Upvotes: 2

Related Questions