## Overlapping Squares

### Overlapping Squares

What ideas does anybody have for an algorithm for overlapping rectangles?

Lets look at the GUI of any operating system, there are many overlapping
windows. They should be drawn back to front in order so that the "top"
window actually appears on top, and the bottom window is less visable.

So what would be a good algoritm to figure out "how much of this window
should I draw".  So that duplication of areas never occures, and double
writes to screen pixels never happens.

The problem for me is, how do you cut a rectangle by another rectangle?

My next problem is, how do you cut a polygon by another polygon.

Are there any articles I should be looking at?

John McCarthy
--
John McCarthy - Author of that awesome Outer Ridge thing

### Overlapping Squares

Quote:McCarthy) writes:

>What ideas does anybody have for an algorithm for overlapping rectangles?

>Lets look at the GUI of any operating system, there are many overlapping
>windows. They should be drawn back to front in order so that the "top"
>window actually appears on top, and the bottom window is less visable.

It's actually usually much faster to draw from front to back. This means that
other views may have to be drawn piece-meal, but it removes all the redundant
screen redrawing.  The method I use is a recursive one that uses a tree
structure of "views" (windows) and keeps breaking down an area until the
rectangle just contains one view.  A clipping region is then set up and the
views told to go and draw itself. The view cannot draw outside the clipping
rectangle, so it doesn't overwrite views that are "on top" of it that have

This method is only really good for x-y aligned rectangular views like a GUI
window. It would get very complex for anything else, and it's pretty complex
even for axis-aligned rectangular views.

Quote:>So what would be a good algoritm to figure out "how much of this window
>should I draw".  So that duplication of areas never occures, and double
>writes to screen pixels never happens.

A recursive one that uses a rectangle intersection function.

Quote:>The problem for me is, how do you cut a rectangle by another rectangle?

>My next problem is, how do you cut a polygon by another polygon.

>Are there any articles I should be looking at?

Sorry about not being too specific, but it would take me a couple of hours to
explain all the ins and outs, even if I could remember them.

------------------------------------------------

------------------------------------------------

### Overlapping Squares

author =       "{James D.} Foley and Andries {van Dam} and {Steven
K.}\ Feiner and {John F.}\ Hughes",
title =        "{Computer Graphics: Principles and Practice}",
publisher =    "Addison-Wesley Publishing Company, Inc.",
year =         1996,
series =       "The Systems Programming Series",
note =        "Second edition in C"
Quote:}.

Kind regards -
Walter Hower
Institut f. Informatik, Fachbereich 4, Uni Koblenz-Landau
Rheinau 1, D-56075 Koblenz, Federal Republic of Germany
--

http://www.uni-koblenz.de/~walter/

Hi,

I want want to check if several given squares do not overlap. These squares
are given as xmin, xmax, ymin and ymax. The sqaures can be of different
size, but form an even larger square.

(view widt a unscalable font)
^   +-------------+-----+--------------+
|   |             |     |              |
Y   +---------+---+-----+----+---------+
|         |              |         |
+---------+              +---------+
|         |              |         |
+-----+---+------+-------+         |
|     |          |       |         |
+-----+----------+       |         |
|     |          |       |         |
+-----+----------+-------+---------+

X ->

Any suggestions what algorithm I could use?