Thomas Klimpel wrote:

The links to "GTL Boostcon 2009 Presentation" in the documentation seem to be broken. The file "GTL_boostcon_draft03.htm" tries to forward to "GTL_boostcon_draft03_files/frame.htm", but the directory "GTL_boostcon_draft03_files" doesn't exist.

fixed

Frank Mori Hess wrote:

At

http://svn.boost.org/svn/boost/sandbox/gtl/doc/gtl_design_overview.htm

it says

"These concepts are listed with the names they are given in the library code and abbreviations used for them in this document in the table below."

but I don't see any such table on the page.

The table was removed because it wasn't needed. I have changed the document to no longer mention it. Luke

Hello, In the BoostCon paper you make a benchmark with, among others, the Boolean operations of CGAL, the Computational Geometry Algorithms Library. Which of the following two packages did you use: - http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Boolean_set_operations_... - http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Nef_2/Chapter_main.html I would be glad to check your claim that CGAL failed on one of your data sets. Are your benchmark testdrivers for the various libs under the boost svn, or can you post them, or send them in a private mail. Also I am wondering if I get it right, that you always operate on integer coordinates of bounded size? Do you give any guarantees on topolgical correctness when you snap round intersection points to grid points. best regards, andreas fabri

The attached file produces the problem that I'm having. It compiles fine using 1.36 thru 1.38. When I use 1.39 or trunk I get the following errors (gcc 4.2.3 on 64bit Fedora 9): <COMPILER_OUTPUT> /data/rosa2/build/boost/ins_boost_1_39_0_x86_64-unknown-linux-gnu/include/boost/preprocessor/iteration/detail/local.hpp: In member function 'void boost::interprocess::detail::Ctor1Arg<T, is_iterator, P0>::construct(void*, boost::interprocess::detail::false_) [with T = Dummy, bool is_iterator = false, P0 = Abcd]': /data/rosa2/build/boost/ins_boost_1_39_0_x86_64-unknown-linux-gnu/include/boost/preprocessor/iteration/detail/local.hpp:37: instantiated from 'void boost::interprocess::detail::Ctor1Arg<T, is_iterator, P0>::construct_n(void*, size_t, size_t&) [with T = Dummy, bool is_iterator = false, P0 = Abcd]' test2.cpp:18: instantiated from here /data/rosa2/build/boost/ins_boost_1_39_0_x86_64-unknown-linux-gnu/include/boost/preprocessor/iteration/detail/local.hpp:37: error: no matching function for call to 'Dummy::Dummy(const Abcd&)' test2.cpp:9: note: candidates are: Dummy::Dummy(Abcd&) test2.cpp:7: note: Dummy::Dummy(const Dummy&) </COMPILER_OUTPUT> The compile is looking for 'Dummy::Dummy(const Abcd&)' but that constructor parameter is actually non-const. If I change the constructor to take a const parameter then the compile succeeds (which, of course, isn't what I want). Note that the attached test code is boiled down from a more complicated case where I had multiple constructor parameters but was seeing the same effect. Obviously, something changed between 1.38 and 1.39. Thanks, --glenn

Ion Gaztañaga wrote:

That was a change in the forwarding code. Since perfect forwarding can't be achieved in C++03

Really? Can't you just overload all the possible const/non-const combinations? That would surely do forwarding of constness just fine. Of course, this is only feasible if you have few arguments. Also, why is this is the Boost.Polygon thread?

Thomas Klimpel wrote:

Until recently, I thought that the "perfect forwarding" problem was a technical defect of C++03, but then I read through the following:

Perfect forwarding works just fine (for a certain definition of fine) in C++03, it just requires an exponential number of overloads as the number of arguments increases and doesn't forward rvalue-ness but only types and const-ness, but since C++03 can't officially detect rvalue-ness anyway that's irrelevant.

Robert Jones wrote:

...

There's a terrific article about RVO and copy elision by Dave A at

http://cpp-next.com/

I don't really see how that article has a link to perfect forwarding.

Thomas Klimpel wrote:

The article explains "copy elision" and RVO, and hence explains why taking argument by value is closely related to rvalue-ness.

