Minimal enclosing Triangle

[g***@pixelglow.com]

Does anybody have a good C/C++/Java implementation of a minimal
enclosing triangle for a (convex) polygon in O(n) time?

I tried implementing the one in "An Optimal Algorithm for Finding
Minimal Enclosing Triangles" (O'Rourke, Aggarwal, Maddila, Baldwin) in
Journal of Algorithms 7 (1986). After grinding my rusty mathematical
mental gears for a couple of days, I finally figured out enough to
start on an implementation only to get stuck at this point:

On page 265, the pseudocode goes

1. If [gamma(b), b] intersects P above b or height(b) < height(a-1)
2. then set side flush with [b-1, b] and
3. if midpoint of B < height(a-1)
4. then set side A to have midpoint a-1
5. else side B is determined by [gamma(b), b]

If line 1 is false, then line 5 is executed. At this stage, the
triangle is uniquely determined by the lines [c-1, c], [a-1, a] and
[gamma(b), b]. So far so good

If line 2 is true, then lines 2-4 are executed. At this stage, only
two sides of the triangle is determined i.e. [c-1, c], [b-1, b].

Qn:

A. If line 3 is false, how do we determine the third side?
B. If line 3 is true i.e. line 4 is executed, how do you arrange side
A to have midpoint a-1?

Notation:
[x, y] is the infinite line that contains points x and y
height(p) is the height of point p from [c-1, c]
gamma(p) is the point on [a-1, a] with height(gamma(p)) = 2 *
height(p)

Thanks for the help in advance!

Cheers,
Glen Low
Pixelglow Software
P.S. You can also reach me at glen dot low at pixelglow dot com.

[Dave Eberly]

----- Original Message -----
From: <***@pixelglow.com>
Newsgroups: comp.graphics.algorithms
Sent: Wednesday, September 17, 2008 6:18 AM
Subject: Minimal enclosing Triangle

Post by g***@pixelglow.com
Does anybody have a good C/C++/Java implementation of a minimal
enclosing triangle for a (convex) polygon in O(n) time?

How large is your 'n'? As with some computational geometry
algorithms:
(1) The asymptotic behavior might not be noticeable until n
is much larger than what your application uses.
(2) The effort to implement the algorithm is not worth the time
when a simpler (but asymptotically slower) algorithm is
easy to code.

Post by g***@pixelglow.com
I tried implementing the algorithm in "An Optimal Algorithm for
Finding Minimal Enclosing Triangles" (O'Rourke, Aggarwal, Maddila,
Baldwin) in Journal of Algorithms 7 (1986).

<snip>

I have browsed this paper but it appears that a careful reading is
essential to understand the pseudocode.

Using the fact that one side of the triangle must be flush with
a polygon edge, you can set up the construction of the other
two sides by formulating the area in terms of two parameters.
A standard calculus approach to computing the minimum may
be applied, leading to a relatively simple solution. This approach
is applied to all n edges of the polygon, and then you select the
smallest-area triangle. Maybe not elegant as in the paper, but
practical to implement.

--
Dave Eberly
http://www.geometrictools.com

[g***@pixelglow.com]

How large is your 'n'?  As with some computational geometry
(1) The asymptotic behavior might not be noticeable until n
      is much larger than what your application uses.
(2) The effort to implement the algorithm is not worth the time
      when a simpler (but asymptotically slower) algorithm is
      easy to code.

I'm pretty sure the algorithm I mentioned is only a couple of factors
of n. I need pretty much real time performance, and the minimal
enclosing triangle algorithm isn't the only one being run.

Post by g***@pixelglow.com
I tried implementing the algorithm in "An Optimal Algorithm for
Finding Minimal Enclosing Triangles" (O'Rourke, Aggarwal, Maddila,
Baldwin) in Journal of Algorithms 7 (1986).

<snip>
I have browsed this paper but it appears that a careful reading is
essential to understand the pseudocode.

I managed to code it up in C++ and it seems to be OK with the polygons
I threw at it. For future reference and further comment, here's how I
interpreted the pseudocode in the OP.

If line 1 is true:

2.
side B is determined by [b-1, b]
vertex A is determined by side B and side C

3.
try side A using [a-1, a]
try vertex C from side A and side B
try midpoint of B from vertex A and vertex C
test if height(midpoint) < height(a-1)

4.
if not, vertex C is twice the height of a-1, but on side B
(essentially a mirror of the gamma(p) function, substituting side B
for side A for symmetry)

if line 1 is false:

5.
side B is determined by [gamma(b), b]
side A is determined by [gamma(b), a] (or [gamma(b), a-1], since
gamma(b) is on the line [a, a-1])
vertex C = gamma(b)
vertex A is determined by side B and side C
vertex B is determined by side A and side C

Cheers, G.

[OvidiuParvu]

A potentially relevant answer to your question was provided here: http://stackoverflow.com/a/27921736/1150554.