GNU Octave – Geometry Package – GSoC 2016
This Repository ( https://bitbucket.org/amr_keleg/octave-geometry ) is a clone(fork) of the Geometry Package which is a part of the Octave Forge Project (http://octave.sourceforge.net/).
This fork adds new functions to the official Geometry Package as part of GSoC (Google Summer of Code) 2016.
The official Geometry Package can be found here:https://sourceforge.net/p/octave/geometry/ci/default/tree/
Added Functions
- polyjoin: Convert cell arrays of polygons into NaN delimited coulmn vectors.
- polysplit: Convert NaN separated polygon vectors to cell arrays of polygons.
- ispolycw: Check whether the polygon(s) has(have) clockwise orientation or counterclockwise orientation.
- poly2cw: Convert Polygons to clockwise contours(polygons).
- poly2ccw: Convert Polygons to counterclockwise contours(polygons).
- polybool: Perform Boolean Operations on polygons.
Valid Operations are: (intersection,and,&), (union,or,|,+,plus), (subtraction,minus,-), (exclusive-or,xor). - poly2fv: Convert Polygons into Faces and Vertices Representation.
Timeline
Community Bonding:
As mentioned in my proposal , I started working on the project 3 weeks before the official start of the GSoC program to compensate the three weeks that overlap with my final examinations.
I started my implementing the polysplit & polyjoin functions as they don’t depend on other functions.
These functions change the representation of the polygons from one form to another.
Since the polysplit & polyjoin functions don’t depend on Boost Geometry, they are implemented as .m files and placed in the inst/polygons2d/ directory.
First Coding Period:
During the first two weeks of this coding period, I continued the implementation of the polysplit/polyjoin functions adding help messages and regression tests.
Then, i worked on the first function that is implemented as a cc file which is the ispolycw function.
As all the package functions were implemented as .m files, i created a new directory src/ so that i can add .cc functions to the package.
The ispolycw function depends on calcualting the signed area of the polygon using the Boost Geometry function area(polygon).
The orientation of Self-intersecting polygons is defined as the respective orientation of the leftmost top point.If these points are co-linear , the signed area of the polygon is used to determine its orientation.
To compile the ispolycw function and generate .oct file that can be run by Octave, A new Makefile was added to the src/ directory.
The Makefile initially used the socket’s package implementation of the Makefile.
(https://sourceforge.net/p/octave/sockets/ci/default/tree/src/Makefile).
Two weeks after the start of the GSoC and we were already ahead of schedule. So we decided to start working on the polybool function as it is the main function of the whole project.
We decided to start by implementing the polybool function to support doing boolean operation between only two polygons.
Second Coding Period:
By the start of the second coding period, we changed the implementation of the polybool function to use the Boost Geometry multipolygon concept so that it can support applying boolean operations on multiple polygons with inner holes.
During the first three weeks the second coding period, simple benchmarks were used to test the polybool function.
And consequently multiple implementation bugs were fixed. One of these bugs was that a single inner ring was initially matched to multiple outer rings that surrounds this inner ring.
So a boolean array is currently used to ensure that each inner ring is matched to one and only one outer ring.
Then, i wrote two simple functions poly2cw & poly2ccw which are used to toggle the orientation of polygons and thus convert inner rings (holes) into outer ones and vice versa.
Then in the fourth week of the second coding period, i decided to make better understanding of Makefiles , how to use them to build only changed files, how to organize dependencies between targets and how to use variables.
Also, i tried to use the dissolve extension of the Boost Geometry to handle self intersecting polygons.
It took me a few days to manage to use it as the Boost Geometry version on my system (Ubuntu 14.04) was 1.54 while the dissolve extension is developed based on Boost Geometry libray of version 1.60
After that, i adapted the ClipperLib benchmarks to Octave so that we can compare my implementation of these functions to the ClipperLib / other programs performance.
By the end of July, i started working on the poly2fv function which is used to triangulate polygons so that they can be better visualized using the patch command.
This function returns a 2D matrix consisting of the triangles’ vertices and another 2D matrix representing the indexes of each triangle respectively.
For the first two weeks of August, i reviewed all the newly implemented package functions, added missing regression test , improved the help messages , added more input format checks , added warning messages when some boolean operations fail to be done mainly because of self-intersections that can’t be resolved.
Then during the last two weeks of the program, i had to learn how to use autotools so that i can use a configure script to test whether the Boost library is installed on the system, and check whether the dissolve function can be used to resolve self-intersecting polygons or not.
It was a great experience to manage to use the autotools to manage the generation of the final Makefile that is required to generate .oct files from the implemented .cc files.
Week | Task | Working hours / week |
22-4 / 29-4 | Understanding the organisation conventions – Prepare a complete plan for each function (Input/Output requirements – Optimal implementation based on memory/time metrics) | 20 hour/week |
30-4 / 6-5 | Implementing the polysplit function and testing it. | 20 hour/week |
7-5 / 13-5 | Implementing the polyjoin function and testing it. | 14 hour/week |
14-5 / 10-6 * | Finalize the implementation of the conversion functions (polysplit-polyjoin) | 7 hours /week |
11-6 / 19-6 | Implementing and testing the ispolycw function. * | 40 hours/week |
20-6 / 27-6 | Midterm Evaluation week | 40 hours/week |
25-6 / 1-7 | Working on the poly2cw and ispolycw scripts | 40 hours/week |
2-7 / 8-7 | Performing severe testing to all the implemented functions | 30 hours/week |
9-7 / 15-7 | Working on the polybool script. | 30 hours/week |
16-7 / 22-7 | 40 hours/week | |
23-7 / 29-7 | Implementing and testing the poly2fv function. | 40 hours/week |
30-7 / 5-8 | A 2 week buffer for finalizing the scripts , debugging them and writing the documentation. | 40 hours/week |
6-8 / 12-8 | 40 hours/week | |
13-8 / 23-8 | Tidying the code, writing tests, improving the documentation and submitting the code sample. | 40 hours/week |
* Final Examinations – Schedule isn’t announced yet – will inform the mentor whenever it is announced.
Conventions
All the newly added functions has the following set of conventions:
- Outer Rings of the polygon has a clockwise orientation, while Inner Rings has a counterclockwise orientation.
- Description of the polygons is represented by two arguments X and Y. Each argument can be represented using Cell Arrays or nan Delimited Vectors.
- The functions don’t require that the last point is the same as the first one.
Example: To represent a square as shown in figure:
— NaN Delimited Vectors:
x=[0 0 3 3 NaN 1 2 2 1];
y=[0 3 3 0 NaN 1 1 2 2];
— Cell Arrays:
x={[0 0 3 3],[1 2 2 1]};
y={[0 3 3 0],[1 1 2 2]};
Dependencies
polybool & poly2fv functions use the Boost Libraries.
The recommended version is 1.60
Getting Started
To test the updates to the Geometry package:
- Make sure you have Boost Libraries installed.
- Clone the package
hg clone https://amr_keleg@bitbucket.org/amr_keleg/octave-geometry
- Run ./bootstrap in the root directory of the package.
./bootstrap
- Create a tar file
tar -zcf geometry.tar.gz octave-geometry/
- Run Octave.
- In Octave Command Prompt, write
pkg install geometry.tar.gz
- Load the package
pkg load geometry
Tests
All the benchmarks where run on a Ubuntu 16.04 computer with Boost Library 1.60.
All the scripts can be found here:
https://drive.google.com/file/d/0B8W8ITHzO_gwWUE0YkZaT0hCRFE/view?usp=sharing
As my blog doesn’t support tables, Kindly check the Tests/Notes which can be found as a single pdf file here:
https://drive.google.com/file/d/0B8W8ITHzO_gwckVaandMYjU1Z0k/view?usp=sharing
Notes
-poly2fv depends on polytri library which isn’t developed to throw exceptions when it can’t triangulate polygons so sometimes poly2fv calls may cause Octave to crash.