# [JAVA2D] Determining if a shape is a hole

Anonymous

I'm using a PathIterator to break up a shape into all of its
consitituent subshapes--where each SET_MOVETO begins a new shape. This
part works fine.

Now I'd like to determine, for each subshape, whether the subshape was
a hole in the original shape.

As a proof of concept, I wrote some code that recursively looks for any
point in the subshape (subshape.contains(x, y)) which is also contained
in the original shape. If none can be found, the shape is a hole. This
gives accurate results, but is very slow when checking holes, because it
ends up checking every point in the subshape down to some granularity.

>From experience I know that in GlyphVectors the "outer" shapes are
always drawn clockwise, and the holes counter-clockwise (a requirement
of the underlying font formats), but obviously this is not true of
shapes in general.

I imagine that to some degree I will have to duplicate the
WIND_EVEN_ODD/WIND_NON_ZERO algorithms, in which case I'd appreciate a
pointer to some Java code, if there is any.

FWIW I need this information to do backface culling when extruding the
shape to a 3d volume.

Thanks,
Chris

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

Kirill Grouchnikov

The simplest way is to "draw" a random ray from some point inside the candidate hole and count the number of intersections with all the shapes. If it's odd, you're in the shape, if it's even, you're in the hole.

Note that here you can have shapes inside holes (the above returns correct results). However, the only catch here is when your ray intersects some vertex of some contour. In this case you'll have to use another random ray, since that vertex can have arbitrary cardinality.

Kirill

Chris Nokleberg wrote: I'm using a PathIterator to break up a shape into all of its
consitituent subshapes--where each SET_MOVETO begins a new shape. This
part works fine.

Now I'd like to determine, for each subshape, whether the subshape was
a hole in the original shape.

As a proof of concept, I wrote some code that recursively looks for any
point in the subshape (subshape.contains(x, y)) which is also contained
in the original shape. If none can be found, the shape is a hole. This
gives accurate results, but is very slow when checking holes, because it
ends up checking every point in the subshape down to some granularity.

>From experience I know that in GlyphVectors the "outer" shapes are
always drawn clockwise, and the holes counter-clockwise (a requirement
of the underlying font formats), but obviously this is not true of
shapes in general.

I imagine that to some degree I will have to duplicate the
WIND_EVEN_ODD/WIND_NON_ZERO algorithms, in which case I'd appreciate a
pointer to some Java code, if there is any.

FWIW I need this information to do backface culling when extruding the
shape to a 3d volume.

Thanks,
Chris

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

---------------------------------
Yahoo! Shopping
Find Great Deals on Holiday Gifts at Yahoo! Shopping

===========================================================================
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".
[att1.html]