pkr@media01.UUCP (Peter Kriens) (05/04/90)
For some people this is probably a very simple problem, but I haven't found a very elegant solution yet. We need to have a path that describes the minimum region in which a set of n rectangles will fit. The path should be described with points which can followed to draw the outline of the region. The rectangles can, but do not always connect, and sometimes they even overlap. Does anyone have a nice clean elegant algorithm that handles this problem? Or a reference to a book? Thanks for your trouble Peter Kriens pkriens@media01 Mediasystemen Tel 31-23-319075 Waarderweg 18 PostBox 4932 2003 EX Haarlem
aipdc@castle.ed.ac.uk (Paul D. Crowley) (05/04/90)
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
welch@ral.rpi.edu (Henry Welch) (05/04/90)
In article <1094@media01.UUCP> pkr@media01.UUCP (Peter Kriens) writes: >We need to have a path that describes the minimum region >in which a set of n rectangles will fit. The path should >be described with points which can followed to draw the >outline of the region. The rectangles can, but do not always >connect, and sometimes they even overlap. I'm not sure of all your requirements with regard to the outline of the region, but here is a suggestion. Record all the vertices of your rectangles and generate the convex hull of the points. ====> Henry <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> Doctoral Candidate - Robotics and Automation Laboratory Center for Intelligent Robotics for Space Exploration Rensselaer Polytechnic Institute welch@ral.rpi.edu <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><> Life's a bitch and then you're reincarnated!