- README
- DIRECTORY
- DEMO

# Quantified calculation about the intersection of curves

[toc]

# 1. Introduction

This project develops a new and efficient algorithm to rigorously calculate the intersection of 2D curves. This work is mainly completed by Shao Wenbin, under the instruction of LIU Xuefeng(@Niigata University) and CHEN Falai(@USTC).

For simplicity of argument, we consider the polynomial system $$f_1(x,y)=f_2(x, y)=0$$ under the assumption that the system has only a finite number of roots. Notice this assumption holds for co-prime polynomials. For general polynomials with a common factor, one can study the common factor independently and then consider the intersection of polynomials after removing the factor.

Let us introduce the main idea of the algorithm (the detailed description can be found in our coming paper). To provide a sharp bounding box for the exact intersection point, we subdivide the area into small blocks and then verify the solution existence in each block. The verification process has two parts: firstly, the non-existence sub-blocks are excluded by applying the Bézier representation of curves and resultant method; secondly, a precise verification is done by re-grouping the remained blocks and utilizing the Krawczyk method. Here, the Krawczyk method is based on the fixed-point theorem and can provide tight bounds of roots for non-linear systems. To have a successful verification under specified tolerance, the subdivision process will be executed recursively.

The rounding error in the floating point number computation is rigorously estimated by utlizing the interval arithmetic.

# 2. About algorithm

This project provides several algorithms, among which the algorithm named by "`CurvesIntersectionByKrawczykBezierPlus`

" gives the best performance for calculating the intersection of the curves. All algorithms have been compiled and placed in the `bin`

directory. The manual below focuses on the `CurvesIntersectionByKrawczykBezierPlus`

algorithms. For other revision of the algorithms, please refer to section "the revised versions of our algorithm" at the end of this document.

To compare with existing approaches, we also provide the direct application version of the Krawczyk method named by "`CurvesIntersectionByKrawczykPlus`

".

# 3. About input of the program

In our algorithms, all input formats are consistent. The default region of interest is set as $[0, 1]\times[0, 1]$. Each time the program is executed, the following five parameters are required:

- the equation of $f_1$;
- the equation of $f_2$;
- the tolerance $\varepsilon$;
- the maximum size of the area;
- the output.

## The equation of $f_1$ and $f_2$

Here, the equations of $f_1$ and $f_2$ are expressed with the power basis. Suppose the equation of $f_1$ is expressed as $$ f_1(x,y)=\sum_{i=0}^m\sum_{j=0}^na_{ij}x^iy^j. $$ Then the coefficient matrix of $f_1$ is $A = (a_{ij})_{m\times n}$.

The coefficient matrixs of $f_1$ and $f_2$ are recorded in csv files. For example, the equations of $f_1$ and $f_2$ are
$$
f_1(x,y) = 5 - 16x + 16x^2 - 4y\
f_2(x,y) = 5 - 4x + 16y^2 -16y
$$
Then we can prepare two `.csv`

files, denoted as `1.csv`

and `2.csv`

respectively.

For `1.csv`

, it writes

5,-4 -16,0 16,0

For `2.csv`

, it writes

5,-16,16 -4,0,0

**Note**: If the given path does not exist or the format of the stored csv file is incorrect, the program will throw an exception. Our program does not verify whether the path exists or whether the content format of csv file meets the standard.

## The tolerance $\varepsilon$

This requires that the error between the calculated solution and the real solution is less than the given tolerance $\varepsilon$.

## The maximum size

The maximum size serves as the threshold for the termination of subdivision. Once the area size is less than the maximum size, the subdivision will be terminated, where the maximum size should be less than the given tolerance $\varepsilon$.

# 4. About output of the program

The output file will have two forms. If the `DEBUG`

macro is not specified when compiling, the information in the output file will contain some basic information. If the `DEBUG`

macro is specified when compiling, the detailed information of each layer of calculation will be displayed after run our program. We have provided two kinds of compiled executable programs. Programs compiled with `DEBUG`

