[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

797.0. "Windowing Algorithms ?" by ZUR01::KRAUS (Buying Land in Costa-Rica ? ) Thu Dec 03 1987 08:19

Following Problem: 
__________________

Given n rectangles r(i), an ordering function i->N : o(i) which indicates
the order of visibility : ie of 2 rectangles that cover the same space the 
one j is visible with o(j) > o(i). How do you calculate the visibility
region for each rectangle, which consists of a rectangle shaped partitions
of that rectangle? = Part(k,i). so that r(i)=Sum Part(k,i) , sum over k?

T.R Title User Personal
Name Date Lines

797.1 much prior art exists on this MATRIX::ROTH May you live in interesting times Fri Dec 04 1987 08:36 18

T.R	Title	User	Personal Name	Date	Lines
797.1	much prior art exists on this	MATRIX::ROTH	May you live in interesting times	`Fri Dec 04 1987 08:36`	18
	If there are not that many, a naive polygon clipping algorithm specialized for rectangles would work fine... you could make a front to back pass, outputing visible fragments of each rectangle as clipped by polygons which have already been output. For many better ideas for the general case much work has been done because of its importance for VLSI design rule checkers. An overall reference is the book 'Introduction to Computational Geometry" by Preparata and Shamos. In particular, there are multidimensional binary search trees and other data structures which make such clipping and interference detection very fast compared to simple-minded approaches. For your rectangle case, an algorithm that sweeps from top to bottom, stopping whenever a new horizontal edge is encountered, and maintains active rectangle lists would do the trick. - Jim

    If there are not that many, a naive polygon clipping algorithm
    specialized for rectangles would work fine...  you could make a
    front to back pass, outputing visible fragments of each rectangle
    as clipped by polygons which have already been output.

    For many better ideas for the general case much work has been done
    because of its importance for VLSI design rule checkers.  An overall
    reference is the book 'Introduction to Computational Geometry" by
    Preparata and Shamos.

    In particular, there are multidimensional binary search trees
    and other data structures which make such clipping and interference
    detection very fast compared to simple-minded approaches.  For your
    rectangle case, an algorithm that sweeps from top to bottom, stopping
    whenever a new horizontal edge is encountered, and maintains active
    rectangle lists would do the trick.

    - Jim