mao@blia.BLI.COM (Mike Olson) (06/15/88)
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