macros will end with debug as a suffix.

The following output files are two examples about whether to use `DEBUG`

macros to compile. It is obvious to show that after using the `DEBUG`

macro, more information about the calculation details can be provided.

No use of `DEBUG`

macro

{ "f1_deg" : 2, "f2_deg" : 2, "init_time" : 8.2000000000000001e-05, "kernel" : { "Bezier" : 269, "Krawczyk" : 21 }, "max_iteration_region" : { "xl" : 0.75, "xr" : 1, "yl" : 0.75, "yr" : 1 }, "max_iteration_steps" : 5, "maximum_size" : 1e-08, "may_contain_solutions" : 0, "root_message" : [ { "x" : 0.90450849718747373, "y" : 0.90450849718747373 }, { "x" : 0.25, "y" : 0.5 }, { "x" : 0.49999999999999994, "y" : 0.25 }, { "x" : 0.34549150281252622, "y" : 0.34549150281252633 } ], "root_nums" : 4, "tolerance" : 9.9999999999999995e-07, "total_time" : 0.0051879999999999999 }

Use of `DEBUG`

macro

{ "connected" : [ { "krawczyk" : [ { "K" : { "xl" : 0.84375, "xr" : 0.96875, "yl" : 0.84375, "yr" : 0.96875 }, "contains_root" : true, "has_K" : true, "has_iteration" : true, "iteration" : [ { "step" : 0, "xl" : 0.75, "xr" : 1, "yl" : 0.75, "yr" : 1 }, { "step" : 1, "xl" : 0.84375, "xr" : 0.96875, "yl" : 0.84375, "yr" : 0.96875 }, { "step" : 2, "xl" : 0.89062499999999989, "xr" : 0.91840277777777779, "yl" : 0.89062499999999989, "yr" : 0.91840277777777779 }, { "step" : 3, "xl" : 0.90381836611456168, "xr" : 0.90519862836438925, "yl" : 0.90381836611456168, "yr" : 0.90519862836438925 }, { "step" : 4, "xl" : 0.90450679319287497, "xr" : 0.90451020118207248, "yl" : 0.90450679319287497, "yr" : 0.90451020118207248 }, { "step" : 5, "xl" : 0.90450849717708548, "xr" : 0.90450849719786197, "yl" : 0.90450849717708548, "yr" : 0.90450849719786197 } ], "iteration_steps" : 5, "reason" : "normal", "region" : { "xl" : 0.75, "xr" : 1, "yl" : 0.75, "yr" : 1 } }, { "contains_root" : true, "has_K" : false, "has_iteration" : false, "reason" : "is singular", "region" : { "xl" : 0, "xr" : 0.75, "yl" : 0, "yr" : 0.75 } } ], "regions" : [ { "label" : 1, "xl" : 0.75, "xr" : 0.875, "yl" : 0.875, "yr" : 1 }, { "label" : 1, "xl" : 0.875, "xr" : 1, "yl" : 0.875, "yr" : 1 } ......., ], "size" : 36, "type" : 2 } ], "debug" : [ { "layer" : [ { "Bezier" : true, "is_minimal" : false, "region" : { "xl" : 0, "xr" : 1, "yl" : 0, "yr" : 1 }, "size" : 1 } ], "level" : 0 }, { "layer" : [ { "Bezier" : true, "is_minimal" : false, "region" : { "xl" : 0.5, "xr" : 1, "yl" : 0.5, "yr" : 1 }, "size" : 0.5 }, { "Bezier" : true, "is_minimal" : false, "region" : { "xl" : 0, "xr" : 0.5, "yl" : 0.5, "yr" : 1 }, "size" : 0.5 }, { "Bezier" : true, "is_minimal" : false, "region" : { "xl" : 0, "xr" : 0.5, "yl" : 0, "yr" : 0.5 }, "size" : 0.5 }, { "Bezier" : true, "is_minimal" : false, "region" : { "xl" : 0.5, "xr" : 1, "yl" : 0, "yr" : 0.5 }, "size" : 0.5 } ], "level" : 1 }, ......, ], "f1_deg" : 2, "f2_deg" : 2, "init_time" : 7.3999999999999996e-05, "interval" : { "lower" : 0, "max_interval" : 0, "upper" : 0 }, "kernel" : { "Bezier" : 269, "Krawczyk" : 21 }, "max_iteration_region" : { "xl" : 0.75, "xr" : 1, "yl" : 0.75, "yr" : 1 }, "max_iteration_steps" : 5, "maximum_size" : 1e-08, "may_contain_solutions" : 0, "root_message" : [ { "x" : 0.90450849718747373, "y" : 0.90450849718747373 }, { "x" : 0.25, "y" : 0.5 }, { "x" : 0.49999999999999994, "y" : 0.25 }, { "x" : 0.34549150281252622, "y" : 0.34549150281252633 } ], "root_nums" : 4, "tolerance" : 9.9999999999999995e-07, "total_time" : 0.0081659999999999996 }