Saying that perfect forwarding doesn't work because the compiler can't do an optional copy elision anymore when you forward a value seems a bit far-fatched, especially since the pattern where you can exploit it is quite specific. (I've never found a reason to pass arguments by value outside of the assignment operator)

So it shows why the statement "..., but since C++03 can't officially detect rvalue-ness anyway that's irrelevant" is not the complete truth.

Notice the "officially" in the sentence.

Mathias Gaunard wrote:

Thomas Klimpel wrote:

...

The article explains "copy elision" and RVO, and hence explains why taking argument by value is closely related to rvalue-ness. Saying that perfect forwarding doesn't work because the compiler can't do an optional copy elision anymore when you forward a value seems a bit far-fatched, especially since the pattern where you can exploit it is quite specific. (I've never found a reason to pass arguments by value outside of the assignment operator)

While reviewing the polygon library in a debugger, I found myself stepping through copy-constructors of various iterator types quite often. So I remembered your claim "I've never found a reason to pass arguments by value outside of the assignment operator", because there are obviously good reasons to pass iterators by value. Regards, Thomas

I promised to come back on this:

My friend Barend Gehrels [Barend.Gehrels@geodan.nl] also has several countires for the geographic database that CGAL fails on. You might be able to get them from him quite easily.

The counties that CGAL fails on are counties where the exterioring ring is touching itself. CGAL reports that the polygon is not strictly simple, which is indeed the case. It is accepted by other libraries (Boost Polygon, GGL, Geos, SQL Server 2008, etc) but that does not mean that CGAL is wrong here. I added an image of this into our WIKI: http://trac.osgeo.org/ggl/wiki/CgalNotStrictlySimple Besides that, I added the performance benchmark results into our Wiki: http://trac.osgeo.org/ggl/wiki/Performance, including Boost Polygon, GGL, CGAL, Geos and other libraries. Regards, Barend

Frank Mori Hess wrote:

Maybe the above isn't relevant to Boost.Polygon though, as I'm having difficulty telling what the library does from the online docs. A full tutorial instead of just a list of commented example code files might help new users a lot. Also, I cant find any documentation on what the names of the library's header files are or what they each contain.

What the library does is provide the core set of algorithms a person would need to write a CAD application for working with 2D polygons. Perhaps you will find the presentation from boostcon illuminating, since the link in the doc There are a large number of header files. The header files in the boost/polygon directory are named in a way that should match what the documentation is talking about. For example, if you read a page about polygon_set_concept you will find a header file named polygon_set_concept.hpp. I have most of the algorithmic detail in the boost/polygon/detail directory. Many of the definitions of functions are inline in the header files under boost/polygon that declare the API, which is common practice in boost libraries. Reading the header files is not a good way to learn what the library does and how to use it. The intention was to document all the interfaces so that people would not need to dive into the header files to use the library. If you think it would be helpful I can add references to the relevant header files throughout the documentation. Thanks, Luke

Hello, When I compute union or intersection of two rectangles rotated by 45 degree that form an X, I don't necessarily get a 45 degree polygon, namely when the intersection point is not an integer. For example when one polygon has an edge 0,0 -- 10,10 and the other polygon has an edge -1,10 -- 9,9 then they intersect mathematically at 4.5,4.5 but as you snap to an integer, you get for example 5,5 Now -1,10 -- 5,5 is no longer a 45 degree edge. Isn't the fact that the set of 45 degree polygons is not closed under Boolean operations with snap rounding bothersome (even in practice). Best regards, andreas fabri

Simonson, Lucanus J wrote:

Andreas Fabri wrote:

...

Hello,

When I compute union or intersection of two rectangles rotated by 45 degree that form an X, I don't necessarily get a 45 degree polygon, namely when the intersection point is not an integer.

For example when one polygon has an edge 0,0 -- 10,10 and the other polygon has an edge -1,10 -- 9,9

then they intersect mathematically at 4.5,4.5 but as you snap to an integer, you get for example 5,5

Now -1,10 -- 5,5 is no longer a 45 degree edge.

Isn't the fact that the set of 45 degree polygons is not closed under Boolean operations with snap rounding bothersome (even in practice).

It would be very bothersome. I don't use snap rounding with 45 degree polygons, they are handled by a completely different implementation of the sweepline algorithm.

In the event that there is an non integer intersection in 45 degree polygon computation I modify the topology of the output to "clip off" corners that lands on a 0.5 value by inserting an edge of length 1. This preserves the 45 degree invariant and also approximates the correct result as closely as possible given the constraints of the integer grid. Details of this and an example diagram are shown in slide 8 of the boostcon presentation (linked to in the docs) entitled "Details of 45-degree Booleans".

Some discussion of this behavior might be warrented in the documentation for Polygon 45 Set.

A user can easily avoid non-integer intersection artifacts with 45 data by multiplying all cordinate values by two. The output polygon vertices will then be even-even or odd-odd coordinate pairs (such data cannot give rise to non-integer intersection) and can be fed back into the algorithm as many times as desired.

Well, if you use an int, you can't multiply that often with 2 without getting an overflow, but as you write in the paper, that is not a problem, because you can use arbitrary precision integer types like GMP. But doesn't that make it slow in practice? Will it appear in practice, that is do you have situations in your VLSI related software that does iterations of Boolean operations? So when you multiply the coordianted of polygon P by two, and feed it back the user has to associate the scale factor to P, in order to also scale a not-yet scaled polygon Q, before applying a Boolean operation on P and Q. Not a big deal, but wouldn't it make sense that the scale factor becomes part of your package? best regards, andreas

Thanks, Luke _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Hi Luke, thank you for your explanations for the 45 degree case. You have a nice solution. I guess for the general case I have to read the BoostCon paper first. andreas Simonson, Lucanus J wrote:

Andreas Fabri wrote:

...

...

A user can easily avoid non-integer intersection artifacts with 45 data by multiplying all cordinate values by two. The output polygon vertices will then be even-even or odd-odd coordinate pairs (such data cannot give rise to non-integer intersection) and can be fed back into the algorithm as many times as desired.

Well, if you use an int, you can't multiply that often with 2 without getting an overflow, but as you write in the paper, that is not a problem, because you can use arbitrary precision integer types like GMP. But doesn't that make it slow in practice? Will it appear in practice, that is do you have situations in your VLSI related software that does iterations of Boolean operations?

You only have to scale all inputs by two then any sequence of boolean operations is safe from non-integer intersection. This may not be immediately obvious, but as long as the end points of two segments are both even coordinates or both odd coordinates their intersection point will allways be either both even or both odd. A non-integer intersection between 45-degree edges only happens when and "even" edge is intersected with and "odd" edge. Booleans cannot introduce odd edges, so arbitrarily long sequences of booleans can be performed without the need for scaling between each.

...

So when you multiply the coordianted of polygon P by two, and feed it back the user has to associate the scale factor to P, in order to also scale a not-yet scaled polygon Q, before applying a Boolean operation on P and Q. Not a big deal, but wouldn't it make sense that the scale factor becomes part of your package?

I never scale and give the user back scaled coordinates as the result of a boolean. I do provide an API that they can use to scale if they desire.

Avoiding problems with non-integer intersections in 45-booleans is a part of the package, I scale up by two and down by two for every 45 degree boolean op where non-integer intersection is detected. I use 64 bit integer if the coordinate was 32 bit integer to avoid overflow. It is transparent to the user except for the clipped off corners that may be present in the result. I also provide access to a set of 1x1 unit squares that describe the locations where non-integer intersections occured in the boolean to allow the user to know how much and where precision forced approximations. These error rectangles accumulate when booleans are chained so that they need only be checked in the end result and not in each intermediate result. I'm adding to my todo to improve documentation of this feature.

As to performance, the 45-degree boolean is roughly 2X slower than manhattan if there are no non-integer intersections and if there are non-integer intersection they are about 8X slower because I have to do quite a bit of extra work scaling, converting to 64 bit and clipping off corners of output polygons. Since I can't know a-priori whether there will be non-integer intersections I optimistically run the boolean, throw an exception when the first non-integer intersection is detected, catch it myself and handle it by scaling up and clipping odd corners when scaling down. The algorithm is exception safe because I use RAII for all memory management and we've validated it with valgrind.

You ask some good questions about the 45 booleans. It took me quite a while to figure out these issues. Since the specialized 45-degree algorithm can be so much faster than the general algorithms and it is an important special case for VSLI we were very motivated to solve them. Right now the 45 degree algorithm is used in full scale production on layout data and are stable, generating no issues since the code for handling non-integer intersections was validated.

Thanks, Luke _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Simonson, Lucanus J wrote:

Andreas Fabri wrote:

...

Hi Luke,

thank you for your explanations for the 45 degree case. You have a nice solution. I guess for the general case I have to read the BoostCon paper first.

andreas

Thank you for saying so.

As requested, I haved added a test case for which CGAL fails to subversion

https://svn.boost.org/svn/boost/sandbox/gtl/forcgal.cpp

Hi Luke, Using CGAL with just floating point arithmetic is rather nonsense, especially when you test robustness. I guess I need a recent version of boost, plus sandbox/gtl, in order that it compiles? Best regards, andreas

I appologize that the test case is rather large. Expected output is:

$$$$$$$$$$$$ RANDOM TEST $$$$$$$$$$$$$$$$ Square BOXX size: 6000 ************************* CGAL error: precondition violation! Expr: compare_xy(cv1.right(), p) == LARGER && compare_xy(cv2.right(), p) == LARGER File: /nfs/ltdn/disks/tcad_lmg_db_exchange_01/CGAL-3.3.1/include/CGAL/Arr_segment_traits_2.h Line: 609 Explanation: terminate called after throwing an instance of 'CGAL::Precondition_exception' what(): CGAL ERROR: precondition violation! Expr: compare_xy(cv1.right(), p) == LARGER && compare_xy(cv2.right(), p) == LARGER File: /nfs/ltdn/disks/tcad_lmg_db_exchange_01/CGAL-3.3.1/include/CGAL/Arr_segment_traits_2.h Line: 609 Abort

This assertion in CGAL code looked to me like some condition that should be ensured by CGAL itself and is an internal error rather than a precondition violation. My interpretation was that the wrong exception type was used. I could be wrong, however, and if you find there was in fact something wrong with the polygon I produced I will eagerly fix my algorithm. My intention was to implement a booleans algorithm with the weakest possible preconditions and the strongest possible postconditions.

Thanks, Luke _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Simonson, Lucanus J wrote:

Andreas Fabri wrote:

...

Simonson, Lucanus J wrote:

...

Andreas Fabri wrote:

...

Hi Luke,

thank you for your explanations for the 45 degree case. You have a nice solution. I guess for the general case I have to read the BoostCon paper first.

andreas

Thank you for saying so.

As requested, I haved added a test case for which CGAL fails to subversion

https://svn.boost.org/svn/boost/sandbox/gtl/forcgal.cpp

Hi Luke,

Using CGAL with just floating point arithmetic is rather nonsense, especially when you test robustness.

I guess I need a recent version of boost, plus sandbox/gtl, in order that it compiles?

Best regards,

andreas

I did try CGAL with other kernel types and found that the same exception was thrown. I probably should have mentioned that. I used boost 1.35 with CGAL 3.3.1 and sandbox gtl. I'm working on getting the dependency on gmp straightened out to try the other kernels again.

I have just re-verified that I get the same exception with the Exact_predicates_inexact_constructions kernel. I should have done that first and uploaded code using a robust kernel to avoid confusion. //definition I'm currently using for Kernel #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel; The test case was not designed to be numerically difficult, all edges are short and all input coordinates are on the integer grid. I exercised CGAL with floating point arithmetic to report its performance as optimistically as possible. It fails for apparently non-numerical robustness reasons, otherwise I would have happily benchmarked the fastest available kernel which allowed it to succeed. I have debugged into the issue futher and it appears that the precondition being checked is the winding direction of a hole. My algorithm can't output a hole with the wrong winding direction. Regardless, I added my own check on each hole before submitting them to CGAL and they all pass my check for winding orientation. The algorithm for winding orientation must be incorrect. Specifically I note that the invariant being violated is an assumption made by the winding algorithm about its own state and not about the polygon itself: --- from check orientation functor --- Comparison_result res_from = cmp_y_at_x_right(*from_left_most, *tmp_from_left_most, left_most_v); Comparison_result res_to = cmp_y_at_x_right(*into_left_most, *tmp_into_left_most, left_most_v); ---- from cmp_y_at_x_right functor ---- CGAL_precondition (compare_xy(cv1.right(), p) == LARGER && compare_xy(cv2.right(), p) == LARGER); The algorithm is taking the two x-monotone curves at the left most point and trying to use their relative angle and ordering to figure out the winding orientation, however apparently they fail the x-monotone invariant check performed in the cmp_y_at_x_right functor. This is hardly the fault of the input polygon and indicates some flaw in the way it was divided into x-monotone curves. At this point I'd like to hand debugging over to CGAL authors. Again, sorry for the confusion about robust kernels, Luke

Phil Endecott wrote:

Dear Luke & others,

Congratulations on getting this library as far as a review. I feared that the scope of the subject might make it impossible for anyone to ever get this far. Perhaps we have Luke's employer to thank for this.

Yes, I have thanked my employer. It has been years of work and I feel very fortuante to have been allowed the opportunity to get this far.

I hope to have time to try out the library with at least a couple of real-world examples. I'll describe the problems that I have in mind now and update later with my experiences.

Marker Merging: I have lots of small square markers indicating search results on a map. If the map is zoomed out so that the whole planet is visible and you search for something common like "lake", it will attempt to draw many thousands of overlapping markers which is slow. Since the markers are just squares of solid colour, I would like to merge them into a single polygon-set and plot that. Speed is the main concern. It it also interesting to consider what would happen if the markers were circles. Here's an example of the sort of output I need: http://chezphil.org/tmp/six_thousand_lakes.jpeg

This will be blazingly fast with my specialized manhattan implementation. The general implementation will switch to the manhattan algorithm dynamically if the data is manhattan, but if you use the manhattan types/concepts it selects the correct algorithm at compile time.

Border Simplification: I have data describing state outlines as polygon-sets. I want to pre-process that into a format that permits rapid rendering; specifically, I want to generate multi-resolution versions with smoothing and interpolation as necessary. I also want to reduce it from polygons with common edges to polylines, so that each border is plotted once rather than twice. This is something that happens off-line as part of a build process, so speed is much less important than ease of coding. Example output: http://chezphil.org/tmp/state_borders.jpeg (yes, it's an iPhone app... hey, we all have to pay the rent somehow...)

I don't have a smooth algorithm because the definition is sort of fuzzy. There are many smoothing algorithms to choose from. It is also straightforward to implement oneself, unlike sweepline. To eliminate borders that would be plotted twice you can easily find duplicate edges by sorting and discovering duplicates as neighbors. From there assign unique ids to each polygon and disable its edges if there is a polygon with greater id that has the same edge. This disables common borders, is n log n, and shouldn't be hard to implement based upon stl and my library. I define less than on point_data<T>, which is about all you need. I'd love to have my code running on an iphone. I pulled out iostream deps to make it more friendly to compile targeting small form factors. If you implement these examples I'd be happy to add them to the docs and put a thank you in there for you.

p.s. has anyone worked out where this thread has gone on gmane.org?

What is gmane.org? Thanks, Luke

Phil Endecott wrote:

Dear All,

I've just had a quick attempt at writing a Boost.Polygon traits specialisation for my rectangle type, and my 10 lines of code produce 105 warnings that come to 54k of output. This is with g++ 4.1.2. That makes it pretty much unusable for me. Luke, please fix this and re-submit. I vote to reject the library if this is not done. I've had a quick look at one of the warnings and it looks easily fixable; interval_concept.hpp:84 just remove "ptr".

Regards, Phil.

I'm using ptr as SFINAE guard. I can move SFINAE checks back to the return type and add the MSVC8 workaround. I'll see what I can do about your warnings in 4.1.2. Luke

Steven Watanabe wrote:

AMDG

Simonson, Lucanus J wrote:

...

Phil Endecott wrote:

...

Dear All,

I've just had a quick attempt at writing a Boost.Polygon traits specialisation for my rectangle type, and my 10 lines of code produce 105 warnings that come to 54k of output. This is with g++ 4.1.2. That makes it pretty much unusable for me. Luke, please fix this and re-submit. I vote to reject the library if this is not done. I've had a quick look at one of the warnings and it looks easily fixable; interval_concept.hpp:84 just remove "ptr".

Regards, Phil.

I'm using ptr as SFINAE guard. I can move SFINAE checks back to the return type and add the MSVC8 workaround. I'll see what I can do about your warnings in 4.1.2.

You don't need to give the parameter a name. typename enable_if<...>::type* = 0 works just fine.

Sneaky. I've fixed all the gcc 4.1.2 warnings, which include the long double warnings you was in 3.4.4. I also fixed the tabs since they were on the same lines as the *ptr = 0 which was added in the MSVC8 IDE. 4.1.2 should compile without warnings now. Thanks, Luke

Phil Endecott wrote:

Simonson, Lucanus J wrote:

...

4.1.2 should compile without warnings now.

The two lines:

typedef polygon_90_set_data<screen_coord_t> markers_t; markers_t markers;

give me 11 kbytes of warnings with gcc 4.1.2.

No doubt this can also be fixed quickly. Would the review manager like to comment on the extent to which Luke may change the library as the review progresses? I recall this being discouraged on one previous occasion: "The library being reviewed is the one submitted". Allowing changes may require that the review manager has to consider whether reviewers might have had different opinions if they had waited for a few days before doing their investigations.

Regards, Phil.

Phil, Thanks for putting in the time to review my library. I've updated the polygon.tar.gz archive to include the latest changes I have checked into the sandbox. These fix the warnings for gcc 3.4.4 and gcc 4.1.2. (I haven't yet fixed all of the MSVC warngings.) Please update your local copy from subversion or download the new tarball and retry. Your example compiles with no warnings for me in gcc 4.1.2 #define BOOST_POLYGON_NO_DEPS #include "polygon.hpp" typedef int screen_coord_t; typedef boost::polygon::polygon_90_set_data<screen_coord_t> markers_t; markers_t markers; int main() {} Compile line: /usr/intel/pkgs/gcc/4.1.2/bin/g++ -Wall phil.cpp -I /usr/intel/pkgs/boost/1.39.0/include/boost-1_39/ Thanks, Luke

Joachim Faulhaber wrote:

with msvc-9 I get a lot of warnings from expressions like

bool bit2 = atr_ & 4; or bool bit2 = (bool)(atr_ & 4);

e.g. boost\polygon\transform.hpp(256) : warning C4800: 'int' : forcing value to bool 'true' or 'false' (performance warning)

A big amount of these can be silenced by the simple replacement

bool bit2 = (atr_ & 4) != 0;

That's a ridiculous warning that we always disable. I've never compared the assembly produced by various compilers, but I'd be wary of the effect on optimization between the two without proof that there is none. BTW, Lucanus, the C-style cast could be eliminated if you used direct-initialization: bool bit2(atr_ & 4); _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Markus Werle wrote:

I think it would make sense to announce formal reviews in the (RSS feeded) News section of http://www.boost.org.

Could you please be so kind and add this announcement there?

The Notes for Review Managers (http://www.boost.org/community/reviews.html) just says:

Posts a notice of the review schedule on both the regular boost mailing list and the boost-announce mailing list.

He probably just forgot to send the notice to the boost-announce mailing list. I guess the boost-announce mailing list automatically adds the messages to the (Rss feeded) News section of http://www.boost.org. Regards, Thomas

Fernando Cacciola wrote:

In fact, I don't even know if that's "allowed" since the "News section" I see lists only releases, not currently ongoing reviews, or such.

I'm pretty sure it used to list starting and conclusion of reviews. Maybe it was removed purposely?

Paul A. Bristow wrote:

But I did note that the examples lack copyright and Boost license header.

Fixed I also added documentation for the APIs of the polygon 45 set data that provide feedback to the user on how many non-integer intersections occurred during boolean operations to produce that polygon set and the regions that error is bounded to. Thanks, Luke

Thomas Klimpel wrote:

...

- What is your evaluation of the documentation?

Don't know yet. I have a bit the impression that I'm supposed to read the sample programs and abstract myself from this what it does. But it somehow seems to work, so I will report my observations in the same style:

Thank you for your careful reading of the examples and some of their associated documentation. Are you suggesting that I should add more explanation (in the form of comments) to the example code?

- Slight inconsistency of Contents menu for "Polygon 45 Concept" and "Property Merge 45"

fixed

- point_usage.cpp: assert(gtl::euclidean_distance(pt, pt2) == 10.0f); is not a good idea, because floating point comparison will not work out

Floating point comparision does work and the assert is not triggered when the code is run. All exact comparsions performed in the example code with floating point literals are safe because I contrived the input parameters so that the floating opint calculations are able to produce exact and not approximate results.

- gtl_polygon_usage.cpp: assert(gtl::extents(rect, poly)); //get bounding box of poly

I see nothing wrong with this line.

- custom_polygon.cpp: static inline unsigned int size(const CPolygon& t) {

Technically this line should return std::size_t, is that what you are pointing out?

- connectivity_extraction_usage.cpp: assert(ce.insert(test_data[i]) == i);

Not sure what you are calling out. The id assigned by insert starts at zero and increments, meaning it happens to be equal to i in my example code.

//Now you know how to use the connectivity extraction algorithm //to extract the connectivity graph for overlapping geometry

Not sure what you are calling out.

- property_merge_usage.cpp: //Now you know how to use the manhattan and arbitrary angle property //merge algorithms to perform map overlay on n layers of input geometry

Not sure what you are calling out.

- gtl_property_merge_90.htm: std::map<std::set<property_type>, polygon_set_data<coordiante_type> > std::map<std::vector<property_type>, polygon_set_data<coordiante_type> >

fixed

coordiante_type should be coordinate_type, but what's the meaning of "polygon_set_data<coordinate_type>"?

polygon_set_data<coordinate_type> is a class defined in the library documented in the polygon set concept page. It is storage for geometry with the assoicated set of properties in the result of the property merge algorithm. Recall that property merge is map-overlay. The polygon_set_data<coordinate_type> is the polygons that are associated with the overlay of several properties which constitute the key of the map that stores the result of the map overlay.

void merge(result_tyep& result)

fixed Thanks again, Luke

Thomas Klimpel wrote:

Simonson, Lucanus J wrote:

...

Thank you for your careful reading of the examples and some of their associated documentation. Are you suggesting that I should add more explanation (in the form of comments) to the example code?

No, it's more something along the line: "I want to read an introduction/tutorial for the library, so what am I supposed to do?" I figured out that the examples are meant to be some sort of tutorial. I worked quite well for me, only the last two examples were a bit too difficult, so I tried to read the associated documentation for them.

Apart from that, I was just looking for an excuse to write my observations without further clarifications.

...

...

- point_usage.cpp: assert(gtl::euclidean_distance(pt, pt2) == 10.0f); is not a good idea, because floating point comparison will not work out Floating point comparision does work and the assert is not triggered when the code is run.

I can't believe that there is no C++ compiler out there that will trigger "assert(sqrt(100.0f) == 10.0f);" for suitably chosen compiler flags.

...

...

- gtl_polygon_usage.cpp: assert(gtl::extents(rect, poly)); //get bounding box of poly

I see nothing wrong with this line.

I guess "gtl::extents(rect, poly)" is meant to set rect to the bounding box of poly. So it's probably not a good idea to wrap the call inside an assert.

...

...

- custom_polygon.cpp: static inline unsigned int size(const CPolygon& t) {

Technically this line should return std::size_t, is that what you are pointing out?

Yes, because "unsigned int" is quite unexpected as return type here. Just returning std::size_t will be more smooth to read for the newcomer, even if the library can also accept unsigned int as return type.

...

...

- connectivity_extraction_usage.cpp: assert(ce.insert(test_data[i]) == i);

Not sure what you are calling out. The id assigned by insert starts at zero and increments, meaning it happens to be equal to i in my example code.

I don't think that the call should be wrapped inside an assert.

...

...

//Now you know how to use the connectivity extraction algorithm //to extract the connectivity graph for overlapping geometry

Not sure what you are calling out.

...

- property_merge_usage.cpp: //Now you know how to use the manhattan and arbitrary angle property //merge algorithms to perform map overlay on n layers of input geometry

Not sure what you are calling out.

The statement "Now you know how to use the ..." wasn't true for me..

...

...

coordiante_type should be coordinate_type, but what's the meaning of "polygon_set_data<coordinate_type>"?

polygon_set_data<coordinate_type> is a class defined in the library documented in the polygon set concept page.

I found it. Thanks.

- gtl_property_merge_45.htm still has some typos in it: property_merge_45(const property_merge_90& that) should probably be property_merge_45(const property_merge_45& that)

The context menu for "Property Merge 45" is still inconsistent, because of "<p> </p>" in line 42, and because of " <li><a href="gtl_property_merge_90.htm">Property Merge_90</a></li> <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> " instead of "".

All other *.htm files have "<li><a href="gtl_property_merge_45.htm">Property Merge_45</a></li>" instead of "<li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>", which should probably also be fixed.

Regards, Thomas _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Michael Fawcett wrote:

Shows both operator| and operator+ as being the same thing - a boolean OR between two polygons.

If there is some precedent for this, I accept, but if there isn't, I would much rather prefer a single way of doing things. I suggest dropping operator+ and operator*. Their counterparts make much more sense to me.

The minus operation is "-" and the xor operation is "^", so neither arithmetic operators nor logic operators cover all common operations. But I agree that the logic operators are more intuitive than the arithmetic operators. And "A-B" should be equivalent to "A & not(B)", so the logic operators should be sufficient, at least in theory.

Mathias Gaunard wrote:

I wonder how difficult it would be to extend the system so that it could work with statically-sized polygons. (the library only provides rectangles, basically polygons 90 which a static size of 4) I'm thinking of triangles in particular. Also, could algorithms like triangulation eventually become part of the library?

You could make a polygon_traits specialization for your own triangle class, but not a polygon_mutable_traits. This would allow the library to view your triangle type as a read-only polygon type. Triangle concept and related algorithms such as triangulation could eventually become part of the library, I would welcome such as community contributions.

Still in the static vs dynamic argument, it appears points implement by default the static coordinate lookup (the x() and y() functions) in terms of the dynamic one (the get(orientation_2d) function). Shouldn't it be the other way around?

The assumption here is that when the dynamic one is instantiated and inlined by the compiler constant propigation will allow it to optimize it away producing an interface without runtime overhead.

The documentation says euclidean_distance was named so instead of distance to avoid ambiguity with std::distance. Isn't that problem simply solved by qualifying the call? Or maybe I'm missing something?

No, the thing you are missing is ADL. The existence of distance() in my own namespace causes ADL lookup to do the wrong thing when instantiating stl templates that use std::distance() on iterators in older version of the standard library.

Personally, I tend to prefer functions that return results rather than those that take some input and modify it, since the latter require the objects to model the mutable variant of the concept, and mutation makes code more complex to reason about by undermining referential transparency and equational reasoning. (part of that sentence was copy/pasted ;)). Couldn't a function like "center", for example, instead of taking a point to modify, directly return some kind of simplistic expression template, then perform the evaluation when a conversion to T is requested, using T as an output type?

I agree with you about equational reasoning. Center used to return point_data. I changed it to be consistent with other interfaces and allow user defined point types. As to your suggestion, I can't implement a generic assignment operator or copy constructor for T, so what you are suggesting would not eliminate the temp copy I'm trying to avoid by passing many outputs by reference as the first argument. In the case of a point, returning an object that casts to arbitrary point type is reasonable because the temp copys are cheap and easy for the compiler to optimize away. In the case of polygons or collections of polygons this is not the case.

Finally, about the operator overloading for set operations, I would like to be able to avoid pushing the namespace in the global one if possible. I think it would be nice to have a "ref" function or something that would make objects just behave like a reference to the original object but within the right namespace so that the operators get picked up by ADL. Functions that would return expression templates like discussed above could also make their return type in the right namespace so that it gets picked up by ADL too.

I can't say I prefer ref(A) | ref(B) to A | B Usually I pull the operators namespace into the local scope of a function where they are used and not the global scope. Pulling them into a scope that defines other operators can actually cause ADL problems that prevent them from being found since ADL ignores using directives. The operators namespace is a recent addition to the library. It was Steven Watanabe's suggestion during the pre-review to add the operators namespace, though I'd been considering it for some time. Previously the operators were defined in the boost::polygon namespace, and to use them you either had to have boost::polygon object find them through ADL or pull the whole boost::polygon namespace in. Arguably, if a person is using the operators in a scope it is reasonable for them to use the using directive. Thanks, Luke

Mathias Gaunard wrote:

Finally, about the operator overloading for set operations, I would like to be able to avoid pushing the namespace in the global one if possible. I think it would be nice to have a "ref" function or something that would make objects just behave like a reference to the original object but within the right namespace so that the operators get picked up by ADL. Functions that would return expression templates like discussed above could also make their return type in the right namespace so that it gets picked up by ADL too.

I almost forgot, there is actually a better answer to your question. The operators in the operators namespace are an optional feature of the library. You can instead use the polygon_set_data objects to perform explicit conversions and use the member operators of the polygon_set_data classes. polygon_set_data<int>(some_polygon) | polygon_set_data<int>(some_rectangle); Since operator| is in this case a member function it is found first though ADL. Luke

Mathias Gaunard wrote:

Simonson, Lucanus J wrote:

...

I almost forgot, there is actually a better answer to your question. The operators in the operators namespace are an optional feature of the library. You can instead use the polygon_set_data objects to perform explicit conversions and use the member operators of the polygon_set_data classes.

polygon_set_data<int>(some_polygon) | polygon_set_data<int>(some_rectangle);

Since operator| is in this case a member function it is found first though ADL.

Except this is going to copy some_polygon and some_rectangle to initialize the polygon_set_data, right?

Yes, however, polygon_set_data encapsulates the data structure that is the input to my sweep line algorithm. It needs to be copied to that format anyway so that I can sort and scan it. The generic operators are implemented by performing the conversion and using the member operator of the polygon_data_data classes. There is no way to run a sweepline algorithm on a polygon without sorting its edges into the order they are to be scanned, and there's no way to sort a polygon's edges without converting it. Luke

Steven Watanabe wrote:

I ran the test with most of the compilers I have available. I'm getting a lot of compiler warnings from msvc-9.0express, msvc-8.0express, and gcc-3.4.4. gcc-4.2.3, gcc-4.3.0, and gcc-mingw-4.4.1 are fine.

I'm aware of the warnings in MSVC. How important is it to fix these warnings? What is boost policy and precident? I am well aware that I will catch no end of grief from users if they get a slew of warnings. I have no internal MSVC users, but I've spent days chasing warnings for EDG and gcc. ...

Did you not #include <cstddef>? ... 1) you should use std::floor. 2) The is no #include <cstdlib> in isotropy.h.

fixed Thanks, Luke

On Sat, Aug 29, 2009 at 10:08 PM, Steven Watanabe<watanabesj@gmail.com> wrote:

AMDG

Simonson, Lucanus J wrote:

...

Steven Watanabe wrote:

...

I ran the test with most of the compilers I have available. I'm getting a lot of compiler warnings from msvc-9.0express, msvc-8.0express, and gcc-3.4.4. gcc-4.2.3, gcc-4.3.0, and gcc-mingw-4.4.1 are fine.

I'm aware of the warnings in MSVC.  How important is it to fix these warnings?

Well, msvc is pretty widely used.  I wouldn't say that you have to fix them, but I would strongly encourage it. gcc 3.4 is sufficiently old, that I wouldn't worry about it much.

...

What is boost policy and precident?

Boost has no official policy.  Some libraries are warning-free. Others are fairly noisy, although the older libraries are slowly getting cleaned up as users complain.

For note, all the libraries that I use in Boost (only about 15 to 20 or so) are warningless, so there is huge precedent.

On Sat, Aug 29, 2009 at 10:27 PM, Steven Watanabe<watanabesj@gmail.com> wrote:

AMDG

OvermindDL1 wrote:

...

For note, all the libraries that I use in Boost (only about 15 to 20 or so) are warningless, so there is huge precedent.

Or at least mostly warningless. Some warnings still slip through the cracks. https://svn.boost.org/trac/boost/ticket/3350

.> <.< Yes yes, but I have not used that yet. ;-) I would have complained when I did though. :p

Simonson, Lucanus J wrote:

Steven Watanabe wrote:

...

isotropy.hpp:308 What does y_c_edist mean, and why are you including a constant in the gtl_and for euclidean_distance?

This is a compiler workaround for MSVC8. There are a large number of them, unfortuantely. It is named with a mangling scheme related to the concept and function name that uses it. MSVC8 has two different code paths for instantiating templates and applying SFINAE. The one where it recognizes that it has seen a subtemplate before is incorrect and I used these constant types that are unique to each function to force MSVC8 to SFINAE correctly. I could perhaps put a

//MSVC8 workaround

on each one so that it doesn't cause too much confusion.

(Caveat: I'm only responding to what I read here: I haven't looked at the code in question. I may be way off the mark.) How about introducing a macro taking a constant argument, that evaluates to the supplied constant, plus required punctuation, for MSVC8 and to nothing for other compilers? That would make the code self documenting and eliminate any #ifdef's where used. BOOST_POLYGON_MSVC8_SFINAE_WORKAROUND? _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Simonson, Lucanus J

Stewart, Robert wrote:

...

Simonson, Lucanus J wrote:

...

Steven Watanabe wrote:

...

isotropy.hpp:308 What does y_c_edist mean, and why are you including a constant in the gtl_and for euclidean_distance?

This is a compiler workaround for MSVC8. There are a large number of them, unfortuantely. It is named with a mangling scheme related to the concept and function name that uses it. MSVC8 has two different code paths for instantiating templates and applying SFINAE. The one where it recognizes that it has seen a subtemplate before is incorrect and I used these constant types that are unique to each function to force MSVC8 to SFINAE correctly. I could perhaps put a

//MSVC8 workaround

on each one so that it doesn't cause too much confusion.

(Caveat: I'm only responding to what I read here: I haven't looked at the code in question. I may be way off the mark.)

How about introducing a macro taking a constant argument, that evaluates to the supplied constant, plus required punctuation, for MSVC8 and to nothing for other compilers? That would make the code self documenting and eliminate any #ifdef's where used.

BOOST_POLYGON_MSVC8_SFINAE_WORKAROUND?

The constant needs to be a unique type in each instance that the workaround is used. Also, there are no ifdefs used for this workaround because the code is legal in all compilers.

Fair enough. However, allow me two points. First, the unique type can be produced from the constant supplied to the macro. Second, one day you might actually drop support for MSVC8 and removing the invocation of a macro that you can search for easily, would make quick work of reverting to the syntax you wanted all along. Thus, the macro can inject the extra type for MSVC8 only, leaving other compilers with the simpler code, which probably means reduced compilation time; the macro documents that the extra type is for MSVC8 only; and you have an easier way to remove the noise later. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Thomas Klimpel wrote:

...

- What is your evaluation of the documentation?

I actually like it, especially now where I read through it once (At least now I have the impression that I understood everything. However, I know from experience that such an impression is deceptive). I noticed that "gtl_point_3d_concept.htm" is not linked to the rest of the documentation, could this be intentional? (It seems like a point_3d concept is not required for a polygon library.)

Yes, it is intentional. I narrowed the scope of the library to explictly 2d polygon focus. The point 3d concept and related code such as 3d axis-transformation are now undocumented features. They are coupled to the 2d transformation system pretty strongly, so I left them in rather than removing the code. They may prove useful, and they do demonstrate how the type system can be extended to 3d.

I gave up writing down all typos explicitly. Instead, I fixed my local version and created a patch (-> see attachment).

Great. That's a big help.

The Polygon Set Concept documentation (and others) says "Will scan and eliminate overlaps" from time to time, but doesn't describe how overlaps are resolved. Common options are the even-odd rule and the non-zero winding number rule, but I guess there exist even more sensible options than that. Is there a way to control how overlaps are resolved and which resolution strategy is used by default?

I should rephrase that to state will scan to merge overlaps in an implicit OR operation. This is because the OR operation is implemented as an accumlulate and is as fast as appending the right hand side data to a vector on the left hand side. The data structure is then in a "dirty" state where there may be regions of overlap between input polygons. The self_xor and self_intersect only produce useful output when the data structure is in this "dirty" state because they pertain to these regions of self overlap within a polygon set. When you get polygons out of a polygon set I need to merge the data to produce output polygons. If you were to call self_intersect after gettting those polygons out you would get the null set. This is potentially confusing. The accumulate behavior of the += operator is important because it is very easy for a person to write a loop like: foreach polygon in input_stream { polygon_set += polygon; } which would be n^2 log n, but is n log n with the optimization. On the other hand, people should be aware that calling get_polygons is potentially an expensive operation if the polygon set is in a "dirty" state. I'll probably have to improve the documentation with regard to these specific issues somewhat substantially....

The "Property Merge" seems to describe a substitute for a "reduce" operation (in the sense of the "map-reduce paradigm"). The result type "std::map<std::set<property_type>, polygon_set_data<coordinate_type> >" is probably the substitute for commutative "reduce" operations and "std::map<std::vector<property_type>, polygon_set_data<coordinate_type> >" the substitute for non-commutative "reduce" operations. I see that I can implement any desired "reduce" operation, by first running the "Property Merge" algorithm, and then applying the reduce operations to the resulting sets, and then just putting all result polygons from sets with identical "reduce" result in the same set (which give the correct result since the polygons sets don't overlap each other). But I wonder whether it would be possible to directly offer "reduce" operations, and whether this could potentially have performance benefits.

You are right that it is possible. You could do exactly what you suggest by implementing the appropriate output functor for the sweepline algorithm to evaluate the boolean logic you want to produce result as a single polygon set directly rather than collecting all the pieces up in the output from property merge and merging them with another pass of sweepline. I've thought about this a fair ammount and while it is very interesting I think there is not much performance benefit to be had. Assuming optimal sweepline we would still not be better off to do it in one pass instead of one per boolean op of the desired boolean logic because the result of an intersect or and not operation usually reduces data volume and we would prefer to do those first if possible. I would expect (A & B) | (C - D) to be slower if executed as one sweep over all the edges in A, B, C and D than as three since we can expect A&B and C-D to reduce the data volume that goes into the OR operation. Also the peak memory required for sweeping all of them at once is greater than as separate passes for each op. One final consideration is that it is fairly rare for people to form multi-op expressions of simple booleans in a single line (such that expression templates could kick in), so even if there were a performance win we would be optimizing for the uncommon case. There is plenty left to do to make a single op run faster, I have a list, actually. Thanks Thomas, I'm glad to hear you liked the documentation, Luke

Simonson, Lucanus J wrote:

Steven Watanabe wrote:

...

interval_concept.hpp:205-206,219-220,231-232,246-247, maybe more Please use static_cast, instead of a C-style cast.

Many more. I use c-style casts for coordinate type conversion pretty much uniformly. How big of an issue is this? It would take a while to hunt them all down.

You'll probably get complaints from gcc users about the warnings it causes (with -Wold-style-cast). John Bytheway

Sebastian Redl wrote:

...

- What is your evaluation of the potential usefulness of the library? The limitation that polygon operations must basically be integral (I'm not sure what effect the snap-rounding distance of one integer unit has in concrete cases, but when that integer unit is a kilometer, it sounds like it would introduce significant inaccuracies) means that my particular use case is somewhat limited - I have to work with 3rd party geometry that uses floating point values. If this is a misunderstanding on my part, the library would be extremely useful to me. Even as it is, I can use the point and rectangle functions to replace quite a bit of my own code.

You can scale your data to minimize inaccuracy. In VSLI CAD most users like to see units in micron as a floating point value, but the integer unit we use is closer to angstroms. We frequently convert back and forth from floating point "user units" to integer "db units". Integer gives you all the precision you could need if you scale your data. I provide the scale_up() and scale_down() interfaces on all my geometry concept types to make that easy. Hope that helps, Luke

Thomas Klimpel wrote:

- The references to the paper and the presentation are very welcome, and really add value to the documentation. But what is meant by "Performance of GTL could be improved by up to 10X with further work on the arbitrary-angle Booleans"???

If you look at slide 15 of the presentation "Manhattan Benchmarking" there is greater than 10X performance delta between gtl and gtl45. I consider the gtl45 algorithm to be something of a lower bound on performance that I could get in the arbitray angle case. Based upon the observation that 90% of runtime is spent in the sub-optimal line segment intersection phase, which could be done at a constant factor additional cost if incorporated into the sweep-line that performs the boolean and the potential to speed that sweep-line up for the 2-input case by applying different data structures I think that given several weeks of effort the algorithm could be sped up ~10X.

I also notice that the library is not intended to directly handle real GDSII or OASIS layout data, which is typically stored in hierarchical form. (This hierarchical form means more or less that some basis shapes are directly defined as polygons, and the more complex shapes are defined by reference to basis shapes or already defined more complex shapes.)

We have propriatary OASIS and GDSII reader/writers. GDSII is simple to parse, but OASIS is quite involved and requires code comparable in scale to the Boost.Polygon library. Reading these data formats imply a hierarchical geometry data model that they are read into. Implementing such and the basic capabilities one would expect of it is also involved. A system with GDSII/OASIS reading and writing, a hierarchical data model with query capabilities plus Boost.Polygon geometry library could easily run 250 KLOC of C++. If you investigate the OpenAccess http://www.si2.org/openeda.si2.org/ data model you will find that Cadence has already released its hierarchical data model and file format reader/writers as open source, and is pushing a million lines. Notably absent in the OpenAccess system are the capabilities present in the Boost.Polygon library.

So I finally have to thank Lucanus Simonson and it's employer for writing this excellent library and proposing it as a boost library.

Thank you Thomas for all your work reviewing it, Luke

Simonson, Lucanus J wrote:

Thomas Klimpel wrote:

...

- The unit-tests should be split into smaller files and use a nonzero exit value to indicate failure. They should be placed in libs/polygon/test.

What granularity would you like to see the tests broken into?

It's OK from my point of view to have many tests in a single source file, as long as regression testing is still possible. My basic assumption is that any unit-test can potentially fail, so it's not good if a single failing unit-test will mask many other unrelated test results. The typical reaction in such a situation would be to comment out the failing unit-test, which bears its own risks... One point to consider when writing unit-tests for a template library is that the compiler will not even find simple typos as long as a template function is not instantiated and called with a concrete type (Try this yourself: Change line 207 of interval_concept.hpp from "high(interval, (newHigh));" to "hhigh(interval, (newHigh));", and see if you can find a compiler that will detect this typo when compiling your current unit-tests.). So I probably would put pure "compile" tests into different source files than real functional tests. Having pure "compile" tests that just exercise every template function in the interface of a concept might be a good idea, especially if the test function is itself a template that is instantiated and called both for a class provided by the library and a custom class which registers as that concept. I also wouldn't object to have "compile" tests for more than one concept in a single source file. Don't forget the "use a nonzero exit value to indicate failure" advice for the functional tests. Even if you don't want to abort at the first failing test, ensure that the exit value is non-zero as soon as at least one test failed.

...

- Failing unit-tests should not be commented out just because they fail to compile.

I uncommented the handful of tests that I had commented out in the unit test source and these tests do compile and pass in MSVC9 and gcc4.2.2. The only tests commented out now are one which fails because the functionality isn't implemented (planed but not implemented functinality) and one that has long runtime and performs no functional testing.

After the custom_xxx.cpp examples failed to compile, I searched for "geometry_concept" in "gtl_boost_unit_test.cpp" and all occurrences of it were in code that was currently commented out. I searched again for "geometry_concept" after your modifications, but the corresponding code is still commented out. Regards, Thomas

Simonson, Lucanus J wrote:

Interval concept high() is called in the internal implementation of many algorithms, so even if there is no unit test for it the unit tests do cover it. I do understand about template functions not being compiled if not used.

The mentioned line 207 is inside the template "scale_up", and my compilers didn't detect this syntax error. But my point was just that compile tests are important for template libraries, and I see that you basically are aware of this. However, the statement "I do understand about template functions not being compiled if not used." is not the complete truth, because gcc compiles template functions even if not used, but he is not able to detect all typos until the function is used with a concrete type.

My unit test does return non-zero error code.

You are right, I was misguided by lines like if(!equivalence(p90, rect)) std::cout << "fail 1\n"; because I hadn't seen that "//this is a compile time test, if it compiles it passes" was written above the function.

Having multiple files would help in the circumstance where multiple developers are breaking and fixing different pieces of the code simultaneously.

I guess for boost it would more be like automatic regression tests run on many different platforms by people you will never meet in person, but you can access the test results by a web interface. However, you will not always have access to the compiler where your code fails, so the fixing might be not as simple as you currently imagine... So it may be sufficient to just put the compile tests in one file and the functional tests in another. Maybe you would also want to put the long running functional tests in yet another source file, so you don't have to comment them out.

Thanks, I think reviewing the unit tests is an important and easily overlooked area and I'm grateful that you took the time.

You're welcome. Thomas

A few more thoughts on my (nano-) review of Boost.Polygon.

Please always state in your review, whether you think the library should be accepted as a Boost library!

Boost.Polygon *should* be accepted as a Boost library. BUT it should NOT be called "Boost.Polygon" - as previous noted by Dave Abrahams - because it is not as fully generic as is possible. Boost.Polygon2D4590 perhaps ;-) I do not believe that Boost is *only* about stuff that can be considered for C++ Standardization. Stuff that is useful (with Good Quality) is also BoostWorthy IMO. 'Boost.Polygon2D4590' clearly does need some people's expectations and needs, and promises meet my expectations for quality. This would not preclude other library (or libraries) that aspires to be more generic. Although C++ provides tools to make things generic, there are still limits to what can be done without a price in compile and/or run time. 1D, 2D and 3D really have major differences that are still difficult to 'program' - as I have found just drawing plots. So I conclude from reading the discussions that some more learning is inevitable. It would be better to accept the real difficulties, and not expect to do the job in one pass. If necessary, to accept Boost.Polygon2D4590, Polygon1, Polygon2 ... Meanwhile I think it would be a bad mistake to not make something useful available NOW, especially when supported by a major company. If this library is rejected, its Open Source development will probably cease. The Best is the Enemy of the Good. Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com

Jeffrey Hellrung wrote:

+1; I'm generally sympathetic to Barend's concerns, especially the (apparent?) lack of direct floating point support. A generic geometry or polygon library could be a component in some fracture simulation research software I plan to eventually write, but imprecision associated with converting to integer types, and hence the associated inexact constructions of intersection points, makes the proposed Boost.Polygon unuseable for that purpose, in my opinion.

We are currently using my library for that exact purpose of a component in fracture simulation research. Floating point does not provide more precision than integer, each has a certain number of bits of precision and both produce inexact constructions of intersection points.

I would like to see at least a framework to be able to support floating point types and exact constructions. CGAL does this, I believe. I'm not familiar with their framework.

I can implement a transparent floating point to fixed point conversion wrapping the algorithm that is integer only. This should allow transparent use of the algorithm with floating point coordinates and no more loss of precision than floating point calculations themselves would produce.

That said, I just want to say it looks like Luke's library is very well designed toward its intended goals. I'll try to give a more elaborate review saying as much.

Thanks Jeff, Luke

John Phillips wrote:

You have made variations of this assertion a few times in this thread, and I wanted to point out one problem with it.

The distribution of the integers is not the same as the distribution of the floating point numbers. It is true that an x-bit integer has about as many distinct values as an x-bit floating point number. (Even more, depending on the representation used.) However, those integers are evenly distributed along the number line, and the floating point values are not. This will not cause a problem in many applications, but in any setting where large and small scales mix (such as polygons that are just off of regular, but need to be precisely defined; or systems that mix large and small polygons) there will be no scaling for the integers that both preserves the needed dynamic range and the needed precision. So the user will be forced to choose between overflow errors or lost precision.

This is true, of course. However, in such systems where large and small scales mix, floating point is itself problematic. When snapping a large scale intersection point to the floating point grid it may cause a long edge to sweep arbitrarily far, potentially crossing to the other side of large numbers over vertices at a small scale near the floating point origin. I would say that in general planar geometry has the property that precision of all points is equally important, and that floating point just provides the convenience of ignoring scale. We mix large and small scale features in VLSI, our package layer looks like a PCB, while the metal layers below are many orders of magnitude smaller. If you can't represent the small features in your integer type because the extents of your large features are simply too huge you have many many many orders of magnitude difference between them, enough that by definition you won't be happy with floating point calculations either. Good question, thanks, Luke

John Phillips wrote:

This will not cause a problem in many applications, but in any setting where large and small scales mix (such as polygons that are just off of regular, but need to be precisely defined; or systems that mix large and small polygons) there will be no scaling for the integers that both preserves the needed dynamic range and the needed precision.

As strange as it sounds, VLSI is exactly such a domain where the mixing of large and small scales occur, but floating point coordinates are not the complete solution in this case. The mixing of scales happens as follows: The "global design" is build from smaller building blocks. The small building blocks (referred to as cells) are described in a local coordinate system around the origin. Larger cells then refer these smaller cells and apply a similarity transformation to them. The accuracy within the small cells is in the order of nm (1e-9m) but the coordinates in the "global design" are in the order of cm (1e-2m). So the ~9 digits of a 32-bit integer are luckily just enough, but I think nevertheless that this scenario is quite typical for settings where large and small scales mix. The mixing is made possible by the translation and rotation invariance of the euclidean plane. Fixed point numbers nicely preserve the translation invariance, and also 90 degree rotation invariance. Arbitrary angle rotations are luckily quite rare in typical applications, but I guess that many of the current tools won't handle arbitrary angle rotations too well (they will probably still snap to the initial integer grid). To support a mixing of scale would hence be more difficult than just providing support for floating point coordinates. You would also need be able to handle similarity transformations (possibly also with different coordinate types than the polygons) assigned to groups of polygons. The good thing about fixed point coordinates is that they preserve the translation invariance of the euclidean plane much better than floating point coordinates. (In a certain sense, the 45 degree special case is possible because of the invariance against translation along the diagonal of the grid. This means that a 26.565/63.439 degree special case would probably also be possible, but I guess no one will care for that special case.) So from my point of view, support for floating point coordinates would be a convenience feature, and possibly also a "performance" feature for a sufficiently good implementation of the floating point algorithms. But you shouldn't require "impossible" postconditions from the results in that case, because the "performance" benefit will otherwise quickly be lost again. As you probably know, the discussions about the "impossible" postconditions (or which postconditions would be reasonable) were not really settled: http://lists.boost.org/Archives/boost/2009/03/149515.php http://lists.boost.org/Archives/boost/2009/03/149693.php Regards, Thomas

John Phillips schrieb:

Simonson, Lucanus J wrote:

...

I can implement a transparent floating point to fixed point conversion wrapping the algorithm that is integer only. This should allow transparent use of the algorithm with floating point coordinates and no more loss of precision than floating point calculations themselves would produce.

Thanks Jeff, Luke

Luke,

You have made variations of this assertion a few times in this thread, and I wanted to point out one problem with it.

The distribution of the integers is not the same as the distribution of the floating point numbers. It is true that an x-bit integer has about as many distinct values as an x-bit floating point number. (Even more, depending on the representation used.) However, those integers are evenly distributed along the number line, and the floating point values are not. This will not cause a problem in many applications, but in any setting where large and small scales mix (such as polygons that are just off of regular, but need to be precisely defined; or systems that mix large and small polygons) there will be no scaling for the integers that both preserves the needed dynamic range and the needed precision. So the user will be forced to choose between overflow errors or lost precision.

John

Hi there, as indicated by Lucanus a mapping from float to int (or equivalently from double to int64) can be performed without loss of accuracy. The transformation is however not linear. A potential possibility to keep track of the mappings over various scale levels could be easily established for data that support the ieee floating point standard: Since there are only a finite number of floats and the number of steps between 2 given floats is the same as the number of steps between the corresponding integers the transform for a polygon would start out by determination of the centroid of the bounding box. From this centroid any point of the polygon contour may be measured in terms of floating point numbers between the corresponding x y positions. Thus the distance is based on the metric of "how many times do I have to increment my floating point to reach a coordinate given the origin" NOT based on a scaling. Accordingly, the integer representation may be obtained by "casting" float to int data and determination of the numbers inbetween: essentially given 2 doubles double originX = ...; double pointX= ...; // convert to float and determine number of steps between the 2 floats : float oX = (float)(originX); float pX = (float)(pointX); int x = numbersBetween(oX,pX); .... // now obtain some new integer by int newx = anyfunction(x); ... // while the floating point data MUST be retrieved via float newX = advance(oX,newx); with numbersBetween and advance something like that: /*! * interpret storage of a float number as integer (same size in memory) * and return as lexigographically ordered two complement int, * i.e. +0.0 and -0.0 are viewed as same number */ inline int const intValue(float const &argValue) { return ( *(reinterpret_cast<int const *>(&argValue)) < 0 ) ? (INT_MIN - *(reinterpret_cast<int const *>(&argValue)) ) : *(reinterpret_cast<int const *>(&argValue)); } /*! * determine number of discrete floating points that may live between 2 given floats */ inline int const numbersBetween(float const &argA, float const &argB) { return (intValue(argA) - intValue(argB)); } /*! * given a float a the number of floats that are possible between another * float than determine and return that float */ inline float advance(float &argValue, int argSteps) { int intdelta = intValue(argValue) +argSteps; return *(reinterpret_cast<float *>(&(intdelta))); } Regards Uwe

Andreas Fabri wrote:

Hello, ... What is the overall strategy in the Boost project for accepting new topics for Boost ?

Hi, Andreas. I'll give one person's opinions in answer to your questions. I would say there is no set process, and no clear guidelines. The measures used most are about perceived need in the community, and ameanebility to a generic solution that is suitable for a broadly used library. The first is judged by the interest level of developers inside and outside Boost in the project. The second is judged partially by experience and partially by the library provided. That is, many of the Boost developers have done enough generic work to have some intuition for what problems are well suited to a generic solution, and this drives some of their work. However, if someone shows up with a good generic solution to a problem no one thought could be done that way before seeing the code, then the response is pleased acceptance of the solution. This is not enough for a Boost library, yet, but it is a good start. Coupled with clear design, solid cross platform coding, thorough testing and well developed documentation this start becomes what Boost wants from a library.

First, it seems strange to me that something as specialized as 45 degree polygons is considered to fit in, what I consider as the mission statement of Boost : ...

The review is not yet completed, so the decision may be that it does not fit in Boost. However you might be missing the forest for the trees. Many Boost developers (myself included) think a good geometry library would be a solid addition to Boost. It is an area that allows generic solutions, that has some very persnickety details that are very easy to get wrong, and that is applied in a large number of different problem and application domains. Given that starting place, the real question of the moment is whether Luke's library is the right geometry library for Boost. One feature of Luke's library is the inclusion of specialized implementations for the 45 and 90 degree polygons. It is a feature that may not be useful in many interested domains, but is very important in the domain for which the library was originally designed. If this was all the library could do, then it would not be a good candidate for Boost. However, many libraries include optimized routines for specific use domains along with the more generic foundation. I see nothing wrong with it.

When I say specialized, obviously something like boost::optional also solves a specific problem, but it is completely independent from a particular application domain. Boost.Polygon seems rather related to VLSI and PCBs, and the only criteria it fulfills is the license choice.

If, in the opinions of the reviewers and review manager the decision is that this library does not extend usefully outside the realm of VLSI and PCBs, then I would expect the result to be rejection. However, if it currently has broader applicability and the review process makes it clear how that can be built on to cover many of the needs in the field then those are points in the library's favor during the review.

Second, I am wondering about, when you add a first geometry related library without having the blue-print for "Geometric Computing in Boost", how can you hope that it will ever grow into a coherent whole?

best regards,

andreas fabri

Boost isn't a centrally controlled work from a pre-approved blue print project. Any blue print for geometric computing, or for any other extended topic in Boost is the responsibility of the developers who bring a proposal to the table. In the case of a geometry library in specific, one reasonable line for questions in the review is about how the choices in this library affect the options for adding other features that make sense as part of the core library, as well as building non-core features on top of the provided facilities. Once again, if the views of the reviewers and the manager are that Luke's library design cuts off important growth in the future then the library is unlikely to be accepted. However, providing concepts and abstractions that ease such expansions are a strong positive for the library. As stated before, this is one person's opinions and should not be taken as anything else. I still hope to review the library and so I may provide my own list of pros and cons for the design, implementation, and documentation. This is not that list. When I mention pros or cons above, they are by way of a thought experiment example, and nothing more. Take it for what it is worth, but I hope that helps. John

Barend Gehrels wrote:

1) the library supports many operations, but some basic polygon algorithms are missing: - convex hull - centroid - is_convex

A grounded argument against inclusion of Polygon in boost would be that the design makes it difficult or unnnatural to implement these alorithms to extend the library or as user code, which I don't believe is the case. Obviously the library cannot implement every algorithm, but it does provide a solid foundation for the building of algorithms it does not provide. Centroid, for example, can be implemented by using the Polygon library algorithm that subdivides a polygon into trapezoids and then accumulating the weighted centroids of the trapezoids.

- the "intersection" operation is too slow compared with other libraries. The paper (referred to in the documentation) compares the intersection performance with GPC and CGAL, but does not give exact figures. It gives some plots about scalability using a very high number of points per polygon.

From the boost website: " The interface specifications for boost.org library components (as well as for quality software in general) are conceptually separate from implementations of those interfaces. This may not be obvious, particularly when a component is implemented entirely within a header, but this separation of interface and implementation is always assumed. From the perspective of those concerned with software design, portability, and standardization, the interface is what is important, while the implementation is just a detail.

Dietmar Kühl, one of the original boost.org contributors, comments "The main contribution is the interface, which is augmented with an implementation, proving that it is possible to implement the corresponding class and providing a free implementation." " Performance is very important, but performance can be addressed over time without changing the interfaces. If there were an algorithm that was licensed under the boost software license that was 100% robust and faster than what I implemented in all cases I would happly accept a patch to swap out my implementation for that algorithm. The runtime measurements you have performed are largely the same benchmark repeated many times with minor variations. My line segment intersection algorithm is suboptimal. When there are a large number of edges that all overlap in their x ranges it degenerates to n^2 runtime when an optimal algorithm would scale closer to linear runtime. It is not hard to construct a benchmark to expose this weakness. My overal intersection algorithm also carries a high constant factor overhead. In your own benchmarking of my algorithm you will observe that it is sometimes faster and sometimes slower than geos, GPC and CGAL. Only your algorithm is faster across the board in your testing. If you are a factor of 10 faster than every other implementation that's great, but we don't know any of the details of your algorithm. What are its preconditions, what post conditions does it guarentee? Is it numerically robust? My understanding of your line segment intersection is that you snap to the floating point grid and ignore the potential to have self intersecting figures in the result. That is a somewhat important post-condition for this kind of algorithm. Particularly for things like, say, fracture analysis where the numerical solvers will reject such polygons at the input to meshing.

3) Boost.Polygon supports integer but does not support double for boolean operations. For the operations "area" and "contains", coordinates in "double" floating precision are supported. Also the boolean operations accept double coordinates, but crashes immediately. I think it should not crash, slightly better is to prevent floating point coordinates by giving a compilation error. Much better: floating point coordinates should be implemented. For me as GIS-user, a library without floating point support is unusable.

In a floating point number you have a certain number of bits of precision. An integer type can be chosen with equal or greater precision and the input translated to center on the origin and scaled by a power of 2 to use the max number of bits when converted to integer. The intersection operation is then performed with at most one bit of snapping and rounding loss of precision and then the result can be scaled back to floating point and translated back to its original position. With this scheme you get precision exactly comparable to what floating point provides. You may not be able to use equality compare on the floating point values from before and after, but you shouldn't be doing that with floating point numbers in the first place. I can detect floating point coordinates at compile time and insert this scaling such that it is transparent to the user of the library. This fixed point algorithm really is equivalent to floating point.

...

- What is your evaluation of the design? The diagram shows the polygon_90 as a refinement to a rectangle, the polygon_45 as a refinement to a polygon_90, the polygon as a refinement to a polygon_90, and a polygon_45_with_holes as a refinement to both a polgon_90_with_holes and a polygon_45. All this makes really no sense to me, I think it could and should be much more simple.

I believe Steven Watanabe already pointed out that the arrows in the diagram are the reverse of what is conventional. This is a fix that needs to be made to the documentation. What is implemented in the library is the correct refinement relationship. I recall Dave Abrahams posted an ascii diagram of what he thought the refinement relationships should be:

refinement:

+-- p <------+ / \ pwh <--+ +-- p45 <---+ \ / \ +-- p45wh <--+ +-- p90 \ / +-- p90wh <--+

Ja? Polygon is a refinement of polygon with holes, polygon45 is a refinement of polygon, polygon90 is a refinement of polygon45 and rectangle is a refinement of polygon90.

...

- What is your evaluation of the implementation? It is curious that Boost.Polygon went from Tag Dispatching to SFINAE last year, while we (GGL) went from SFINAE to Tag Dispatching. We're very glad with our change, while most compiler problems and warnings in Boost.Polygon origin from the SFINAE implementation. I'm still convinced that Tag Dispatching, suggested to us on this list by Dave Abrahams, is a very good choice in a geometry library implementation. We're happy with it and all compiler and compatability problems are vanished.

SFINAE is necessary for generic operators and good to have for generic functions with very generic names such as "area" and "distance". SFINAE is not a bad thing in a boost library. It turns out thate once compiler issues are understood they can be overcome.

Things are copied from other boost libraries. File isotropy.hpp contains a nearly literal copy of enable_if. There is also an extraction of MPL. While this is an explicit choice, I don't think it is a good choice. The Boost Concept Check Library is not used to check concepts.

These things copied from boost source code are inside #ifdef BOOST_POLYGON_NO_DEPS and are to facilitate compiling and using the library in stand alone mode. This is necessary for internal use of the library and I didn't want to fork the code to submit it to boost.

I didn't try everything, but I'm getting the feeling that the concepts are not implemented as they should be. The file polygon_set_concept.hpp, which should give an outline of the polygon set concept, is dependant on polygon_set_data.hpp (which implements that concept). That should be the other way round. Inside that concept file, points are often copied into a polygon_set_data temporary. That is not how concepts should be implemented, and is very bad for performance.

I have to copy the polygon edges into something so that I can sort and scan them. That thing is encapsulated by the polygon_set_data class.

I conclude with the remark that I've asked several times on this list and off-list for cooperation, I suggested that Luke could join us writing a combined Geometry Library for Boost. All these requests were never answered. I would still be in favour of one library. If this library is accepted it will create a different situation for subsequent geometry libraries. In reviews it will be expected that these libraries work together or that one is built on top of the other. If that is the case, the base should be very very good. It is to the other reviewers to decide that this is the case.

Our agreement at boostcon was that I would submit my library for review in a matter of months and that eventually when your library is reviewed it would be necessary to demonstrate interoperability. There is nothing about my library that would make it hard to demonstrate interoperability so I don't understand your concern. Kindest regards, Luke

Thomas Klimpel wrote:

Simonson, Lucanus J wrote:

...

Barend Gehrels wrote:

...

I didn't try everything, but I'm getting the feeling that the concepts are not implemented as they should be. The file polygon_set_concept.hpp, which should give an outline of the polygon set concept, is dependant on polygon_set_data.hpp (which implements that concept). That should be the other way round. Inside that concept file, points are often copied into a polygon_set_data temporary. That is not how concepts should be implemented, and is very bad for performance.

I have to copy the polygon edges into something so that I can sort and scan them. That thing is encapsulated by the polygon_set_data class.

I think what Bahrend Gehrels observed here is related to my remark "..., and the source files implementing the concepts got overloaded with algorithms (or algorithm dispatch code).".

It would be cleaner to only implement the interface of the polygon_set concept in polygon_set_concept.hpp and implement the algorithms (or dispatch code) that work on the polygon_set concept in their own source file. This approach will also scale better as you add more algorithms to the library. I think it is a good idea that the algorithms use polygon_set_data internally, but it would not be a good idea if the implementation of the interface of the polygon_set concept would make use of polygon_set_data.

To be honest, I really think that it would be a good idea to "slightly change the organization of the code into source files".

I agree that the presence of implementation details of the definitions of functions at the same place where they are declared makes the header files harder to read. Are you suggesting that I separate the declarations of functions from their defintions and place the defintions in the detail directory? Doing so would double the effort required to maintain the interfaces. Most boost libraries implemented as header only do not seperate the declarations from the defintions. I favor the idea in principle, however. As to the dependency of the concept on polygon_set_data, it is not the interface, but the implementation that depends on polygon_set_data. In order for the interface to be dependent on polygon_set_data the interface would need to refer to polygon_set_data in the declarations of functions, using it in the definition of the function is not a dependency of the interface, per se, but an implementation detail. I don't believe that polygon_set_data is referenced anywhere in the declarations of concept functions. Thanks, Luke

Hi Luke, Thanks for your explicit answers to my concerns. Simonson, Lucanus J wrote:

Barend Gehrels wrote:

...

1) the library supports many operations, but some basic polygon algorithms are missing: - convex hull - centroid - is_convex

