Minimal Enclosing Triangle
gle...@pixelglow.com
Does anybody have a good C/C++/Java implementation of finding the
minimal enclosing triangle for a (convex) polygon in O(n) time?
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). 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].
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! (You can also email me at glen dot low
at pixelglow dot com).
Cheers,
Glen Low
Pixelglow Software
Dave Eberly
news:garnll$5g8$1...@dizzy.math.ohio-state.edu...
> Does anybody have a good C/C++/Java implementation of finding the
> minimal enclosing triangle for a (convex) polygon in O(n) time?
How large is your 'n'? As with many 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.
> 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