## Explanation of the output

The following table shows the explanation of the main fields in the output file:

Field | Explanation |
---|---|

`f1_deg` |
The degree of polynomial $f_1$ |

`f2_deg` |
The degree of polynomial $f_2$ |

`root_nums` |
The number of approximate solution after verification about existence and uniqueness |

`tolerance` |
Store the input parameter for the tolerance $\varepsilon$ |

`maximum_size` |
Store the input parameter for the maximum size |

`total_time` |
The time required for the program to run |

`init_time` |
The time required for program initialization |

`max_iteration_steps` |
If the current program uses the Krawczyk method, then this value stores the maximum number of iteration steps by the Krawczyk method |

`max_iteration_region` |
In the current example, the largest area with a unique solution by applying the Krawczyk method to determine. |

In addition, there are some structured data.

`root_message`

This field is used to store all the solutions after verification by the Krawczyk method.

"root_message" : [ { "x" : 0.90450849718747373, "y" : 0.90450849718747373 }, { "x" : 0.25, "y" : 0.5 }, { "x" : 0.49999999999999994, "y" : 0.25 }, { "x" : 0.34549150281252622, "y" : 0.34549150281252633 } ],

`may_contain_solutions`

and `may_contain_solution_regions`

When all verification fails to draw valid conclusions and the area size is less than the `maximum_size`

, these areas will be considered as areas that may contain solutions.

The field `may_contain_solutions`

stores the number of regions that may contain solutions.

The field `may_contain_solution_regions`

stores the detailed information about the regions that may contain solutions.

`kernel`

Test the number of calls of each module, including the Bezier method, the resultant method and the Krawczyk method.

