[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Line2D intersection

From: Sven de Marothy
Subject: Re: Line2D intersection
Date: Tue, 03 Aug 2004 21:14:40 +0200


>I modified the Line2D class to correct the linesIntersect() method - a
>patch is attached.  The fix is based on an algorithm described in
>"Computational Geometry in C" (2nd edition) by Joseph O'Rourke.  

Great! I've tried it out, and it seems to work just fine. And it appears
to be relatively robust too. (But not invincible)

For instance, Sun's implementation can't handle lines which are colinear
within numerical error, for instance try:
(492.4307556152344,315.69091796875) to
and (201.19495192826076,240.0653816715973) to

(There are open-source CAD/GIS libraries like JTS which provide numerically robust
algorithms for those who really need 14 significant digits for every
calculation and don't mind speed.)

Actually most of my work on Area() at the moment is trying out the
robustness. At the moment it gets into some trouble with shapes that
have > 1000 or so self-intersections.

>Re-reading Sven's earlier post, it sounds as though he has a fix for
>the problem also, which I'll try to find out more about (I couldn't
>find it posted anywhere).

Yes, I've written intersection-point code for Area, so I figured I'd
just adapt that to return true or false instead of a point or null.
But I think your code seems better (haven't compared them against
eachother though).

Just one suggestion: I'm (hopefully) going to be done with Area before
the end of the month, and the remaining Arc2D stuff (and whatever else
is left in geom.*) should be pretty trivial to do. So instead of making
a bunch of small commits, I'd like to roll this all into one big geom.*
patch, since any updates to this will need to be sent over to the
gcj-gui-branch guys, and it'd be less work for them.

Does that sound OK?

Oh, and keep up the good work on writing tests! It's very useful!

(If only someone with Mauve CVS would commit them for you..
doesn't seem to be much action on that mailing-list)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]