This is the mail archive of the mauve-patches@sources.redhat.com mailing list for the Mauve project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Area.java


> There is a definition of which points lie "inside" a shape in the
> description of the Shape interface:
> 
> http://java.sun.com/j2se/1.4.2/docs/api/java/awt/Shape.html

Ah,yes, you are so right. I forgot about that. It's a (IMHO) bad
definition though, good example of Sun turning implementation 
into specification. 

> It more or less says that points on the left/top edges are "in" and
> points on the right/bottom edges are "out".  Now *somewhere* I read a
> justification for this 

It's due to the aforementioned line-crossing algorithm. 
Basically it says for a point (X,Y): Test intersections with the line
x>X, y=Y. Unless the point is on a horizontal line segment, in which
case you test the line x=X, y>Y. 

The horizontal-segment special case is something I'll have to add.

> I haven't spotted any inconsistencies based on the above definitions,
> but I'll review them again.  If you have some cases where Sun's
> implementation is wrong, it would be great to get some checks included
> for them.

Sure.. some bugs:
http://www.qc.physto.se/~sven/ContainsBug/

The ContainsBug program shows off the pitfall I mentioned before
with line-crossing (note the line y=151 to the left of the arc)
with CubicCurve2D.contains(). The ArcBug program shows off how
Arc2D.contains() doesn't work at all for Chorded-type arcs.
(One case where it doesn't return any points at all as inside, 
and one where it returns the same result as for a Pie-type arc)

This is also with Java 1.4 on Linux. (RH 9) IIRC, Sun's site indicated
it had been fixed, so I'm not so certain about 1.5.
(Gloating: A screenshot is there with gcj/classpath running natively
on the left, JDK1.4 on the right.)

> There certainly seems to be enough traps and pitfalls in this geometry
> stuff.  I'm looking through your source code and as my understanding
> increases, hopefully I'll be able to add some further checks for special
> cases.

Well.. it's good to remember making a completely bug-free
implementation of Area simply isn't possible without using special
robust algorithms, which would be slow and difficult. So we use these
simpler methods, and trust that those who need that level of precision
(GIS engineers) will be using the special-purpose software which is
available. (There is an LGPL java library for this)

You can find plenty of cases which will completly screw up or hang,
both with my implementation and the JDK if you just feed it random
GeneralPath-objects with a sufficiently large number of segments.

/Sven


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]