"kernel" : { "Bezier" : 269,//the number of calls of the Bezier method "Krawczyk" : 21//the number of calls of the Krawczyk method },

`debug`

This is a list used to record whether there is no solution after the Bezier method or the resultant method. If the area is asserted to have no solution, then this region is marked by `false`

, otherwise marked by `true`

. All areas are divided into different groups according to the same size and stored in the `layer`

filed. The `level`

field in the layer is used to indicate the label of the layer.

{ "Bezier" : true,//may contain roots by the judgment of the Bezier method "is_minimal" : false,//whether the size is less than the maximum size "region" : { "xl" : 0, "xr" : 0.5, "yl" : 0, "yr" : 0.5 }, "size" : 0.5//the size of current region },

`connected`

This field is used to store the relevant information of the connected components labeling and verification about the existence and uniqueness of calculated solutions. It consists of two field: `regions`

and `krawczyk`

.

`regions`

The field stores all areas of the current layer. Each area is assigned a `label`

field. Having the same `label`

field means that they are located in the same connected component. The filed `size`

and `type`

denote the size of each region and the number of all regions in current layer.

`krawczyk`

This field records the details of using the Krawczyk method to judge each connected component. After the judgment of the Krawczyk method, the conclusion about this area will be recorded in the field `reason`

.

There are four kinds of results after the judgment

Result | Explanation |
---|---|

does not contain zero | The polynomial range of the current region does not contain zero, indicating that there is no solution in the current region. |

is singular | It is hard to draw a conclusion and require further judgments. The two curves in the current region are close to the singularity. |

is empty for intersection | After the current area is mapped by the Krawczyk method, the intersection with the current area is empty, indicating that the current area has no solution. |

The intersection is in the intersecting set of K and X | -- |

K is in X but the norm of R is not less than 1 | -- |

has only one intersection | -- |

Additionally, the following information will be recorded during each judgment:

Field | Explanation |
---|---|

`has_K` |
If the mapping area by the Krawczyk method can be calculated, it is recorded as true, otherwise it is recorded as false. |

`has_iteration` |
If it is determined that there is a unique solution, the iteration scheme will be implemented. Then this field is recorded as true, otherwise it is recorded as false |

`contains_root` |
Whether the area contains the intersection points. |

`iteration` |
The detailed information about the iteration process. |

The output refers to a `.json`

file path. When input the necessary parameters, all results will be recorded in the `.json`

file, where the following message is included:

- the degree of $f_1$
- the degree of $f_2$
- the tolerance $\varepsilon$
- the message about intersections
- the message about unknown's regions

# 5. A quick start tutorial

The following steps can help you compile and run the program `CurvesIntersectionByKrawczykBezierPlus`

on the **ganjin** platform.

**Step 1**: compile the whole project

cd basic mkdir build chmod 755 build.sh ./build.sh

The executable file will be generated in the `bin`

directory.

**Step 2**: check whether it is valid when the binary loads:

```
cd bin
./CurvesIntersectionByBezierPlus -h
```

If the following information appears in the console, it means that the dynamic libraries are loaded successfully.

Options: ->Required arguments: -m, --f1 The csv file path to store the coefficients of the curve. -n, --f2 The csv file path to store the coefficients of the curve. -o, --out The json file path of the output file to store the results about the intersection algorithm. ->Optional parameters: -t, --tolerance Maximum distance between approximate solution and true solution. The default value is set to 1e-6. -s, --mini_size The minimum size of the area to terminate the subdivision. Require the minimum size to be smaller than the value of tolerance. The default value is set to 1e-14. -h, --help Print the message and exit.

Otherwise, please check whether the path of the dynamic libraries specified earlier in step 1 is correct.

**Step3**: Execute the program to calculate the intersection of the curve.

We provide some curve data in the `data`

folder under the root directory of the project. You can choose a set of data to run our program for testing. Assuming that the curve data in folder `/project/path/data/1`

is selected, the tolerance is set to `1e-6`

, the maximum size of the region is set to `1e-8`

, and the path of the output file is set to `/project/path/result.json`

, then you can execute the following command:

./CurvesIntersectionByKrawczykBezierPlus --f1=/project/path/data/1/1.csv --f2=/project/path/data/1/2.csv --tolerance=1e-6 --maxinum_size=1e-8 --out=/project/path/result.json

All calculation results will be stored in `result.json`

.

All our projects are placed in the `basic`

and `pro`

folders. The folder in basic only needs to install the dependency package boost jsoncpp, eigen to compile and run. In the `pro`

folder, you need to install the mathematica environment to compile.

# 6. Configure in your computer

Since **ganjin** cannot support wolfram engine, you can download our project and configure it on your own computer to execute all the programs.

Our project is tested under the ** Linux** platform. We have not tested the

`Mac`

platform or `Windows`

platform. Therefore, the following tutorial is also compiled based on the **platform.**

`Linux`

To build our project in your computer, you need to confirm the following dependencies first.

Our project is a regular cmake project that can be built as shown in the following snippet.

```
mkdir build
cd build
cmake ..
make
```

The executable programs will be compiled and placed in the `bin`

folder.

# 7. Drawing details

We provide python programs to plot the detailed information from the debug version. The calculation results of each layer will be marked on the picture. All python scripts are placed in the `plot`

folder under the root directory of our project. The introductions of each python file are as follows:

The python file | Introduction |
---|---|

`Connected_components_labeling.py` |
Mark the connected components with different colors. |

`Bezier.py` |
Use the marker `X` to indicate the area without solution by the Bezier method. The green area indicates that it may contain a solution. |

`Resultant.py` |
Use the blue marker `X` to indicate the area without solution by the resultant method. The green area indicates that it may contain a solution. |

`Krawczyk.py` |
Use a red rectangular box to indicate the area to be verified by using the Krawczyk method. |

`Results.py` |
Draw all roots which have been verified about the existence and uniqueness by the Krawczyk method. |

The above python scripts all need to provide the following input:

`f1`

Algebraic expression $f_1$ of the first curve.

`f2`

Algebraic expression $f_2$ of the second curve.

`path`

Output file obtained by debug version mentioned earlier.

`layer`

Number of layers of concern.(In the file `Result.py`

, it is not necessary to provide this parameter.)

When executing the python script, please modify the above four parameters.

# 8. The revised versions of our algorithm

Below we provide more revised versions of our algorithm for testing:

`CurvesIntersectionByBezier`

Direct application of the Bezier method to exclude the regions which do not contain intersections.

`CurvesIntersectionByKrawczyk`

Direct application of the Krawczyk method to verify the existence and uniqueness of the intersections. The interval arithmetic is applied to estimate the range of curves in a given region.

`CurvesIntersectionByKrawczyk`

Direct application of the Krawczyk method to verify the existence and uniqueness of the intersections. The Bezier method is applied to estimate the range of curves in a given region.

`CurvesIntersectionByKrawczykBezier`

The Bezier method is applied to as a raw verification to exclude the regions which do not contain intersections. After that, a precise verification is done by re-grouping the boxes and utilizing the Krawczyk method.

`CurvesIntersectionByKrawczykBezier_debug`

This is a debug version for `CurvesIntersectionByKrawczykBezier`

to store the detailed information during the calculation.

`CurvesIntersectionByKrawczykBezierFloatingPointArithmetic`

Compared with `CurvesIntersectionByKrawczykBezier`

, the floating-point decimal is used to calculate the Bezier coefficient in the calculation process.

`CurvesIntersectionByKrawczykBezierFloatingPointArithmetic_debug`

This is a debug version for `CurvesIntersectionByKrawczykBezierFloatingPointArithmetic`

to store the detailed information during the calculation.

`CurvesIntersectionByKrawczykBezierPlus`

Compared with `CurvesIntersectionByKrawczykBezier`

, the range of $f_1 - f_2$ is selected as an additional rule in the raw verification.

`CurvesIntersectionByKrawczykBezierPlus_debug`

This is a debug version for `CurvesIntersectionByKrawczykBezierPlus`

to store the detailed information during the calculation.

`CurvesIntersectionByKrawczykBezierResultant`

Compared with `CurvesIntersectionByKrawczykBezier`

, the range of the resultant $Res(f_1,f_2;x)$ and $Res(f_1,f_2;y)$ is selected as an additional rule in the raw verification.

`CurvesIntersectionByKrawczykBezierResultant_debug`

This is a debug version for `CurvesIntersectionByKrawczykBezierResultant`

to store the detailed information during the calculation.

`CurvesIntersectionByKrawczykBezierResultantPlus`

Compared with `CurvesIntersectionByKrawczykBezier`

, the range of $f_1 - f_2$, the resultant $Res(f_1,f_2;x)$ and $Res(f_1,f_2;y)$ is selected as an additional rule in the raw verification.

`CurvesIntersectionByKrawczykBezierResultantPlus_debug`

This is a debug version for `CurvesIntersectionByKrawczykBezierResultantPlus`

to store the detailed information during the calculation.

`CurvesIntersectionByCanonicalKrawczyk`

The **kv** library is provided to calculate the intersection of curves.

When each algorithm is compiled on your own computer, one or more macros need to be specified for each algorithm. Please refer to the table below for the macros required by each algorithm.

Program | Macros |
---|---|

`CurvesIntersectionByBezier` |
BEZIER |

`CurvesIntersectionByKrawczyk` |
PURE_KRAWCZYK |

`CurvesIntersectionByKrawczykBezier` |
KRAWCZYK_BEZIER |

`CurvesIntersectionByKrawczykBezier_debug` |
KRAWCZYK_BEZIER, DEBUG |

`CurvesIntersectionByKrawczykBezierFloatingPointArithmetic` |
KRAWCZYK_BEZIER_FLOATING_POINT_ARITHMETIC |

`CurvesIntersectionByKrawczykBezierFloatingPointArithmetic_debug` |
KRAWCZYK_BEZIER_FLOATING_POINT_ARITHMETIC, DEBUG |

`CurvesIntersectionByKrawczykBezierPlus` |
KRAWCZYK_BEZIER_PLUS |

`CurvesIntersectionByKrawczykBezierPlus_debug` |
KRAWCZYK_BEZIER_PLUS, MINUS_DEBUG, DEBUG |

`CurvesIntersectionByKrawczykBezierResultant` |
KRAWCZYK_BEZIER_AND_RESULTANT |

`CurvesIntersectionByKrawczykBezierResultant_debug` |
KRAWCZYK_BEZIER_AND_RESULTANT, DEBUG |

`CurvesIntersectionByKrawczykBezierResultantPlus` |
KRAWCZYK_BEZIER_AND_RESULTANT_PLUS |

`CurvesIntersectionByKrawczykBezierResultantPlus_debug` |
KRAWCZYK_BEZIER_AND_RESULTANT_PLUS, DEBUG |

`CurvesIntersectionByKrawczykPlus` |
PURE_KRAWCZYK_PLUS |

`CurvesIntersectionByCanonicalKrawczyk` |
CANONICAL_KRAWCZYK |

Every time you compile a program, please modify the corresponding macro definition in `CMakeLists.txt`

.

**Note:** When you execute the algorithm that needs to calculate the resultant, you should start the Mathematica script "`Resultant.wls`

" in the folder `bin`

first, and then use the compiled program to calculate. Since the **ganjin** website does not provide support for Mathematica, please configure the project on your own computer

## INTLAB toolbox

In the INTLAB toolbox, it also provides the function `verifynlssall`

to address the guaranteed solutions in a given box. Before start testing the performance of the INTLAB toolbox, it is required to install the INTLAB toolbox and MATLAB in your own computer. In order to keep the input and output interfaces consistent with our previous program, the function `verifynlssallForMine`

has been packaged to perform calculations. You only need to provide the file path of the two curves(`csv`

file) and the path of the output file(`mat`

file) each time. All calculations are placed in the `matlab`

folder.

# 9. Performance comparison with existing approaches

We have tested the performance of other reliable computing methods like **kv library**, the **INTLAB** toolbox (using the function `verifynlssall`

). The figure bellow provides the result obtained from kv library, the INTLAB toolbox and our method. All experiments data are stored on the ganjin online platform; see experiment_data.zip.

The graph tells that our proposed algorithm has a much improved performance than existing algorithms.

## How to repeat our experiments on ganjin website

We have provided 300 examples for the experiment. The degree of curves ranges from 2 to 16, and each degree of curves has 20 examples. In the experiment, we tested the first two hundred examples, where the degree of the polynomial ranges from 2 to 12. The following steps are how to conduct the entire experiment.

### Step1: Compile our method on ganjin website

Please modify the `CMakeLists.txt`

in the path `/home/ganjin/notebook/basic`

as follows:

cmake_minimum_required(VERSION 2.8) project(CurvesIntersectionByKrawczykBezierPlus) set(CMAKE_CXX_COMPILER "g++") set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g") set(CMAKE_C_FLAGS“$ {CMAKE_C_FLAGS} -fPIC”) set(CMAKE_CXX_FLAGS“$ {CMAKE_CXX_FLAGS} -fPIC”) include_directories(${PROJECT_SOURCE_DIR}/include) add_definitions(-w) add_definitions(-DKRAWCZYK_BEZIER_PLUS) include_directories(/usr/include/jsoncpp) include_directories(/usr/include/eigen3) aux_source_directory(./src srcfiles) set(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin) add_executable(CurvesIntersectionByKrawczykBezierPlus ${srcfiles}) target_link_libraries(CurvesIntersectionByKrawczykBezierPlus -lcln -lginac -ljsoncpp)

Then you can start compiling by issuing the following commands:

```
cd /home/ganjin/notebook/basic/build
cmake ..
make
```

### Step2: Compile kv library on ganjin website

We refer to the examples provided by the kv library official website, but only modify the input and output to ensure that the format of the input and output is consistent with our existing algorithm. Please modify the `CMakeLists.txt`

in the path `/home/ganjin/notebook/basic`

as follows:

cmake_minimum_required(VERSION 2.8) project(CurvesIntersectionByCanonicalKrawczyk) set(CMAKE_CXX_COMPILER "g++") set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g") set(CMAKE_C_FLAGS“$ {CMAKE_C_FLAGS} -fPIC”) set(CMAKE_CXX_FLAGS“$ {CMAKE_CXX_FLAGS} -fPIC”) include_directories(${PROJECT_SOURCE_DIR}/include) add_definitions(-w) add_definitions(-DCANONICAL_KRAWCZYK) include_directories(/usr/include/jsoncpp) include_directories(/usr/include/eigen3) aux_source_directory(./src srcfiles) set(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin) add_executable(CurvesIntersectionByCanonicalKrawczyk ${srcfiles}) target_link_libraries(CurvesIntersectionByCanonicalKrawczyk -lcln -lginac -ljsoncpp)

Then you can start compiling by issuing the following commands:

```
cd /home/ganjin/notebook/basic/build
cmake ..
make
```

### Step3: Start calculating by our method

There is a start script `our_method.sh`

in the folder `/home/ganjin/notebook/experiment`

. When you want to execute our algorithm to calculate all the examples, please issue the following commands:

```
chmod 755 /home/ganjin/notebook/experiment/our_method.sh
/home/ganjin/notebook/experiment/our_method.sh
```

The calculation results of each example are stored in the corresponding subfolder with the name of `our_method.json`

.

### Step4: Start calculating by kv library

There is also a start script `kv.sh`

in the folder `/home/ganjin/notebook/experiment`

. You can issue the following commands to calculate all the examples by kv library:

```
chmod 755 /home/ganjin/notebook/experiment/kv.sh
/home/ganjin/notebook/experiment/kv.sh
```

The calculation results of each example are stored in the corresponding subfolder with the name of `kv.json`

.

### Step5: Start calculating by INTLAB toolbox

Since the ganjin webisite cannot provide the toolbox, you had better confirm that the INTLAB toolbox and MATLAB are installed on your computer. Besides, please confirm that you have added the path `/home/ganjin/notebook/matlab`

to the workspace of MATLAB and you have load the module of INTLAB toolbox.

In order to excute all experiments, it is required to run the file of `summary.m`

. All variables are stored in the `.mat`

file in each subfolder of `experiment`

. There is a variable called `running_time`

for storing the running time of the whole procdure of each example. You can use the function `load`

to load the `.mat`

file to access the variable.

### Step6: Analyze the results and plot the data

Please issue the following commands to plot the data obtained by the experiments.

python plot.py

#### About the directory

Folders or files beginning with a dot are not displayed by default.