Geometry package:GSoC17

Boolean operations with polygons

Objectives

  1. Implement a set of boolean operations and supporting function for acting on polygons.

  2. These include the standard set of potential operations such as union/OR, intersection/AND, difference/subtraction, and exclusiveor/XOR.

  3. Other things to be implemented are the following functions: polybool, ispolycw, poly2ccw, poly2cw, poly2fv, polyjoin, and polysplit.

Expectations

Mentor:

Developer:

 1. Incorporating Clipper native oct interface instead of mex.
 2. Adding new algorithm as per the paper of F. Martínez, A.J. Rueda, F.R. Feito
 3. Improve the already implemented scripts ispolyccw, poly2ccw, poly2cw, polyjoin, polysplit, and ensure that they are compatible with MATLAB.
 4. Devise an automated way to ensure that the functions which are in geometry package repo are synced with those in matGeom.

Workplan

Tasks

Task 0:

 Benchmark Piyush polygon union written as an .oct file against the current .mex interface to clipper in geometry 3.0

If task 0 shows bad performance of mex, then

1. Clipper native oct interface instead of mex

if mex is ok

1. Add F. Martínez, A.J. Rueda, F.R. Feito algorithm

2. Salvage work from last GSoC

Maybe

Add CGAL interface for poly clipping

Details of proposed work

This section describes the overall idea of implementation and the workplan for the implementation of the new algorithmalgorithm which is based on the paper by F. Martínez, A.J. Rueda, F.R. Feito.

Basic structure of the program for boolean operations :

1. Take the polygons in standard input form of Octave (NaN separated or Cell arrays) and convert it into the required input format of the algorithm (the way it is implemeted). This part will be handled by m script.

2. Implement .cc file which will return the resultant polygons. This will also contain input validation.

3. oct-interface will be created for this file.

4. The output of the cpp code will be passed onto the m script which will handle the necessary processings before returning it as final result.

Expected Challenges :

1. Handling overlapping edges seems to be a bit tedious with this algorithm. It will surely be a challenge.

Syncing matGeom and geometry

The goal is to devise a somewhat automated way to ensure that the functions which are there in geometry are synced with those in matGeom without manually checking the edits.

To achieve this, first a workaround is implemented on a dummy repository dummyMatGeom. Its master branch is matGeom (dummy) and there is another branch (named geometry) is created which contains geometry package (dummy). To test the entire procedure, go to the dummy repository dummyMatGeom , pull both branches in different folders, say "dummyMatGeom" for master branch and "dummyGeom" for geometry branch. Then follow the given steps. 1. go to the local dummyMatGeom directory (named dummyMatGeom) and pull upstream (dummy matGeom) using these commands :

  - git fetch origin master
  - git reset --hard FETCH_HEAD
  - git clean -df
  This will ensure that your local repo is exactly same as your current version of matGeom. Here, we are doing hard reset because when we apply folder structure change script (next step), it might have changed its structure.

2. run the following octave command.

  - rmdir("dummyGeom/deprecated","s");
  - movefile("dummyMatGeom/matGeom/deprecated","dummyGeom/");
  - movefile("dummyMatGeom/matGeom", "dummyGeom/");
  - rmdir("dummyGeom/inst","s");
  - rename("dummyGeom/matGeom","dummyGeom/inst"); 
  This will simply replace the scripts of geometry with those of matGeom. Don't worry, we are not going to push this  whole matGeom script folder onto our geometry repo.We'll now commit and push only those scripts which have been modified and the rest of scripts will remain as it is, in the remote repository(geometry branch).

3. Now, go to local geometry directory (dummyGeom) and run following command.

  - git diff --name-only --diff-filter=M | xargs git add
  - git commit -m "synced with matGeom"
  - git push origin master:geometry
  This will sync the scripts which were already present in the geometry branch with those of the matGeom branch without disturbing other scripts.

4. Now, update your local geometry repo by force pulling from the remote branch.

  - git pull -f origin master:geometry

Challenges :

Clearly, the above procedure will only sync the script of the function, not it's tests and demo, which are in separate folders in a Matlab package structure. Even if we try to concatenate their corresponding test/demo scripts with the function scripts (as it is in an octave package structure), there will be discrepancies because the notion or writing tests for octave and matlab packages are quite different. The way octave allows tests to work is unique to octave as explained here. SO, we can't simply concatenate the Matlab test scripts with the functions.

Discoveries

On benchmarking the polyunion function in oct interface vs the mex interface, it is found that oct interface had twice as better performance as mex. As it doesn't ensure much advantage, it is not worthed to rewrite the package with oct.

External links

Github repository where the work is stored.