Title

Guaranteed calculation about the intersection of curves

Author

shaowb

Description

This project is set up for the intersection of curves. It aims to develop an algorithm that can calculate the intersections of curves both efficiently and rigorously.

Properties

Public

  • 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:

  1. the equation of $f_1$;
  2. the equation of $f_2$;
  3. the tolerance $\varepsilon$;
  4. the maximum size of the area;
  5. 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 Linux platform.

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.

comparison of performance

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.

Virtual Machine Setting

(Please login first to start the virtual machine.)

About file revision at virtual machine

For owner of the project, the file revised on the virtual machine will be saved after shutting down the server. As a visitor user, one can revise files in the booted virtual machine, but the revision will be aborted once the server is shut down.

About Machine Type

The Google app compute engine provides a detailed guide of the machine type. For more detailed information, please refer to More detail.
If you need a high-spec machine type, please contact the site manager.