A grounded argument against inclusion of Polygon in boost would be that the design makes it difficult or unnnatural to implement these alorithms to extend the library or as user code, which I don't believe is the case. Obviously the library cannot implement every algorithm, but it does provide a solid foundation for the building of algorithms it does not provide. Centroid, for example, can be implemented by using the Polygon library algorithm that subdivides a polygon into trapezoids and then accumulating the weighted centroids of the trapezoids.

Which will give a (probably very) bad performance.

...

- the "intersection" operation is too slow compared with other libraries. The paper (referred to in the documentation) compares the intersection performance with GPC and CGAL, but does not give exact figures. It gives some plots about scalability using a very high number of points per polygon.

...

From the boost website: " The interface specifications for boost.org library components (as well as for quality software in general) are conceptually separate from implementations of those interfaces. This may not be obvious, particularly when a component is implemented entirely within a header, but this separation of interface and implementation is always assumed. From the perspective of those concerned with software design, portability, and standardization, the interface is what is important, while the implementation is just a detail.

Dietmar Kühl, one of the original boost.org contributors, comments "The main contribution is the interface, which is augmented with an implementation, proving that it is possible to implement the corresponding class and providing a free implementation." "

Performance is very important, but performance can be addressed over time without changing the interfaces. If there were an algorithm that was licensed under the boost software license that was 100% robust and faster than what I implemented in all cases I would happly accept a patch to swap out my implementation for that algorithm.

