Skip to main content

Efficient Z-Order Calculation

2 replies [Last post]
Anonymous

This isn't specifically a Java2D question, though the context is a
Java2D-based application. Hopefully I'm not too far out of line.

I have an application which displays a large number (~10-1000) of opaque
2D shapes. The user can add, delete, and move the shapes with the
mouse. Operations can be performed on single shapes or on user-selected
sets of them.

The problem involves generating the z-ordering of the shapes. If shape
A is inside shape B, and I draw shape A first, then shape B will
completely hide it. I need an efficient algorithm and data structure to
maintain an ordering on the shapes so that, at worst, a shape is only
partially obscured by another. Generating the data structure should be
relatively fast, and once it is generated, add, delete, and move
operations should be fast.

The approach that comes to mind is some sort of tree structure based on
a nesting hierarchy of the bounding boxes of the shapes. I've done a
little research. Would some variation on R-trees be appropriate? This
seems like a problem others would have encountered, but I can't seem to
find anything that specifically addresses this issue. Any help would be
greatly appreciated. Thanks!

-David

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
Seth Tager

I'm confused. How do you know A is inside B? You should be able to use
that information to draw B first, and then draw all of the objects
that are inside B, which should result in the z-ordering that you're
after.

Have you looked at the Composite pattern from the Design Patterns
book? That should point you in the right direction.

On 4/28/06, David Eisner wrote:
> This isn't specifically a Java2D question, though the context is a
> Java2D-based application. Hopefully I'm not too far out of line.
>
> I have an application which displays a large number (~10-1000) of opaque
> 2D shapes. The user can add, delete, and move the shapes with the
> mouse. Operations can be performed on single shapes or on user-selected
> sets of them.
>
> The problem involves generating the z-ordering of the shapes. If shape
> A is inside shape B, and I draw shape A first, then shape B will
> completely hide it. I need an efficient algorithm and data structure to
> maintain an ordering on the shapes so that, at worst, a shape is only
> partially obscured by another. Generating the data structure should be
> relatively fast, and once it is generated, add, delete, and move
> operations should be fast.
>
> The approach that comes to mind is some sort of tree structure based on
> a nesting hierarchy of the bounding boxes of the shapes. I've done a
> little research. Would some variation on R-trees be appropriate? This
> seems like a problem others would have encountered, but I can't seem to
> find anything that specifically addresses this issue. Any help would be
> greatly appreciated. Thanks!
>
> -David
>
> ===========================================================================
> To unsubscribe, send email to listserv@java.sun.com and include in the body
> of the message "signoff JAVA2D-INTEREST". For general help, send email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".

David Eisner

Seth Tager wrote:
> I'm confused. How do you know A is inside B?
By "inside," I mean that the set of points of A are a subset of the set
of points of B.

> You should be able to use that information to draw B first, and then
> draw all of the objects
> that are inside B, which should result in the z-ordering that you're
> after.

Yes. I want to do this efficiently. To make the problem less abstract,
imagine I'm trying to solve the following problem:

You are given a file defining a set of 10,000 rectangles. Each
rectangle is defined on a single line of the file. Rectangle i is
defined by:

x1i y1i x2i y2i

where (x1i, y1i) is the lower-left corner of the rectangle and (x2i,
y2i) is the upper-right corner. Your task is to draw and fill each
rectangle, with the following requirement: When you are done, no
rectangle may be totally hidden by another rectangle.

It is easy to see if (x1,y1,x2,y2) is inside (X1,Y1,X2,Y2) (or you could
just use the Rectangle contains() method). So one approach would be to
create a sorted list of rectangles based on the partial ordering defined
by the "contains" relation. Thus, if rectangle A contains rectangle B,
then we say B < A. However, it seems like there might be a more
efficient way to do this.

-David

>
> Have you looked at the Composite pattern from the Design Patterns
> book? That should point you in the right direction.
>
> On 4/28/06, David Eisner wrote:
>> This isn't specifically a Java2D question, though the context is a
>> Java2D-based application. Hopefully I'm not too far out of line.
>>
>> I have an application which displays a large number (~10-1000) of opaque
>> 2D shapes. The user can add, delete, and move the shapes with the
>> mouse. Operations can be performed on single shapes or on user-selected
>> sets of them.
>>
>> The problem involves generating the z-ordering of the shapes. If shape
>> A is inside shape B, and I draw shape A first, then shape B will
>> completely hide it. I need an efficient algorithm and data structure to
>> maintain an ordering on the shapes so that, at worst, a shape is only
>> partially obscured by another. Generating the data structure should be
>> relatively fast, and once it is generated, add, delete, and move
>> operations should be fast.
>>
>> The approach that comes to mind is some sort of tree structure based on
>> a nesting hierarchy of the bounding boxes of the shapes. I've done a
>> little research. Would some variation on R-trees be appropriate? This
>> seems like a problem others would have encountered, but I can't seem to
>> find anything that specifically addresses this issue. Any help would be
>> greatly appreciated. Thanks!
>>
>> -David
>>
>> ===========================================================================
>>
>> To unsubscribe, send email to listserv@java.sun.com and include in
>> the body
>> of the message "signoff JAVA2D-INTEREST". For general help, send
>> email to
>> listserv@java.sun.com and include in the body of the message "help".
>>
>
> =====================================================3D=====================
>
> To unsubscribe, send email to listserv@java.sun.com and include in the
> body
> of the message "signoff JAVA2D-INTEREST". For general help, send
> email to
> listserv@java.sun.com and include in the body of the message "help".
>

===========================================================================
To unsubscribe, send email to listserv@java.sun.com and include in the body
of the message "signoff JAVA2D-INTEREST". For general help, send email to
listserv@java.sun.com and include in the body of the message "help".