Experimental Data and Code

This webpage contains the Java Code and experimental data for our paper

Adaptive Isotopic Approximation of Nonsingular Curves:
the Parametrizability and Nonlocal Isotopy Approach

Long Lin and Chee Yap
Discrete & Comp.Geometry. Vol.45, No.4, pp.760-795, 2011.
Special Issue based on 25th SoCG, in Aarhus, Denmark, Jun 8--10, 2009.

The following preliminary Java codes are implemented in Eclipse SDK Version 3.3.0. We use it to experiment with our algorithms (Balanced Cxy, Rectangular Cxy) and to compare with known algorithms (PV, Snyder). Since we did not implement a polynomial parser in Java, the input functions need to be manipulated manually. We plan to translate the codes to C++ to be distributed with our open source Core Library.

First, we will show a figure by running the four algorithms on the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.5, 1.5), (1.5, 1.5)] to give some intuition of our approaches (the Balanced Cxy Algorithm and Rectangular Cxy Algorithm): produces less boxes than PV, without isolating roots (like Snyder). The Rectangular Cxy Algorithm even produces less boxes than Snyder's Algorithm.




Then, we will show the experimental results for each of the four algorithms. These experiments show that the Balanced Cxy Algorithm is faster than Snyder and PV's Algorithm. Furthermore, we refine the Balanced cxy Algorithm to Rectangular Cxy Algorithm to achieve even better performance.

Snyder's Algorithm
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.5, 1.5), (1.5, 1.5)], the Snyder's algorithm produces 112 boxes in 31 milliseconds.
Example 2 Approximation of the curves f(X,Y)=X^2-100Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the Snyder's algorithm produces 16 boxes in less than 15 milliseconds.
Example 3 Approximation of the curves f(X,Y)=X^2-1000Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the Snyder's algorithm produces 22 boxes in 16 milliseconds.
Example 4 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-1.4, -1.4), (1.5, 1.5)], the Snyder's algorithm produces 10 boxes in less than 1 milliseconds.
Example 5 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-14, -14), (15, 15)], the Snyder's algorithm produces 1036 boxes in 110 milliseconds.

Remark: We can not test the curve f(X,Y)=X(XY-1)=0 inside the box [(-1.5, -1.5), (1.5, 1.5)] or [(-15, -15), (15, 15)], which is because the Snyder's algorithm doesn't allow the curve to overlap the sides' of boxes.

PV Algorithm
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.5, 1.5), (1.5, 1.5)], the PV algorithm produces 196 boxes in 31 milliseconds.
Example 2 Approximation of the curve f(X,Y)=X^2-100Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the PV algorithm produces 268 boxes in 15 milliseconds.
Example 3 Approximation of the curve f(X,Y)=X^2-1000Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the PV algorithm produces 811 boxes in 31 milliseconds.
Example 4 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-1.5, -1.5), (1.5, 1.5)], the PV algorithm produces 82 boxes in 15 milliseconds.
Example 5 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the PV algorithm produces 5686 boxes in 157 milliseconds.

PV Algorithm with epsilon precision
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.4, -1.4), (1.5, 1.5)] with 0.01 precision, the PV algorithm produces 8509 boxes in 219 ms.

Balanced Cxy Algorithm
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.5, 1.5), (1.5, 1.5)], the Balanced Cxy algorithm produces 112 boxes in 16 milliseconds, which is twice as fast as Snyder and PV.
Example 2 Approximation of the curves f(X,Y)=X^2-100Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the Balanced Cxy algorithm produces 37 boxes in less than 1 milliseconds.
Example 3 Approximation of the curves f(X,Y)=X^2-1000Y^2=0 inside the box [(-1.4, -1.4), (1.5, 1.5)], the Balanced Cxy algorithm produces 220 boxes in 15 milliseconds.
Example 4 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-1.5, -1.5), (1.5, 1.5)], the Balanced Cxy algorithm produces 40 boxes in 15 milliseconds.
Example 5 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Balanced Cxy algorithm produces 2878 boxes in 125 milliseconds.
Example 4 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-1.4, -1.4), (1.5, 1.5)], the Balanced Cxy algorithm produces 13 boxes in less than 1 milliseconds.
Example 5 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-14, -14), (15, 15)], the Balanced Cxy algorithm produces 1510 boxes in 63 milliseconds.

Balanced Cxy Algorithm with epsilon precision
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.4, -1.4), (1.5, 1.5)] with 0.01 precision, the Balanced Cxy algorithm produces 8497 boxes in 204 ms.

Rectangular Cxy Algorithm
Example 1 Approximation of the curve f(X,Y)=X^2(1-X)(1+X)-Y^2+0.01=0 inside the box [(-1.5, 1.5), (1.5, 1.5)], the Rectangular Cxy algorithm with maximum aspect ratio 2 produces 74 boxes in 15 ms, which is slightly better than Cxy.
Example 2 Approximation of the curves f(X,Y)=X^2-100Y^2=0 inside the box [(-1.5, -0.15), (1.5, 0.15)], the Rectangular Cxy algorithm with maximum aspect ratio 5 produces 20 boxes in 15 ms.
Example 3 Approximation of the curves f(X,Y)=X^2-1000Y^2=0 inside the box [(-1.5, -0.15), (1.5, 0.15)], the Rectangular Cxy algorithm with maximum aspect ratio 5 produces 36 boxes in 15 ms.
Example 4 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-1.5, -1.5), (1.5, 1.5)], the Rectangular Cxy algorithm with maximum aspect ratio 5 produces 17 boxes in less than 1 ms.
Example 5 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Rectangular Cxy algorithm with maximum aspect ratio 5 produces 258 boxes in 32 ms.
Example 6 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Rectangular Cxy algorithm with maximum aspect ratio 10 produces 140 boxes in 31 ms.
Example 7 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Rectangular Cxy algorithm with maximum aspect ratio 20 produces 82 boxes in 16 ms.
Example 8 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Rectangular Cxy algorithm with maximum aspect ratio 40 produces 54 boxes in 15 ms.
Example 9 Approximation of the curve f(X,Y)=X(XY-1)=0 inside the boxe [(-15, -15), (15, 15)], the Rectangular Cxy algorithm with maximum aspect ratio 80 produces 37 boxes in 15 ms.