The end: Good Bye GSoC

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:

  1. Outer Rings of the polygon has a clockwise orientation, while Inner Rings has a counterclockwise orientation.
  2. Description of the polygons is represented by two arguments X and Y. Each argument can be represented using Cell Arrays or nan Delimited Vectors.
  3. 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]};

2427028285-square


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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s