Re: (patch) java.awt.geom - implementations

[Sven de Marothy]

Hello again,

On Sat, 2004-05-22 at 00:26, Mark Wielaard wrote: 

> We like to play it a bit strict and not put anything in CVS and/or
> distribute it before the paperwork has cleared.

Very well. I'll fix the things Sascha pointed out in the meantime, and
get back to you all then.

> Otherwise could you put up the complete new source files?
Yeah, I think I'll go for that, it seems simplest. The patch wasn't
smaller anyway, and far less readable. :-)

On Sat, 2004-05-22 at 00:12, Sascha Brawer wrote:

Your comments on my documentation are noted, I'll fix them, no problem.

> Do you have a reference to an explanation of the line-crossings
> algorithm? If so, it might be good to add it to the respective method.

Yes, it's well known. Eric Haines has his text from Graphics Gems IV:
(available: http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
I didn't use his code though, nor could I; it's for lines not
Beziers)
It's not very difficult, though: translate the shape to put your
point at the origin, shoot a ray from that point along an axis 
(X+ is usual) to infinity and count the intersections. 
Odd total = inside, Even total =outside.
(aka. Jordan's curve theorem)

For GeneralPath's NON_ZERO winding rule however, you need to evaluate
the derivative at every crossing to get the winding number.

> Maybe your nice write-up of the problem with figure-8 cubic paths could
> go into the code docs? In the mailing list archive, it will be much
> harder to find in case someone stumbles over the bug/feature.

Nice write-up? Actually, I saw now it was kind of vague. In case
someone misunderstood: it's the same problem as for end-points, e.g.
the 'waist' of the figure-8 counts as one intersection, which means
points perpendicular to it on the X axis will only intersect once.

A typical (say, drawing) application often defines a curve on integer
points, and also tests on integer points. That makes the end-point
bug very real. (Sun screws up in about 1/5 of random cubics!)

Under the same circumstances, the loop-intersection is not as likely 
to end up on an integer point, it'd require the control points to form
a pythagorean triplet or something like that.
But sure, I'll note it in the code. 

> getAxisIntersections(): Would it make sense putting 1E-10 in a constant?
I considered that, but it's a slightly arbitrary number. Basically,
we want a small, non-zero number relative the curve size. Doubles
have about 14 significant digits, so I chose a factor of 1E-10 as a
good number which wouldn't disappear in rounding. I can't see why it'd
need changing except for programs using some totally insane coordinate
system. (E.g. defined on the scale of 10^-300 or something, which is
just asking for trouble, anyway.)

> I'm just curious, do you know whether your replacement of points by
> xpoints/ypoints has had much effect on performance? But please don't re-
> write anything just for finding out...

Yes I do. The options as I see them are as follows: 
Either have one set of axis-intersection code for the 
X axis and one for Y. 
(duplicating 150 lines of code only with x and y swapped)
Or: Swap the x and y coordinates and use the same code.

The former seemed too ugly to me, but would be faster.

Anyway, chosing the latter, the choice to swap X and Y
in the axis-intersection method made the rectangle contains()
and intersects() 200% slower than the Sun version.

Storing them separately and swapping references is of course much
better. But it sucks for the transform, because you can't convert
the entire thing in one call to
AffineTransform(float[], int, float[], int, int). 

The performance of GeneralPath.transform() is now about 40% slower
compared to that of Sun. Previously it was about 25% slower. :-(
(Sun has a faster AffineTransform; Using the same AffineTransform
gives the same results. Yeah, I get pedantic in my profiling.)

Anyway, I'd hate to become known for sacrificing the speed of other's
code for the sake of my own. :-)

So if you feel we should go all-out for speed, I'm completely
prepared to sacrifice my sense of aesthetics and go with the first
option. :-)

/Sven