Considering the image below, I want to compute the smallest triangle T enclosnging all the points in the set of vertices in a convex polygon. I have an iterative algorithm doing the job based on the assumption that the each edge of T is a superset to some edge of the convex polygon. That assumption turned out to be wrong. Two of the edges of T must be supersets to precisely two of the polygon's edges. However, apparently, it's possible that the third edge of T might be tangenting a vertex of the polygon, hence only intersecting a single vertex of it, instead of two. (The difference in large sets of points is insignificant and I've missed that. Shame on me!)
How can I find the correct tangent (that might turn out to be a superset to an edge of the polygon)?
In the image above, I can easily exclude
- c becuase neither cb' nor ca produces an enclosing triangle,
- d because de has the same slope as bb' and da' doesn't produce a triangle at all
- g because gb doesn't produce triangle at all and gf produces a triangle that isn't minimal
So we've got the candidates of e and f but the triangle produced by ef doesn't need to be the minimal one (that was my mistake to believe). The correct line that minimizes the triangle will pass through e or f (or both), though.
How can I compute that line?
I have suspicion that the correct line must be perpendicular to the mid-angular line that passes through the intersection of aa' and bb' (hence having the same angle to the former as to the latter). If I have that slope, I only need to offset it so that it passes through each of the candidates and compare the sizes of produces triangles.
Is that a correct approach or am I missing a flaw somewhere? I'm not making an ass of myself again.