Xref: utzoo comp.graphics:2661 comp.windows.misc:567
Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!decwrl!nsc!voder!blia!mao
From: mao@blia.BLI.COM (Mike Olson)
Newsgroups: comp.graphics,comp.windows.misc
Subject: looking for point location algorithm
Message-ID: <4831@blia.BLI.COM>
Date: 15 Jun 88 16:55:46 GMT
Organization: Britton Lee, Los Gatos, CA
Lines: 20

i'm looking for a spare, elegant, and blindingly fast algorithm to determine
which of many rectangles contains a given point.  if necessary, i'll
compromise on spare and elegant.

the problem, in brief:  i maintain a list of rectangles.  the user clicks
the mouse button somewhere.  i want to determine which rectangle, if any,
contained the pointer.  making each rect a window under X11 is cheating.
ordering of the list of rectangles is flexible; that is, the algorithm
should define it.

it would be best if the algorithm also handled z-ordering of windows
correctly -- that is, it should get the right answer when one rectangle
partially obscures another.

references to papers in the better-known trade publications are welcome;
you may also send a description of the algorithm yourself.  reply directly
to me, and i will summarize and post.

					mike olson
					britton lee, inc.
					...ucbvax!mtxinu!blia!mao