The runtime measurements you have performed are largely the same benchmark repeated many times with minor variations.

Originally I had one intersection benchmark, but you suggested that I should test scalability and environments with high intersection density... So I did. There are indeed two types, the ellipse and the star, tested both three times for scalability. The 10001 test is probably ridiculous in the sense that it can take 20 hours for a library, but I still think the benchmark is testing normal and heavy GIS operations. And users can use other datasets of course. Sorry that I cannot test your 45-90 polygons, I've no use cases and not the experience.

My line segment intersection algorithm is suboptimal. When there are a large number of edges that all overlap in their x ranges it degenerates to n^2 runtime when an optimal algorithm would scale closer to linear runtime. It is not hard to construct a benchmark to expose this weakness. My overal intersection algorithm also carries a high constant factor overhead. In your own benchmarking of my algorithm you will observe that it is sometimes faster and sometimes slower than geos, GPC and CGAL. That is true. In the most heavy case it is faster than GPC, but it loses a lot of precision than which worries me. Only your algorithm is faster across the board in your testing. If you are a factor of 10 faster than every other implementation that's great, but we don't know any of the details of your algorithm. What are its preconditions, what post conditions does it guarentee? Is it numerically robust? My understanding of your line segment intersection is that you snap to the floating point grid and ignore the potential to have self intersecting figures in the result. That is a somewhat important post-condition for this kind of algorithm. Particularly for things like, say, fracture analysis where the numerical solvers will reject such polygons at the input to meshing.

