Editing Geometry package:GSoC17

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 1: Line 1:
== Boolean operations with polygons ==
== Boolean operations with polygons ==


'''Developer''': [[User:PiyushJain | Piyush Jain]]
'''Developer''': Piyush Jain


'''Mentor''': [[User:KaKiLa | JuanPi Carbajal]]
'''Mentor''': [[User:KaKiLa | JuanPi Carbajal]]


=== Objectives ===
=== 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 ===
=== Expectations ===
Line 16: Line 11:


* Developer:
* Developer:
  1. Incorporating Clipper native oct interface instead of mex.
  2. Adding new [http://www4.ujaen.es/~fmartin/bool_op.html 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 [https://github.com/kakila/matGeom matGeom].


== Workplan ==
== Workplan ==
Line 28: Line 19:
   Benchmark Piyush polygon union written as an .oct file against the current .mex interface to clipper in geometry 3.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
* Salvage work from [https://bitbucket.org/amr_keleg/octave-geometry last GSoC]
 
* Clipper native oct interface instead of mex
1. Clipper native oct interface instead of mex
* Add F. Martínez, A.J. Rueda, F.R. Feito [http://www4.ujaen.es/~fmartin/bool_op.html algorithm]
 
if mex is ok
 
1. Add F. Martínez, A.J. Rueda, F.R. Feito [http://www4.ujaen.es/~fmartin/bool_op.html algorithm]
 
2. Salvage work from [https://bitbucket.org/amr_keleg/octave-geometry last GSoC]
 
Maybe
* Add CGAL interface for poly clipping
* 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 algorithm[http://www4.ujaen.es/~fmartin/bool_op.html algorithm] which is based on the [http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdf 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 [https://github.com/piyush-jain1/dummyMatGeom/ 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 [https://github.com/piyush-jain1/dummyMatGeom/ 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");
  - copyfile("dummyMatGeom/matGeom/deprecated","dummyGeom/");
  - copyfile("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 resetting it from the remote geometry branch.
  - git fetch origin geometry
  - git reset --hard origin/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 [http://wiki.octave.org/FAQ#What_features_are_unique_to_Octave.3F 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 ==
== External links ==
* [https://github.com/piyush-jain1/GSoC17OctaveGeometry Github repository ] where the work is stored.
* [https://github.com/ Github repository ] where the work is stored.
Please note that all contributions to Octave may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Octave:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)