Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!mcsun!ukc!edcastle!aipdc
From: aipdc@castle.ed.ac.uk (Paul D. Crowley)
Newsgroups: comp.graphics
Subject: Re: Minimum bounding region
Keywords: rectangles region bounding
Message-ID: <3799@castle.ed.ac.uk>
Date: 4 May 90 13:37:19 GMT
References: <1094@media01.UUCP>
Reply-To: aipdc@castle.ed.ac.uk (Paul D. Crowley)
Organization: Edinburgh University Computing Service
Lines: 11

A simple solution to this is described in "Algorithmics" by David Harel.
Basically you take the lowest point (which must be on the boundary) and
sort the rest according to angle w/ref to the lowest point.   Then... I
can't exactly describe it but if you draw a lot of points and draw a
line between every point and the lowest one and consider them in
clockwise order then it should be clear.

I think it takes O(n^2) time.
-- 
\/ o\ Paul Crowley aipdc@uk.ac.ed.castle                       :-| Have a day
/\__/ "The whole is the sum of its parts, plus one or more bugs" aimsm@castle