re need a good concave convex polygon algorithm in article c juyz aly murdoch acc virginia edu rws v uvacs cs virginia edu richard stoakley writes we need a good concave convex polygon conversion routine i ve tried a couple without much luck please e mail responses and i will post a summary of any replies thank you richard stoakley rws v uvacs cs virginia edu the problem is not precisely defined above but if you need to find the smallest convex polygon that encloses a given polygon then you are seeking the convex hull of your original polygon there are two ways to do this use a somewhat tricky but by now well examined linear time algorithm that exploits the polygon boundary or just feed the vertices of the original polygon to a convex hull routine and accept o n log n both methods are discussed in preparata and shamos for example
