# Efficient Z-Order Calculation

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".

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

>> 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".

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".