Thanks for your clarifications. The details of my algorithm will be described separately and indeed I start with non-self-intersecting polygons, giving a non-self-intersecting output.

In a floating point number you have a certain number of bits of precision. [snipped]

This is also addressed by John, and I wanted to add that I cannot live with this behaviour because in my tests, which reflects my normal usage, GIS Map Overlay, I don't get the right results. If I take a higher factor, it starts to overflow. If I take a lower factor, it is not precise enough.

Polygon is a refinement of polygon with holes, polygon45 is a refinement of polygon, polygon90 is a refinement of polygon45 and rectangle is a refinement of polygon90.

I would say: a polygon always have zero or more holes. A polygon45 is a specialization of a polygon (overriding the algorithms where it makes sense, e.g. performance-wise). A polygon90 is another specialization of either a polygon or a polygon45. A rectangle is a special case, having nothing to do with a polygon, this makes things really complicated.

[snipped some things which are answered]

...

I didn't try everything, but I'm getting the feeling that the concepts are not implemented as they should be. The file polygon_set_concept.hpp, which should give an outline of the polygon set concept, is dependant on polygon_set_data.hpp (which implements that concept). That should be the other way round. Inside that concept file, points are often copied into a polygon_set_data temporary. That is not how concepts should be implemented, and is very bad for performance.

