38370

神经网络昆斯林的新闻组分类2006

Newsgroups: comp.graphics
Path: cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!gatech!darwin.sura.net!haven.umd.edu!uunet!news.smith.edu!orourke
From: [e-mail] (Joseph O'Rourke)
Subject: Re: Need a good concave -> convex polygon algorithm
Message-ID: <[e-mail]>
Organization: Smith College, Northampton, MA, US
References: <[e-mail]>
Date: Sat, 17 Apr 1993 00:51:43 GMT
Lines: 16

In article <[e-mail]> [e-mail] (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
>[e-mail]

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.