Longest straight line in a convex polygon with fixed slope and constrained endpoints

Question

Consider two convex polygons A and B. Polygon B lies completely inside polygon A. I am trying to find the longest line segment (with a fixed slope) such that:

• One end of the line segment lies on the boundary of polygon B, and the other end of the line segment lies on the boundary of polygon A.

Can anyone help me with an algorithm to find that length?

Further, can this be extended to the following:

• Suppose you have two line segments with different slopes (both fixed slopes), such that they have the same endpoint on or inside polygon B and their other endpoints (would be different for the two lines) on the boundary of A. How would I maximize the sum of their lengths?
• Polytopes/ polygons of higher dimensions?

Answer 1

Rotate the polygons so that the slope is horizontal (in practice, do this implicitly with vector math). The desired segment has an endpoint at a vertex of A or at a vertex of B (otherwise we could lengthen the segment by perturbing its position up or down).

Obtain the left hull of A and the right hull of B. We simulate a line sweeping bottom to top by doing a sorted merge of the vertices of A with the vertices of B. At each vertex, determine the length horizontally, which will be determined by the equation for the segment connecting the previous vertex on that hull with the next.

Answer 2

First, you need to realize that the connecting line segment will never end in the middle of both A's and B's edges.

If it did, and A's and B's edges are not parallel, then moving one way or the other would always result in a longer connecting line segment. If A's and B's edges are parallel, you can move both ways to find equal-length connecting line segments, until you reach a vertex, so there will always be a max-length solution that ends in a vertex.

This reduces the list of potential connecting line segments to line segments that end at a vertex.

So, for every vertex of A, find the (up to) two points on a line of the given slope that crosses B, and choose the point furthest away (if any). That is a candidate line segment.

Do the same for every vertex of B, locating point where line crosses A.

Now select the longest line segment from all those candidates.

Note that the above will work for concave polygons too. There will just be more than two points where a line from the vertex of one polygon crosses an edge of the other polygon.