Help with sorting rectangles

Article View: cmu.cs.general

Article #1

From: Brad Myers
Date: Fri, 31 Jul 1992 18:43

23 lines
1144 bytes

Does anyone know an algorithm for sorting rectangles in row-major order?
The problem is that they might not be exactly aligned.  For example:

         |-----|
  |----| |  B  | |-----|
  | A  | |     | |  C  |
  |____| |-----| |_____|
        
|-----|         |-----|
| D   ||-----|  |  F  |
|-----||  E  |  |     |
       |_____|  |-----|


I want to get the order ABCDEF which is "clearly obvious", but notice
that D has an X value that is less than A, and B has a Y value that is
less than A (assuming 0,0 at the top), so simply sorting by X and then
Y (or vice versa) fails.  Surely, someone has solved this problem already!

Thanks for your help!
Brad Myers
bam@cs.cmu.edu

Technical Details

Message-ID: <1992Jul31.184332.125762@cs.cmu.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!rutgers!rochester!cantaloupe.srv.cs.cmu.edu!bam

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!sparky!uunet!stanford.edu!rutgers!rochester!cantaloupe.srv.cs.cmu.edu!bam
From: bam+@BAM.GARNET.CS.CMU.EDU (Brad Myers)
Newsgroups: cmu.cs.general,comp.graphics
Subject: Help with sorting rectangles
Message-ID: <1992Jul31.184332.125762@cs.cmu.edu>
Date: 31 Jul 92 18:43:32 GMT
Organization: School of Computer Science, Carnegie Mellon
Lines: 23
Nntp-Posting-Host: bam.garnet.cs.cmu.edu
Originator: bam@BAM.GARNET.CS.CMU.EDU