Geometry Boost List: [geometry] Generating multi_polygon from sets of CW and CCW points

Subject: [geometry] Generating multi_polygon from sets of CW and CCW points
From: John Swensen (jpswensen_at_[hidden])
Date: 2016-06-20 12:57:45

For Google Summer of Code, I am mentoring a student to implement Matlab-compatible polygon function in GNU Octave. It has been going pretty well, but we have gotten to the point where we are starting to thing about efficiency with regards to both memory and computation. So, if any of you have suggestions on the following issues, I would appreciate it.

1) Matlab compatibility requires that the inputs to the polybool function is either a NaN-separated list of X values and Y values (or a cell array, which is kindof like and array of arrays}. CW sets of points are considered exterior rings and CCW sets of points are considered holes. The problem is that you can’t be guaranteed that there is any sort of correspondence between the CW and CCW sets of points. Is there an efficient way of converting these NaN-separated lists of points into their corresponding multi_polygon? Currently the student is essentially using the within algorithm to check the CCW sets of points against the CW sets of points, but I am hoping there is something quicker because this ends up being almost O(n*log(n)) for n polygons.

2) There is a way within the Octave C++ API to get a double pointer to the underlying data. We have been thinking about creating a legacy adapter to essentially identify the locations of the outer ring and inner rings within this array and then implement iterators to allow Boost to operate on the Octave data without having to copy it all. In your experience, would you think it just better to create a copy of the points in the Boost::Geometry native format and live with the performance and memory duplication?

John S.