I have to copy the polygon edges into something so that I can sort and scan them. That thing is encapsulated by the polygon_set_data class.

As far as I know concepts should not implement things. Concepts should model things. Algorithms should take classes fulfilling the concepts. In BP, inside the concept file a model of that concept is used to do things. It sounds as inside-out.

Our agreement at boostcon was that I would submit my library for review in a matter of months and that eventually when your library is reviewed it would be necessary to demonstrate interoperability. There is nothing about my library that would make it hard to demonstrate interoperability so I don't understand your concern.

We discussed interoperability at BoostCon and I was advised to take Boost.Polygons booleans. Therefore I started those benchmarks and included our (then suboptimal) intersection. Because of your paper and presentation, everyone had good confidence in the performance. However, I concluded other things and mailed this in June (off-list), giving the message that we could not use Boost.Polygon's booleans because of performance, because of floating point and because of compiler issues (the last ones are solved now). Another thing I wanted to test is if we could adapt our geometry types to each others concepts. That test is not done, at least not by me, but for purpose of this review I looked to your concepts. Not an in-depth study. I conclude that it is, at least partly, implementation. So I don't know how to continue with this. It is useless to give Boost.Polygon my polygon and as soon as BP does things with it, the whole thing is just converted. That is not how a geometry concept should work. Regards, Barend

Thomas Klimpel wrote:

Barend Gehrels wrote:

...

I don't know whether convex hull should be considered as a basic polygon algorithm. It is the base of some other algorithms, e.g. the polygon diameter (furthest point pair, e.g. http://pagesperso-orange.fr/colin.barker/lpa/anti_pod.htm). But indeed it can be discussed if it is really basic. It is prescribed by OGC and implemented by most spatial databases.

...

2) though some reviewers were satisfied about the performance, and the paper indicates it is well performing, our benchmark shows that it is in general slower or much slower than other libraries:

Who do you mean by "some reviewers"? The review by "Sebastian Redl" doesn't talk about performance, nor do most of the pre-reviews.

I did mean one of yours indeed:

-> The benchmarks by the author also indicate that the library is very efficient. <-

And this one by Mathias:

The library appears to be quite adequate at performing operations on dynamically-sized polygons of integral coordinates.

...

I think most people using geometry / polygons are using floating point coordinates. As these are not supported in the algorithms where this library is specialized on (booleans), I think it is useful for a limited public (VSLI?)

It's also useful for VLSI :)

Sure :-)

...

I hope that my review was as objective as can be expected from an alternative library writer. ... It is to the other reviewers to decide that this is the case.

So I conclude from this (as being one of the other reviewers) that you don't vote against accepting Boost.Polygon as a Boost library. Or did you just miss the advice "Please always state in your review, whether you think the library should be accepted as a Boost library!"?

This is a difficult one, the one that I wanted to avoid indeed, so I omitted it from my reply. As a Boost-user, always working with and interested in geometry, this library in its current form is of no use for me. But of course, I'm part of the team of another geometry library, having most of this one and more... so why would I use this one... Therefore I feel I can't vote. Regards, Barend

Barend,

Inside the Boost review process, you are quite welcome to vote. It is a good idea for you to make sure such mitigating factors as you list are clear in your review, and it is the review manager's job to decide how that should affect the weight given to your vote.

John Phillips Review Wizard

OK, so here is my vote: NO I've already sent several issues to this list, and have many concerns about this library. The main reasons to vote "no" are: 1) it is way too slow 2) its concepts are not sound 3) it is not generic ad 1) the library is specialized on polygon boolean operations (intersection, union, symmetric difference). But they are implemented very slow. Of course everything can be enhanced lateron, but we're measuring now, we don't know what we will measure lateron. A simple overlay operation costs 92.2 seconds using Boost.Polygon, versus 1.1 second in GGL. So how can I vote yes for this? Besides that the result is less precise... Anyone is welcome to test this assertion, to reproduce my figures. ad 2) already explained in another posting. The file polygon_set_concept contains the "area" operation, copying a set of poylgons to another std::vector of polygons just to calculate the area... This is not sound in design and in implementation. Copying of polygons is as far as I glanced through done in many operations for polygon_sets. ad 3) Quote of John Phillips' mail:

Many Boost developers (myself included) think a good geometry library would be a solid addition to Boost. It is an area that allows generic solutions, that has some very persnickety details that are very easy to get wrong, and that is applied in a large number of different problem and application domains. I agree with this. But I don't think that Boost.Polygon is a good geometry library (yet). a) it is polygon only b) it is 2D only c) it is cartesian only d) it is (for boolean operations) integer only

Look below for an elaboration. For integers: of course we can map to integer but as I've said earlier, the results are different. In my benchmark the resulting summed area is 155 vs. 161, which is the correct answer. If I take other factors the result is even less precise or overflows. Luke, if I'm doing things wrong here, please tell me. But this deviation is way too large. Boost.Polygon seems to just unable to handle this case. ----------- Elaboration: let me memorize the previews for GGL here shortly, because they are relevant, and now that my reactions are classified as "mine-is-betters-than-yours" anyway. I came with a geometry library preview in January 2008, which was criticized on this list because it was 2D only and Cartesian only (it still had more than polygons) and its concepts were not clear. Those critics were very welcome because they have greatly enhanced the library. In the meantime Bruno Lalande (who already contributed to Boost) joined me. We did another three previews. It has now a sound core for 2D/3D/nD, it is cartesian as well as spherical, it has clear concepts modeled as a set of small metafunctions. It is now really generic. On the last preview there were not so many comments. This spring Mateusz Loskot joined us, having much experience with open source and geometry. The library would have been for preview 5 in August, that was postponed until about October. Intersections are new here by the way. In between Federico did the Google of Summer spatial index effort, now included in the library. The library is now used in e.g. an OpenStreetMap mapping program and the OpenGraphRouter. GGL is partly hosted by osgeo, partly by Geodan, partly by Boost Sandbox, this is a somewhat uncomfortable situation so we'll look forward to have one place for it. There is, as far as I know, noone who really compared the two libraries, Boost.Polygon and the GGL. It seems that I'm the only one until now, but I can be considered as being subjective. It would be very good if an objective person would compare the two libraries, in design, in implementation, in functionality, in performance. I also suggested (off-list) that the libraries could go for (another) review together, at the same time. But other people were less enthousiastic about that, being more complicated for the reviewers. Boost.Polygon is now for review as the first one. Acceptance of Boost.Polygon might change our efforts. I don't know if I, or my team, or my employer, will make it possible for us to go for review as a second boost geometry library. And our generic library cannot be based on a non-generic kernel. We can and will not go back to 2D / Cartesian. GGL has nearly everything what this Boost.Polygon library has. It does not have 45/90 angled polygons, nor plans for it. But Luke is welcome to add them to our library, it is perfectly feasable, it makes sense. I sent this to Luke last July, to which I referred to earlier:

