How to find the largest isosceles trapezium with a set center inscribed in a closed polygon?

Question

I need to find the largest (biggest area) isosceles trapezium inscribed inside a polygon, and the trapezium must have a set center.

The polygon is defined by an array of points in 2D. The polygon is closed and it can be convex or concave. By isosceles trapezium I mean this shape.

Which is a quadrilateral with two parallel sides and one line of symmetry.

Center can mean many things, for this problem the center is the following

That is, the point where perpendicular line at the middle of the base meets the perpedincular line at the middle of the height.

The center of the trapezium must match an arbitrary point of the polygon. So for instance, if the polygon is the following, and the arbitrary point is the black dot:

The inscribed trapezium should be something like this:

My sample trapezium is probably not the largest one but lets assume it is. The parallel lines must be horizontal, so the following example is not valid:

I tried reading the algorithms to find out the biggest rectangle inscribed in a polygon, and adapting them, but they don't seem to be very flexible.

Answer 1

This problem gets a lot easier if you:

1. Rotate it by 90 degrees; and
2. Fold it in half

So that this:

Becomes this:

Now, you're only concerned with the maximum height available at every x position, and you only have to find the top line of the best half-trapezoid that fits underneath that envelop:

The envelope is easy to calculate as a piecewise function just by finding the original line segment with the minimum height at every x position.

To find the top line of the best trapezoid, you can try every pair of segments between each pair of zero crossings, and find the best top line that connects those spans.