Need Algorithm for n-convex bounding polygon
Hein Veenhof
of a concave polygon.
This convex hull must have exactly n vertices.
A polygon can always be approximated by a triangle, so there is
a lower bound 3 for n. I assume there is also an upper bound for
n. Other approximations are e.g. 4-corner, 5-corner etc..
Who is familiar with algorithms for generating convex hulls ?
Is it possible to have these algorithms generate a convex hull with
exactly n vertices ?
Who knows of a reference to such an algorithm ?
Please reply soon.
===============================================================================
Ir. Hein M. Veenhof email: vee...@cs.utwente.nl
University of Twente phone: ++31 (0)53 893763
Dept. of Computer Science fax : ++31 (0)53 339605
mail : P.O. Box 217
7500 AE Enschede
The Netherlands
===============================================================================
Who? Me? Do you really mean me?
& I'am looking for an algorithm that will generate a n-convex hull
& of a concave polygon.
& This convex hull must have exactly n vertices.
& A polygon can always be approximated by a triangle, so there is
& a lower bound 3 for n. I assume there is also an upper bound for
& n. Other approximations are e.g. 4-corner, 5-corner etc..
& Who is familiar with algorithms for generating convex hulls ?
& Is it possible to have these algorithms generate a convex hull with
& exactly n vertices ?
& Who knows of a reference to such an algorithm ?
& Please reply soon.
& ===============================================================================
& Ir. Hein M. Veenhof email: vee...@cs.utwente.nl
& University of Twente phone: ++31 (0)53 893763
& Dept. of Computer Science fax : ++31 (0)53 339605
& mail : P.O. Box 217
& 7500 AE Enschede
& The Netherlands
& ===============================================================================
If you take a polygon whose normal convex hull has exactly 3 vertices, you
cannot find a smallest convex quadrilateral enclosing the polygon.
3 of your 4 vertices will be vertices of the convex hull, and whereever you
pick the fourth vertex of the quadrilateral, there will be another point
closer to the original convex hull. ( I assume degenerated cases where the
convex quadrilateral has 3 colinear points are forbidden.)
Haijo.
Joseph O'Rourke
>I'am looking for an algorithm that will generate a n-convex hull
>of a concave polygon.
>This convex hull must have exactly n vertices.
What is an "n-convex hull"? For standard convex hulls, you
might start with Preparata and Shamos:
@book{Preparata.Shamos
, author = "F. P. Preparata and M. I. Shamos"
, title = "Computational Geometry: an Introduction"
, publisher = "Springer-Verlag"
, address = "New York, NY"
, year = "1985"
, keywords = "book"
, label = "PS-CGI-SV-85"
, note = "Corrected and expanded second printing, 1988."
}