Let me also repeat that you're still welcome to join us. We're prepared to add 45 and 90 manhattan geometries. You could implement your algorithms as specializations for those cases.

Both parties worked for nearly two years on this boost process and (future) submission. We've had several useful discussions and I met Luke at BoostCon. So in a way it is hard to say no. But I think Boost.Polygon is not the long waited-for geometry library. We should cooperate, resulting in a generic Boost geometry library, including the VLSI specializations. Regards, Barend

...

...

...

...

"Arash" == Arash Partow <arash@partow.net> writes:

Arash> A convex hull is by definition, simply, a set of points. The Arash> cardinality of such a set is infinite. From a geometers point Arash> of view a hull is its own structure or entity and has its own Arash> set of operations. Just because a couple of GIS applications Arash> you've work with in the past seem to have a representation of Arash> CHs that resemble a polygon doesn't mean that has to be the Arash> case. It seems to be more than a cople of GIS applications. For what it is worth, from Wikipedia (http://en.wikipedia.org/wiki/Convex_hull): In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X. In computational geometry, it is common to use the term "convex hull" for the boundary of the minimal convex set containing a given non-empty finite set of points in the plane. Unless the points are collinear, the convex hull in this sense is a simple closed polygonal chain. - Maurizio

Bahrend Gehrels wrote:

...

I'm not sure what you mean by "basic polygon algorithm". If you could qualify that phrase [snipped] No, I cannot qualify that phrase. You see the convex hull in most libraries, e.g. wykobi, and in most textbooks on geometry, and in every spatial database, and can be used to figure out things like diameter. Therefore I consider it as basic.

I raised the question whether "convex hull" is a "basic polygon algorithm", because it is not the only "basic 2D" algorithm, and I wasn't sure whether - Delaunay triangulation - Voronoi diagram - Closest pair of points - Euclidean shortest path - Polygon triangulation would all make their way into the requirements, if one doesn't clearly state what needs to be provided for a polygon library and what can be considered as optional. Providing just "convex hull" is probably not really difficult, but some of the other algorithms might be more challenging. Regards, Thomas

Phil Endecott wrote:

The first step was to add the "magic" required by the library to support my rectangle type. The examples don't seem to include a custom rectangle, and the decomposition of a rectangle into a pair of intervals rather than the more common pair of points or point and size, made this a bit tricky. More serious were the following problems:

** The library does not seem to use any sort of explicit concept checking; if types do not satisfy their concepts random errors from deep inside the library are emitted. The verbosity and incomprehensibility of errors from complex C++ code is, in my opinion, the greatest single failing of the language today. In the face of these ridiculous messages, some users will simply abandon trying to use the library (or the whole language, and go back to C) or limit themselves to only what can be done by copying examples. Fixing this needs effort from the language designers, compiler writers, and libraries. I am not certain that concept checking can totally cure this problem, but it can only help.

I believe that I should supply concept checking tests (similar to the examples in the docs) for all concepts so that users who try to map their object types to my concepts can check whether it is correct. I don't know how much I can do to make error messages more friendly as a library author. My intention was to provide a library that demonstrates what a C++ concepts based library would look and feel like. I've been successful in that. I think that the verbose error messages issue is something that is a problem many boost libraries have.

** The library spews out enormous quantities of warnings (gcc 4.1.2), I think mainly related to unused parameters. This has to be fixed (and I don't believe fixing it is hard).

I thought I had fixed it already. I made a few changes, compiled my unit tests without warnings with gcc 4.1.2, and checked those changes in during the review.

** The library failed to work with std::pair being used as the interval type, despite this being mentioned as a possibility in the documentation. The problem seems to be that the std namespace is brought into ADL and std::set is found rather than the library's own set function. I have not investigated how hard this would be to fix; instead I wrote my own pair template.

I was aware that ADL poses a problem for the functions I gave exceedingly common names to, not least the operators. I can guard useage of set() with (set)() throughout the library and add tests that std::pair can be adapted to both point and interval.

Having completed the "magic", I started to adapt my marker drawing code. My first attempt was a minimally-invasive version that would check if each marker covered any new area and not plot it otherwise:

if (!contains(markers,b)) { markers |= b; plot(b); }

Unfortunately this failed since contains() does not seem to be defined for a polygon_90_set and a rectangle. This surprised me somewhat. A valuable addition to the documentation would be a matrix indicating which operations are supported between which types. Somebody will need every combination of operations and types, and it would be useful to see quickly which are provided, which are planned for a future version of the library, and which cannot be implemented due to some restriction of the library design.

It is possible to make a list of all free functions and all the concepts they accept. It was suggested by other reviewer. I could make an index section to the documentation.

I could have tried to implement contains(polygon_90_set,rectangle) in terms of e.g. intersection but I was concerned that that would have much worse complexity than an optimised contains() algorithm could have. Which raises another issue:

** Algorithms should indicate their complexity guarantees, and (where different) their expected complexity for common inputs.

I can add this to the documentation.

So I moved on to a more invasive modification where I accumulate all of the rectangles and use get_rectangles() at the end to extract a minimal set of areas to plot:

for (...) { markers |= b; } get_rectangles(rects,markers); foreach(rect in rects) { plot(rect); }

This works, and reduces the number of rectangles that are plotted from about 6,000 to about 900. Unfortunately get_rectangles() takes about 100 ms to run, which is slightly longer than plotting the redundant markers would have taken, so overall the frame rate is not improved.

In that code, I was surprised to see that get_rectangles takes an output container by reference. In this case, I have no need to allocate memory and store these rectangles at all. I would have prefered some way to get the rectangles as they were generated and pass them directly to my plot function, e.g.

for_each_rectangle(markers, &plot);

An output iterator would be a more conventional (but in this case more verbose) way to achieve this.

** Unless there is some good reason for using output reference parameters, algorithms should use output iterators.

I expected this feedback to come up during the review. I can add the output iterator based inerfaces.

I was also a little confused by the difference - if any - between "markers |= b" and "markers.insert(b)". I believe that I know what the former does, but I worry that unioning-in each rectangle in turn is inefficient and that it would be better to construct a set of rectangles and self-union in one go. Perhaps this is what insert() does - yet there is no self_union function, and in practice I seem to get the same results. Maybe get_rectangles() has done the self_union. Some clarification of this in the documentation would be useful.

markers |= b is implemented by a call to insert, get_rectangles does indeed to the self union. I have discussed this optimization during the review and it is described in the documentation as well.

One issue that I noted while reading in the polygons is that the provided polygon_data type is immutable: to read from a file, I need either an exotic iterator that can be passed to its constructor, or a temporary. I'm unsure why polygon_data can't be more like a mutable std::container so that I can simply read points from a file and push_back() in a loop. Trying to use a std::vector<point_data> required more traits specialisation that I expected; can't this be pre-defined?

** The polygon_data type should be mutable (i.e. support things like push_back()), or a mutable version should be provided, or std::vector/list<point_data> should work with minimal traits specialisation.

The example custom_polygon.cpp shows the traits for a list<CPoint>. I could make all containers of points models of polygons_concept by default, but I wouldn't know which polygon concept the user prefers.

I also found that polygon_data is specialised by the coordinate type, not the point type, so anyone using their own point type will have to provide their own polygon type. Is there some reason why I can't have polygon_data<my_point>? Again, making it easier to use std::container<my_point> would help.

Point type is a trait.

I also found little mention of winding direction in the documentation. I haven't checked whether the data I have winds consistently; what does unknown_winding actually do?

Forces a runtime evaluation of the winding direction when that information is needed.

As I guessed, contains(polygon,point) is very slow if done naively: the library's polygon concept (and the provided default implementation) have no way to determine whether a point lies within a polygon in better than O(N) time. Testing first with the bounding box makes it O(1) in the common case. So I tried to write a polygon type that would do this, something like this (but not exactly this!):

struct my_polygon: polygon_data { rectangle bbox; template <typename ITER> my_polygon(ITER begin, ITER end): polygon_data(begin,end), bbox(extents(*this)) {} };

bool contains(const my_polygon& poly, point_t pt) { return contains(poly.bbox,pt) && contains(poly,pt); }

Hmm, well that looks OK until the very last "contains"... no doubt someone will immediately spot the "right" way to do this. I ended up making contains() a member of my_polygon, and this worked reasonably well. Note that the extents() function does not work as written above: it takes a reference to a rectangle as an out parameter. center() does something similar. This seems wrong to me; returning a point or rectangle would be more conventional I think.

Since it is just as expensive to compute the bounding box of a polygon I left the bounding box optimization to the user.

** extents() and center() should return their results, rather than using an output reference.

Out parameters and equational reasoning have been discussed elsewhere in the review.

I have a fixed point type that I use for GPS coordinates (32 bits is good for lat/lng GPS positions, but 24 bits isn't) and using it with this library worked well. The Coordinate Concept page doesn't say much about the type requirements ("expected to be integral") and spelling out in more detail what is needed would be useful. In practice I must have already implemented everything that it needed.

Interesting. I provide default traits for coordinate concept, if these are sufficient for you all you need to do is specialize geometry_concept for your coordinate type.

However, I can't see any way to perform these boolean operations other than using the operators, and I think this is an ommission. If I were writing code that I expected someone else unfamiliar with the library to understand I would like the important calls to be conspicuous.

** The library should provide functions to perform the boolean operations, as well as operators, for the benefit of those who want to make their code more verbose.

The polygon_set_data objects have operator member functions that can be used instead, if you manually convert the inputs to polygon_set_data objects in user code.

I dislike the use of operators with integers for the grow/shrink operations. My concern is that this meaning is non-obvious, and since these operators are also defined for boolean operations, there is potential for error:

polygon_set a, b, i; ... for (int i = 0; i<10; ++i) { ... a -= b+i; // oops, forgot i is now an int }

I agree there is a potential for error. It is a judgement call and preference in this is very subjective.

Isotropic Style ---------------

I recall Luke describing his isotropic style on the list a long time ago, and the documentation would benefit from an explanation along those lines. One "FAQ" that it would need to address is the question of the performance of a run-time selection of X vs. Y compared to a compile-time selection in more conventional code.

I use the isotropic style extensively in the implementation details of algorithms in the library. If the user doesn't like it they generally have alternative APIs available to them that do not require it, and can ignore its existence except when setting up the point and rectangle traits.

Barend has also raised questions about the worse-case performance of Luke's line intersection algorithm, and it seems that Luke accepts that it is not optimal. Achieving the best possible algorithmic complexity is something that I would consider very important or essential for a Boost library. At the very least, Luke needs to document the complexity of his current algorithm and explain why he cannot do any better. The views of experts should be sought if this cannot be resolved by the review manager.

If Barend, or anyone, implements a fast, robust line intersection algorithm and licenses it under the boost license I can easily replace my own line intersection algorithm with the faster one. Implementing fast, robust line intersection is extremely difficult and time consuming. Our internal performance requirements are met by what I implemented.

In view of all this, I suggest that this library should be rejected for now. This will tell Barend that he still has an opportunity to present his library for review, and that it will be considered on a level playing field. If Barend's library is reviewed and found to be more complete, more performant and at least as usable as this library, then it should be accepted. On the other hand, if Barend's library is found to be deficient in some way (or is not submitted for review), then Luke will have an opportunity to resubmit an updated version of this library, which I anticipate should be accepted.

I don't believe it is necessary to position the decision as an either or GGL/Boost.Polygon proposition. Thanks, Luke

Fernando Cacciola wrote:

Hi Luke,

...

...

** The polygon_data type should be mutable (i.e. support things like push_back()), or a mutable version should be provided, or std::vector/list<point_data> should work with minimal traits specialisation.

The example custom_polygon.cpp shows the traits for a list<CPoint>. I could make all containers of points models of polygons_concept by default, but I wouldn't know which polygon concept the user prefers.

A mere container of points should be a model of the most general polygon concept (which is polygon_concept)

This would prevent a user from defining it to be (for example) a polygon_90_concept in their application, forcing them to declare a different type to be their model of polygon_90_concept. I have the example that shows how to make a container a model of polygon_concept. That should be enough help for users who wish to do so. Personally, I would not want a vector of points to automatically be a model of polygon because a vector of points is not a polygon most of the time, and in my view making it so would not be type safe. If I felt that vector of points should be a model of polygon my polygon_data type would simply be a vector and not a class encapsulating a vector.

...

...

I also found that polygon_data is specialised by the coordinate type, not the point type, so anyone using their own point type will have to provide their own polygon type. Is there some reason why I can't have polygon_data<my_point>? Again, making it easier to use std::container<my_point> would help.

Point type is a trait.

Can you elaborate in your response?

If I have

struct my_point { float x,y; }

How do I create a "polygon_data" that uses that point type?

AFAICT that is just not possible.

That is true. My polygon_data types are not parameterized on point type. If you want to use your own point type you will have to use your own polygon type. There is no particular reason that polygon_data is not parameterized on point type, I was trying to keep its implementation simple. I use my own point type internally in many instances, and there may be a dependency in the implementation details of some algorithm in which I know the polygon type is my own that I assume its point type is my own also.

...

...

** extents() and center() should return their results, rather than using an output reference.

Out parameters and equational reasoning have been discussed elsewhere in the review.

Yes, but I'm not sure what is your position regarding that. Can you clarify it?

I agree that it is better to have these functions return their result rather than have an input/output parameter. Originally I implemented each as returning my rectangle type and my point type respectively. I changed them to allow the user to get the output as their own data type. I could change them further to make them return an object that auto-casts to T if T is a model of rectangle or point concept. I prefer not to add generic casting operators to my point and rectangle types because this would lead to confusing syntax errors, so I would use some sort of expression object as suggested when this issue was previously discussed. This is a change I am perfectly willing to make if required. Thanks, Luke

Hi Luke,

Fernando Cacciola wrote:

...

(*) The library needs to distinguish lvalue-ness from write-ness: it is one thing to "reset" the X ccordinate of a point and one totally diferent is to get a non-const reference (lvalue) to it.

This general lack of "mutation" as opposed to "assignment" causes for example gross inefficiency in the operations that modify the vertices of a polygon (such as convolve, scale, transform, etc):

The functions that implement that, generate a new container with the modified points and then resets the point sequence within the input/output polygon. IMO this is nonesense (and a showstopper from a review POV). yet is it really just the conequence of lacking "lvalue" access to the vertices WITHIN a polygon.

This is a trade-off that I made intentionally. The rationale for not allowing references to member data of geometry objects is that a geometry object may not have such a data member. For example, a polygon may store its first point as a point and then subsequent points as offset pairs from the previous point, a rectangle may be represented as its center plus width and height and a point may be in polar coordinates convertible to cartesian in the traits specialization. My own manhattan polygon data type stores only one coordinate per vertex and has no point to get a non-const reference to. In this case I sacrificed performance for generality.

But you don't have to sacrifice anything: that's the whole point of generic programming. Just add the concepts that allow mutation of veritices (or at least assignment of vertices which is not even the same) and let the right types model it. Then distpatch your algorithms appropriatedly. What you said above is like justifying O(n) lookup in a vector just because a generlized container might not have random access.

...

(*) There is a lowercase "winding_direction" enum whith values like "clockwise_winding" and "counterclock_winding" (plus unknown), but then there is the "direction_1d_enum" with values of "CLOCKWISE" and "COUNTERCLOCKWISE" Not only that is confusing but it also boils down to inefficient code because the "winding" function returns CLOCKWISE|COUNTERCLOCKWISE yet the "polygon_traits<>::winding" code that is the actual implementation returns winding_direction. Since the actual numeric values mismatch there is an explicit conditional convertion:

return w == clockwise_winding = CLOCKWISE : COUNTERCLOCKWISE

(*) In fact, the problem above comes from the design of the fucntion winding(): if the actualt winding cannot be computed, it iself computes the area instead and uses its sign to second guess the winding.

IMO, that alternative calculation should be done by the user if and when it makes sense.

(*) In fact again, the problem above comes from the design of the function area(): there is a "point_sequence_area" that does the actual calculation and returns a signed value. But then area() returns the ABS of that, so a user would not be able to call area() as a robust way to compute the winding of a polygon as, well, winding() internally does.

IMO this is a mistake: the area() method should return the signed value and let the user do the abs() WHEN and IF makes sense.

I was trying to make providing the traits easier. Having a trait for winding is an optimization. I was trying to make it easy for users to specify that trait by returning that the winding of their polygon is not known at compile time. I undertand the existence of the "unknown_winding". That's not the problem. It is the lack of this in the rest of the API. Ther is no need for two windings enumerations IMO.

I expect the return of negative values from area() would be more surprising to the user than the fact that I created a special enum for use by the winding trait.

Yet even if it rally were more surprising for some users, the point is that you can get rid of the sign but you cannot put it back once it is lost. i.e., users can always do abs(area) but they can never figure out what the sign was before it got lost in the implementation without computing the winding or such. So, signed area is more general and should be the one provided by the library. Best -- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com

Fernando Cacciola wrote:

(*) I really don't like the use of overloading-on-concept as the main API element. Specially implemented via SFINAE as it is.

IMO, a much better design would be to a have basic traits that provides the fundamental building blocks, as the library is doing, for example via "point_traits<>", but then the derived functions be also provided as static members of a template class, say, point_concept<>

This is much better for a number of reasons:

A user can specialize the functions for their own data types in a snap. Currently is next to impossible. For instance, having the compiler call my own assign() for my own point type, when it happens to be a model of a mutable point, can be very very tricky.

A design based on many layers of specialzable classes is WAY more compiler friendly and hence much more easy for the programmer to spot mistakes such as constrains violations (wrong type) without concept checking.

Then, at the front end of the API, I would provide the overloaded versions as there are now as a top layer. This is in fact what the library is doing for those fundamental functions that are given directly by the traits class, but IMO it needs to do the same with all free functions, dispatching the actual implementation to the right specialization of the concept (i.e. free fucntions would be merely forwarding)

Finally, the library itself wouldn't use the overloaded free functions but the "real" member functions. This would make the code much more robust in the presence of ADL. Right now, there are countless places where unqualified calls to, say, assign(), set(), even "abs()", WILL cause ambiguities in many real world contexts.

This suggesting is similar to the previous API design. I found it was challenging to do so much typing. I agree that it would help with ADL problems, and it was my policy to use the internal functions when they were still part of the design. My goal was to show how a C++ concepts based API would look and feel in a real world C++ library that people can use now. I think that as a case study for C++ concepts Boost.Polygon is a very interesting piece of software with an important place in the ongoing discussion of C++ concept and for that reason it is important for it to be prominently exposed to the C++ community as a boost library. That is the intention of the design and submission to boost.

(*) In fact, that most opertations modify their arguments instead of producing new ones is odd, and in some cases just plain wrong (when the reference parameter is not even an input value)

Can you elaborate? I don't know which functions you are referring to here.

(*) The library is specifically 2D yet that fact isn't encoded in the namespace nor the identifies. This should be fixed as otherwise will conflict with future 3D libraries.

You foresee a different boost.polygon namespace?

(*) The library names something as "orientation". IMNSHO, in the context of polygos, orientation means something else (that which the library call direction instead). So, I would strongly suggest the rename it, to something like: axis_alignment (which is what it is).

I would prefer to keep the names the same. I don't believe people who are used to thinking of winding direction as orientation will be confused for long. Most users don't really understand winding at all, and power users who might think of it as orientation aren't the type who will be easily confused.

(*) some enums are named after "BLABLA_enum" and some after "BLABLA". that should be consistent... it would remove _enum

Those enums are usually wrapped by an encapsulating class. Their names are meant for internal use. The values are meant for users, and the names of the enum values tend to be straightforward.

(*)

I don't think it makes sense to name "point_data<>" with the "_data" postfix. I understand "_traits" etc... but point should be just point IMO.

I agree with you. I chose to be extra explicit so that people could not become confused about the different between a data type and what is a concept, which is easy to happen since concepts are a new style element to most users.

(*)

I dislike that there is scale and move not being merely convenience warppers of transform() (also there).

And I *really* dislike the existence of a scale_up() + scale_down() which are BOTH there simply because they take "integer" factors instead of a fraction (whether a rational number or a floating point). Also, scale down *secretly* uses a "rouding_policy", instead of taking it as argument.

IMO, there should be just scale(), which to add confusion already is but is really an "applicator" that takes a an scaling function object doing whatever and applying thee point's coordinate into it. Which is the same transform() does.

But, anyway, IMO there should be just one "scale" taking a floating point factor, or if you prefer, a rational number (expressed as separate numerator and denominator integer arguments for instance). The rounding policy would be given as optional aregument.

There is also the transformation<> (along with the transform() function), and the isotropic_scale_factor<>, which are naturally related to these scaling operators. IMO, these is overegineered and leaves the user with too many choices.

Originally there was a simpler design which implemented only isotropic_scale_factor based scaling, but it grew with additional requests from users to add scaling by integer and scaling by floating point. You are seeing the result of a legacy of internal use of the library.

(*) Likewise, polygon.hpp should be renamed since it is really the mother header of the library, including all others. I can imagine that it is called "polygon.hpp" since that's the name of the library which I expected to find on it stuff specifically related to a polygon data type or concept or such.

What do you suggest polygon.hpp be named?

(*)

Many classes have "inline" in the method definitions. This is completely unnecesary since in-class definitions are inline already. IMO this needs to be removed.

This happened primarily because functions that were free functions in name spaces moved to static member functions of templated structs and I neglected to remove the irrellevant inline declarations. If it is in the implementation details does it really matter?

(*)

There are some structs wrapping enums to make them type safe. That's useful, but then the structs store the enum value as int (or unsigned int depending on where you look), while a char would be enough.

This is true. I can likely change them to char without needing to change anything else and not break the functionality of the library.

...

- What is your evaluation of the documentation?

As many others said it really needs a good introduction that a newcomer can read to see what the library is, and perhaps more importantly, is NOT, about.

Also some tutorials, both on using the library out of the box with its own models and on using it on user-defined types.

And as some reviwers said, the documentation is way too focus on concepts and its needs to document models as well. In fact, I think most "junior" users won't be interested at all in adapating their own types but on just using the library with the types provided, so the documentation for the models should come first, and the concepts should go after in the chapter discussing adaptation.

This sounds like a good suggestion. Thanks, Luke

Fernando Cacciola wrote:

...

This suggesting is similar to the previous API design. I found it was challenging to do so much typing. I agree that it would help with ADL problems, and it was my policy to use the internal functions when they were still part of the design. My goal was to show how a C++ concepts based API would look and feel in a real world C++ library that people can use now. I think that as a case study for C++ concepts Boost.Polygon is a very interesting piece of software with an important place in the ongoing discussion of C++ concept and for that reason it is important for it to be prominently exposed to the C++ community as a boost library. That is the intention of the design and submission to boost.

Fair enough. As I said I think the current design is a stretch of current C++ but I can live with that, *provided* that you do the hard work of making it usable with mainstream compilers (i.e. adding workarounds, resolving ADL issues, fixing warnings, etc)

I'm fully committed to supporting all mainstream compilers (including adding workarounds for broken compilers when possible) as well as resolving issues people run into with ADL such as replacing all instances of set() with (set)() and fixing warnings in all mainstream compilers. I've fixed all instances of quite a few of the effective C++ warnings not that long ago and put a lot of work into making the code compile warning free in several versions of gcc and edg. I would plan on fixing all MSVC8 and 9 warnings before ever letting the library into boost because I don't want to read all the complaints about warnings anymore than the users want to read the warnings.

...

...

(*) In fact, that most opertations modify their arguments instead of producing new ones is odd, and in some cases just plain wrong (when the reference parameter is not even an input value)

Can you elaborate? I don't know which functions you are referring to here.

center() for example.

...

...

(*) The library is specifically 2D yet that fact isn't encoded in the namespace nor the identifies. This should be fixed as otherwise will conflict with future 3D libraries.

You foresee a different boost.polygon namespace?

It is easy to forsee someone wanting to integrate 3D polygons. Where would that be? It can't be merged within "boost::polygon" because it will most likely clash with your names, unless you names are made much less general (i.e. planar specific). So it will end up in say "boost::polygon_3d" or such.

But then there would be an unfair asymmetry.

This is actually a general issue with the library name, not just it's namespace: "Polygon" is too a broad a name... there can be in 2D, 3D, snapped to integer grids, or the floating point cartesian plane, they can have homogenerous coordinates, etc.. etc...

So, like many others said, you need to come up with a more specific name for the library. IMO, it should clearly express the two central constaints: 2D and integer coordinates. Have in mind that you *can* come up with something creative. Consider Spirit and Fusion for instance.

I really like the current name, but I suppose I can change it if needed. I'd like suggestions for names from the community. Its easy to shoot down a name, but not so easy to come up with a name that won't be shot down. I'd prefer a name that is descriptive to help people know what to expect of the library. Here's the result of my brainstorming: Boost.Shape Boost.Shapeshifter Boost.ipcg (Integer Planar Cartesion Geometry)

...

...

(*) some enums are named after "BLABLA_enum" and some after "BLABLA". that should be consistent... it would remove _enum

Those enums are usually wrapped by an encapsulating class. Their names are meant for internal use. The values are meant for users, and the names of the enum values tend to be straightforward.

Does that mean that they shouln't be named consistently? They are not even in a "detail" namespace, so it's not even evident that they are for internal use only (and even then they could be named consistently)

The ones that are wrapped by an encapsulating class are named <classname>_enum, where as the ones where it is the enum type itself that is intended for use is named without the _enum. Originally the class encapsulated enums where implemented with the enums as private member types and the constants as static const declarations of the class type. This however resulted in those constants being memory locations and runtime variables everwhere the compiler should have evaluated them at compile time because of the lack of constexpr. I changed the constants to enum values to force the compilers to do the right thing and treat them as constants. This forced me to move the enum declarations out of the classes, which is how we got to where we are today. I would prefer to have constexpr.

...

Originally there was a simpler design which implemented only isotropic_scale_factor based scaling, but it grew with additional requests from users to add scaling by integer and scaling by floating point. You are seeing the result of a legacy of internal use of the library.

OK, and what do you propose for Boost now? The current legacy design seems unnecesarilty confusing.

template <typename geometry_type, typename scale_factor_type> enable_if<..., void>::type scale(geometry_type &obj, scale_factor_type numerator, scale_factor_type denominator = 1); Scale_factor_type can be integer or floating point and we can scale down by integer factor of eg. 10 with scale(1, 10) without the need to convert 1/10 to floating point. I'd be very dissapointed in any compiler that fails to compile away the (value / 1) division identity property sub-expression tree. I don't think that the isotropic_scale_factor is currently used. It was part of the original design which turned out to be not very needed by my internal user base. Thanks, Luke