I have a suggestion about modifications to the JTS DD class to yield higher
performance for certain applications.
The JTS DD class provides routines for extending the precision of
floating-point arithmetic operations by representing numbers using two-doubles
instead of one (attaining approximately 30 digits of decimal precision).
Recently, I have been experimenting with using DD in a Java application I have
for creating Triangulated Irregular Networks (TINs), or "triangular meshes",
from lidar data. One of the key operations in all triangular mesh building
operations is the "in-circle" method which determines if an arrangement of
neighboring points is triangulated in an optimal manner. This method gets
called quite frequently. For a 1.02 million points sample, my application
performs about 18.7 in-circle tests. But because in-circle depends on the
evaluation of a determinant that can often be very close to zero (but still
significant), precision is an important consideration. Thus the motivation for
using DD. In fact, the DD class actually includes an implementation of a
method called DD.inCircleDDNormalized().
The problem is that DD is substantially more expensive than straight
floating-point operations. In my testing, I developed two routines, one that
would use DD only when "absolutely necessary" and one that used it all the
time. The runtimes for the application variations were:
a) Standard floating point: 0.769 seconds
b) Using DD: 8.078 seconds
Part of that difference is unavoidable. Extended precision operations simply
cost more than hardware-based calculations. But looking at the code I noticed
that one of the features of DD is that in using it, you have to create a very
large number of short-lived objects. For example, to add a+b, you need to
create at least two DD objects (one for a, one for b, and then you can either
store the result in a or produce a third object depending on whether or not you
use one of what DD calls "self" methods). Once you create an object, there is
no way to set their value so that they may be While Java has made great strides
over the years in terms of handling the creation and garbage collection of
large numbers of objects, it would be far more efficient if the DD objects
could be reused.
For example, I hacked a version of DD to add a couple of "set" methods that let
me set the values of DD objects. I created all the DD objects I needed at
application start up and used the set method to recycle them every time the
in-circle method was called. The results:
a) Using DD: 8.078 seconds
b) Recycling Objects: 4.404 seconds
The nearly 50 percent reduction in run time was due to just the savings in not
creating and garbage collecting objects. The cost of the real work done by DD
did not change.
These changes are only worthwhile in applications that perform a large number
of the same calculation over-and-over again. Of course, that's just the kind of
thing that shows up in computational geometry applications. Although it could
be argued that "non-mutable" objects are "safer" than mutable objects I believe
that any developer with basic experience in handling data would understand how
to use mutable objects without mishap. And, after all, the authors of DD
already found it necessary to implement "self" objects that mutate the content
of DD objects, so there is a precedent.
Basically I suggest the introduction methods such as set(), setSubtract(a,b),
setMultiply(a,b), etc. to DD. Developers could then allow apply them to their
code where appropriate.
The code snippet below gives the guts of my in-circle implementation. The
algebra is the same as that used in DD.inCircleDDNormalized(). All DD objects
are instantiated in the constructor (not shown).
// inCircle for coordinates a, b, c, d (DD used p instead of d)
// "q" variables are pre-allocated DD objects. Set methods are
// used to set values of the object.
q11.setSubtract(a.x, d.x);
q21.setSubtract(b.x, d.x);
q31.setSubtract(c.x, d.x);
q12.setSubtract(a.y, d.y);
q22.setSubtract(b.y, d.y);
q32.setSubtract(c.y, d.y);
q11s.setSqr(q11);
q12s.setSqr(q12);
q21s.setSqr(q21);
q22s.setSqr(q22);
q31s.setSqr(q31);
q32s.setSqr(q32);
q11_22.set(q11);
q11_32.set(q11);
q21_12.set(q21);
q21_32.set(q21);
q31_22.set(q31);
q31_12.set(q31);
q21_32.selfMultiply(q32);
q31_22.selfMultiply(q22);
q31_12.selfMultiply(q12);
q11_32.selfMultiply(q32);
q11_22.selfMultiply(q22);
q21_12.selfMultiply(q12);
// the following lines use s1,s2,s3, etc. as a convenience
// naturally, you have to be careful about what you overwrite...
DD s1 = q11s.selfAdd(q12s);
DD s2 = q21s.selfAdd(q22s);
DD s3 = q31s.selfAdd(q32s);
DD t1 = q21_32.selfSubtract(q31_22);
DD t2 = q31_12.selfSubtract(q11_32);
DD t3 = q11_22.selfSubtract(q21_12);
s1.selfMultiply(t1);
s2.selfMultiply(t2);
s3.selfMultiply(t3);
s1.selfAdd(s2).selfAdd(s3);
return s1.doubleValue();------------------------------------------------------------------------------
"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos. Get
unparalleled scalability from the best Selenium testing platform available.
Simple to use. Nothing to install. Get started now for free."
http://p.sf.net/sfu/SauceLabs
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
