Hi, I am reviewing the library and trying to adapt some of the shapelib examples that don't seem to be included in the formal_review distribution. Any reason why the latlong.hpp is not included ? Without the typedefs the examples are harder to get working e.g. ring_ll_deg or area ring regards
Hi Jose,
I am reviewing the library and trying to adapt some of the shapelib examples that don't seem to be included in the formal_review distribution.
Any reason why the latlong.hpp is not included ?
Because the whole geographic coordinate system including projections is moved to an extension, they're indeed not in the formal review distribution. Sorry for that. You can still use them though, getting them from our SVN or from boost sandbox (the last option is probably inconvenient as it uses distributions from different dates). The shapelib examples are also not there, for Formal Review we preferred to have minimal dependence on external libraries. But here the same, they are not thrown away, still available. Regards, Barend
I am reviewing the library and trying to adapt some of the shapelib examples that don't seem to be included in the formal_review distribution.
Any reason why the latlong.hpp is not included ?
Because the whole geographic coordinate system including projections is moved to an extension, they're indeed not in the formal review distribution. Sorry for that. You can still use them though, getting them from our SVN or from boost sandbox (the last option is probably inconvenient as it uses distributions from different dates).
What is the link for your SVN ? I think the key extensions like this one should be part of the library. I also think there should be an example using GIL. There are several examples but all the SOCI ones I feel they are irrelevant because they add another external dependency to use them and what SOCI does is not relevant to show the examples regards
Without the typedefs for point_ll_XX many examples (even in the main page) are broken, correct ? I think this is a serious issue, because the main use for the library is for non-cartesian geometries, so if its not easy anymore then what is the value of using the library ? ------------------------------------------------------------------ We now show that it is also possible to use non-Cartesian points. When then an algorithm such as distance is used the library "feels" that it is handling geographic points and calculates the distance over the globe, in meters: point_ll_deg amsterdam, paris; parse(amsterdam, "52 22 23 N", "4 53 32 E"); parse(paris, "48 52 0 N", "2 19 59 E"); std::cout << "Distance A'dam-Paris: " << distance(amsterdam, paris) / 1000.0 << " kilometers " << std::endl;
Hi Jose, Jose wrote:
Without the typedefs for point_ll_XX many examples (even in the main page) are broken, correct ?
No, I think you're looking at the wrong page. This is the main page for Formal Review: http://geometrylibrary.geodan.nl/formal_review/ There are no point_ll samples currently in the distribution. As far as I know there is nothing broken in the distribution. Regards, Barend
Without the typedefs for point_ll_XX many examples (even in the main page) are broken, correct ?
No, I think you're looking at the wrong page. This is the main page for Formal Review: http://geometrylibrary.geodan.nl/formal_review/
There are no point_ll samples currently in the distribution. As far as I know there is nothing broken in the distribution.
Sorry, I got confused with the different pages
Hi again, Jose wrote:
What is the link for your SVN ? I think the key extensions like this one should be part of the library.
I'll send it you. But if you've the right page things will be more clear. The geometry library is a large library. We choose for review for a solid subset of it, the kernel. Projections (~90 sources) would be too much. GIS would be too much. The extension model works quite well to organize things in different parts. But the geographic coordinate system is in an extension, included in the distribution. I yesterday wrote
they're indeed not in the formal review distribution but that was in fact about the point_ll_deg, the algorithms for distance over the earth are there, e.g. used in the 07 graph route extension. Sorry for the confusion, I think if you've the right main page, it will be more clear.
I also think there should be an example using GIL.
We did think about that but need an extension, or something, to draw lines or polygons in GIL. But yes, it is a good idea.
There are several examples but all the SOCI ones I feel they are irrelevant because they add another external dependency to use them and what SOCI does is not relevant to show the examples
Some people use databases and geometry, so this shows one way to do that. People not doing things with them can skip them. Regards, Barend
Hi, I'm trying to run a test that will take the boolean difference of two polygons, but haven't been able to find an explicit difference function. So I've tried instead to get the difference by taking: A & !B (the intersection of A and the negation of B, where negation is done by reversing the winding.) Anyway, when I tried this I got a crash when the winding was reversed on B. I've attached a text with the test. Regards, Brandon // //! Copyright © 2008-2009 //! Brandon Kohn // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // #ifndef GENERATIVE_GEOMETRY_GGL_REVIEW_TESTBOOLEANS_HPP #define GENERATIVE_GEOMETRY_GGL_REVIEW_TESTBOOLEANS_HPP #pragma once #include <boost/test/unit_test.hpp> #include <boost/test/floating_point_comparison.hpp> ////////////////////////////////////////////////////////////////////////// #include <sstream> #include <fstream> #include <ggl/util/write_dsv.hpp> #include <ggl/extensions/gis/io/wkt/read_wkt.hpp> #include <ggl/extensions/gis/io/wkt/write_wkt.hpp> #include <ggl/geometries/point_xy.hpp> #include <ggl/geometries/box.hpp> #include <ggl/geometries/linear_ring.hpp> #include <ggl/geometries/polygon.hpp> #include <ggl/geometries/geometries.hpp> #include <ggl/algorithms/correct.hpp> #include <ggl/algorithms/intersection.hpp> #include <ggl/algorithms/area.hpp> #include <ggl/algorithms/length.hpp> #include <ggl/algorithms/num_points.hpp> #include <ggl/algorithms/simplify.hpp> #include <ggl/strategies/strategies.hpp> #define TEST_WITH_SVG 1 #if(TEST_WITH_SVG) #include "svg_mapper.hpp" //might need to change this back to your <testutil...path> #endif namespace { template <typename OutputType, typename G1, typename G2> void test_intersection( int caseid, G1 const& g1, G2 const& g2, int expected_count = 0, int expected_point_count = 0, double expected_length_or_area = 0 ) { static const bool is_line = ggl::geometry_id<OutputType>::type::value == 2; std::vector<OutputType> clip; ggl::intersection_inserter<OutputType>(g1, g2, std::back_inserter(clip)); double length_or_area = 0; int n = 0; for (typename std::vector<OutputType>::const_iterator it = clip.begin(); it != clip.end(); ++it) { // instead of specialization we check it run-time here length_or_area += is_line ? ggl::length(*it) : ggl::area(*it); // Simplify to get a correct point-count without duplicate points // (note that overlay might be adapted to avoid duplicates) OutputType simplified; ggl::simplify(*it, simplified, 0.0001); n += ggl::num_points(simplified); //std::cout << std::endl << "case " << caseid << " "; //std::cout << ggl::dsv(*it) << std::endl; } BOOST_CHECK_EQUAL(clip.size(), expected_count); BOOST_CHECK_EQUAL(n, expected_point_count); BOOST_CHECK_CLOSE(length_or_area, expected_length_or_area, 0.001); #if defined(TEST_WITH_SVG) { std::ostringstream filename; filename << "intersection" << caseid << ".svg"; std::ofstream svg(filename.str().c_str()); svg_mapper<typename ggl::point_type<G2>::type> mapper(svg, 500, 500); mapper.add(g1); mapper.add(g2); mapper.map(g1, is_line ? "opacity:0.6;stroke:rgb(0,0,255);stroke-width:5" : "opacity:0.6;fill:rgb(0,0,255);stroke:rgb(0,0,0);stroke-width:1"); mapper.map(g2, "opacity:0.6;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1"); for (typename std::vector<OutputType>::const_iterator it = clip.begin(); it != clip.end(); ++it) { mapper.map(*it, "opacity:0.6;fill:none;stroke:rgb(255,0,0);stroke-width:5"); } } #endif } template <typename OutputType, typename G1, typename G2> void test_one( int caseid, std::string const& wkt1, std::string const& wkt2, int expected_count = 0, int expected_point_count = 0, double expected_length_or_area = 0 ) { G1 g1; ggl::read_wkt(wkt1, g1); G2 g2; ggl::read_wkt(wkt2, g2); test_intersection<OutputType>(caseid, g1, g2, expected_count, expected_point_count, expected_length_or_area); } } template <typename Point> void test_ops() { typedef ggl::linestring< Point > linestring; typedef ggl::polygon< Point> polygon; typedef ggl::box< Point > box; std::string p5 = "POLYGON((37.29449462890625 1.7902572154998779,37.000419616699219 1.664225697517395,37.140213012695313 1.3446992635726929,50.974888957147442 -30.277285722290763,57.297810222148939 -37.546793343968417,41.590042114257813 -7.2021245956420898,40.6978759765625 -5.4500408172607422,40.758884429931641 -5.418975830078125,42.577911376953125 -4.4901103973388672,42.577877044677734 -4.4900407791137695,42.699958801269531 -4.4278755187988281,46.523914387974358 -8.5152102535033496,47.585065917176543 -6.1314922196594779,45.389434814453125 -4.5143837928771973,46.296027072709599 -2.4984308554828116,37.43402099609375 1.470055103302002,37.29449462890625 1.7902572154998779))"; //! p7 is p6 in reverse. std::string p6 = "POLYGON((42.399410247802734 1.4956772327423096,42.721500396728516 2.2342472076416016,42.721500396728516 3.6584999561309814,51.20102152843122 7.1738039562841562,51.370888500897557 7.4163459734570729,37.43402099609375 1.470055103302002,37.29449462890625 1.7902572154998779,37.000419616699219 1.664225697517395,37.140213012695313 1.3446992635726929,36.954700469970703 1.2597870826721191,26.472516656201325 -3.5380830513658776,27.069889344709196 -4.2926591211028242,30.501169204711914 -2.3718316555023193,32.708126068115234 -2.3611266613006592,32.708126068115234 -2.3611700534820557,32.708168029785156 -2.3611698150634766,32.718830108642578 -4.3281683921813965,29.135100397190627 -8.9262827849488211,29.619997024536133 -9.5368013381958008,30.339155197143555 -8.9838371276855469,30.670633316040039 -8.8180980682373047,30.896280288696289 -9.1206979751586914,30.207040612748258 -10.275926149505661,30.947774887084961 -11.208560943603516,31.669155120849609 -10.653837203979492,32.000633239746094 -10.488097190856934,32.226280212402344 -10.790698051452637,31.682494778186321 -12.133624901803865,32.274600982666016 -12.879127502441406,32.998821258544922 -12.323249816894531,33.339523315429688 -12.147735595703125,33.566280364990234 -12.450697898864746,33.164891643669634 -14.000060288415174,33.598796844482422 -14.546377182006836,34.328716278076172 -13.992490768432617,34.658355712890625 -13.81736946105957,34.886280059814453 -14.120697975158691,34.634240447128811 -15.85007183479255,34.931102752685547 -16.223842620849609,35.656356811523438 -15.66030216217041,35.963497161865234 -15.476018905639648,37.326129913330078 -17.190576553344727,38.823680877685547 -16.296066284179688,39.966808319091797 -17.625011444091797,40.800632476806641 -17.208097457885742,41.821544647216797 -19.211688995361328,41.988733475572282 -19.945838749437218,57.524304765518266 -37.807195733984784,41.590042114257813 -7.2021245956420898,40.6978759765625 -5.4500408172607422,40.758884429931641 -5.418975830078125,42.577911376953125 -4.4901103973388672,42.577877044677734 -4.4900407791137695,42.699958801269531 -4.4278755187988281,46.559533858616469 -8.435196445683264,47.604561877161387 -6.087697464505224,45.389434814453125 -4.5143837928771973,46.695858001708984 -1.6093428134918213,47.263670054709685 -1.784876824891044,47.830955505371094 -0.69758313894271851,48.43512638981781 -0.81299959072453376,49.071769542946825 0.61489892713413252,43.764598846435547 0.93951499462127686,43.644271850585938 0.96149998903274536,42.399410247802734 1.4956772327423096))"; std::string p7 = "POLYGON((43.644271850585938 0.96149998903274536,43.764598846435547 0.93951499462127686,49.071769542946825 0.61489892713413252,48.43512638981781 -0.81299959072453376,47.830955505371094 -0.69758313894271851,47.263670054709685 -1.784876824891044,46.695858001708984 -1.6093428134918213,45.389434814453125 -4.5143837928771973,47.604561877161387 -6.087697464505224,46.559533858616469 -8.435196445683264,42.699958801269531 -4.4278755187988281,42.577877044677734 -4.4900407791137695,42.577911376953125 -4.4901103973388672,40.758884429931641 -5.418975830078125,40.6978759765625 -5.4500408172607422,41.590042114257813 -7.2021245956420898,57.524304765518266 -37.807195733984784,41.988733475572282 -19.945838749437218,41.821544647216797 -19.211688995361328,40.800632476806641 -17.208097457885742,39.966808319091797 -17.625011444091797,38.823680877685547 -16.296066284179688,37.326129913330078 -17.190576553344727,35.963497161865234 -15.476018905639648,35.656356811523438 -15.66030216217041,34.931102752685547 -16.223842620849609,34.634240447128811 -15.85007183479255,34.886280059814453 -14.120697975158691,34.658355712890625 -13.81736946105957,34.328716278076172 -13.992490768432617,33.598796844482422 -14.546377182006836,33.164891643669634 -14.000060288415174,33.566280364990234 -12.450697898864746,33.339523315429688 -12.147735595703125,32.998821258544922 -12.323249816894531,32.274600982666016 -12.879127502441406,31.682494778186321 -12.133624901803865,32.226280212402344 -10.790698051452637,32.000633239746094 -10.488097190856934,31.669155120849609 -10.653837203979492,30.947774887084961 -11.208560943603516,30.207040612748258 -10.275926149505661,30.896280288696289 -9.1206979751586914,30.670633316040039 -8.8180980682373047,30.339155197143555 -8.9838371276855469,29.619997024536133 -9.5368013381958008,29.135100397190627 -8.9262827849488211,32.718830108642578 -4.3281683921813965,32.708168029785156 -2.3611698150634766,32.708126068115234 -2.3611700534820557,32.708126068115234 -2.3611266613006592,30.501169204711914 -2.3718316555023193,27.069889344709196 -4.2926591211028242,26.472516656201325 -3.5380830513658776,36.954700469970703 1.2597870826721191,37.140213012695313 1.3446992635726929,37.000419616699219 1.664225697517395,37.29449462890625 1.7902572154998779,37.43402099609375 1.470055103302002,51.370888500897557 7.4163459734570729,51.20102152843122 7.1738039562841562,42.721500396728516 3.6584999561309814,42.721500396728516 2.2342472076416016,42.399410247802734 1.4956772327423096,43.644271850585938 0.96149998903274536))"; test_one<polygon, polygon, polygon>(2, p5, p7, 0, 0, 0); } BOOST_AUTO_TEST_CASE( TestBooleanOperations ) { test_ops< ggl::point_xy<double> >(); } #endif
Hi Brandon, Brandon Kohn wrote:
I'm trying to run a test that will take the boolean difference of two polygons, but haven't been able to find an explicit difference function. So I've tried instead to get the difference by taking: A & !B (the intersection of A and the negation of B, where negation is done by reversing the winding.) Anyway, when I tried this I got a crash when the winding was reversed on B. I've attached a text with the test.
Thanks for stressing our library to its limits. The exception you reported does happen indeed if you input a reversed polygon, invalid input. On the normal case it didn't throw (but results are, also then, not correct). I know that it should be handled correctly, also in reverse cases. The exception is solved now. That will not say that the numerical FP behaviour (probably why you test this) is solved, I'm investigating this further today. As there are also various other messages to be answered, I come back to this, probably tomorrow. Anyway, I'm glad with this case. Regards, Barend
Barend Gehrels wrote:
Thanks for stressing our library to its limits. The exception you reported does happen indeed if you input a reversed polygon, invalid input. On the normal case it didn't throw (but results are, also then, not correct). I know that it should be handled correctly, also in reverse cases. The exception is solved now. That will not say that the numerical FP behaviour (probably why you test this) is solved, I'm investigating this further today. As there are also various other messages to be answered, I come back to this, probably tomorrow.
I wouldn't call this test stressing the library to its limits. This operation is on two fairly ordinary small scale isovists (visibility polygons). As for reversed inputs being invalid, this doesn't make sense in the context that the negation operation creates a reverse of a polygon. This is how the boolean difference is defined (at least one way). How do you do the difference operation in GGL? Regards, Brandon
I wouldn't call this test stressing the library to its limits. This operation is on two fairly ordinary small scale isovists (visibility polygons). As for reversed inputs being invalid, this doesn't make sense in the context that the negation operation creates a reverse of a polygon. This is how the boolean difference is defined (at least one way). How do you do the difference operation in GGL? This is explained on that web-page I referred to yesterday, and touched in previous discussions with Luke. Summary: it is not yet available as a separate function but the operation itself is supported by the algorithm, we have to walk through the input with iterators, sometimes forward, sometimes reverse.
I cannot yet respond on isovists because it is still being researched. Barend
Barend Gehrels wrote:
I wouldn't call this test stressing the library to its limits. This operation is on two fairly ordinary small scale isovists (visibility polygons). As for reversed inputs being invalid, this doesn't make sense in the context that the negation operation creates a reverse of a polygon. This is how the boolean difference is defined (at least one way). How do you do the difference operation in GGL? This is explained on that web-page I referred to yesterday, and touched in previous discussions with Luke. Summary: it is not yet available as a separate function but the operation itself is supported by the algorithm, we have to walk through the input with iterators, sometimes forward, sometimes reverse.
My question must have confused you. I wasn't asking how the algorithm works. I'm asking how you have tested the difference operation, i.e. what methods do you call and what are the forms of the inputs? The documentation says that difference is supported.
I cannot yet respond on isovists because it is still being researched.
I wasn't asking you about isovists. I was just telling you how these polygons I used were created. They are simple polygons which form boundary of the visible area from a source point. Perhaps it's best if we don't cloud the issue with worry about isovists. For now let's focus on how taking a difference works. Regards, Brandon
Hi Brandon,
I wouldn't call this test stressing the library to its limits. This operation is on two fairly ordinary small scale isovists (visibility polygons). As for reversed inputs being invalid, this doesn't make sense in the context that the negation operation creates a reverse of a polygon. This is how the boolean difference is defined (at least one way). How do you do the difference operation in GGL? This is explained on that web-page I referred to yesterday, and touched in previous discussions with Luke. Summary: it is not yet available as a separate function but the operation itself is supported by the algorithm, we have to walk through the input with iterators, sometimes forward, sometimes reverse.
My question must have confused you. I wasn't asking how the algorithm works. I'm asking how you have tested the difference operation, i.e. what methods do you call and what are the forms of the inputs? The documentation says that difference is supported. I answered: "it is not yet available as a separate function". OK, new more concrete answer: I tested it the way you did, so with reverse polygons, I copied them in my testprogram.
Where says the documentation actually that difference is implemented? I think it states that it is supported by the algorithm, but not implemented as a separate function... Like I said above. Regards, Barend
Barend Gehrels wrote:
Where says the documentation actually that difference is implemented? I think it states that it is supported by the algorithm, but not implemented as a separate function... Like I said above.
It's the first line at: http://geometrylibrary.geodan.nl/formal_review/sets.html Introduction The GGL implementation of the algorithms intersection, union, difference and symmetric difference is based on set theory (a.o. http://en.wikipedia.org/wiki/Set_(mathematics)).
Brandon Kohn wrote:
Barend Gehrels wrote:
Where says the documentation actually that difference is implemented? I think it states that it is supported by the algorithm, but not implemented as a separate function... Like I said above.
It's the first line at:
http://geometrylibrary.geodan.nl/formal_review/sets.html
Introduction The GGL implementation of the algorithms intersection, union, difference and symmetric difference is based on set theory (a.o. http://en.wikipedia.org/wiki/Set_(mathematics)). OK, sorry about that. It is true. I wrote that page one week ago, during the review, as additional doc, and it gives the necessary theoretical background. It *is or will be* (depending how you consider it) implemented like that but *not yet* as a separate function. It is written in the lower part of that page but not in the first line.
Sorry about the confusion, and (I now understand better) also about my remark about invalid input, I understand the confusions now, you are right to test like that. Barend
Barend Gehrels wrote:
Hi Brandon, I answered: "it is not yet available as a separate function". OK, new more concrete answer: I tested it the way you did, so with reverse polygons, I copied them in my testprogram.
Your answer has confused me. Why did you say my using reverse polygons was invalid input when this was how you tested it?
Hi list, Herewith explanations and backgrounds about this report this morning. Brandon, thanks for sending it.
I'm trying to run a test that will take the boolean difference of two polygons, but haven't been able to find an explicit difference function. So I've tried instead to get the difference by taking: A & !B (the intersection of A and the negation of B, where negation is done by reversing the winding.) Anyway, when I tried this I got a crash when the winding was reversed on B. I've attached a text with the test.
Both A and B were reversed, so in fact !A & !B was tested in the first case, and !A & B in the second case. The library does not test orientation, and that is on purpose. This behaviour is the same for self-intersections which are also not tested during intersections on purpose. The GGL is original built with OGC conventions in mind, polygons are clockwise, closed and non-self-intersecting. We added support for orientation (clockwise, counter clockwise or undetermined) and here the test was done with a polygon defined clockwise. The input should therefore be clockwise. GGL is not testing if it is really clockwise, on purpose, for performance reasons. When using the "undetermined" option, it should be tested (and reversed is necessary). However, that is currently not yet there (though trivial) because the counter clockwise option is also not there yet, they will both be applied when we add the (symmetric) difference. On A & B the behaviour is correct. As explained earlier, A&!B is not yet supported but will be. Theoretically and conceptually it is the same as A & reversed(B), but apparently we have to make a few more changes than only apply the reverse iterator, especially in paths to be taken. A&!B were not included in the submission, and therefore they are not tested (besides one simple case to verify conceptually). It is therefore not strange and does not really surprise me that if reverse polygons are tested now, errors are reported, you might get others, this is untested, valid input is assumed. So, having all information now, you should currently test with clockwise oriented polygons (so contrary to what I said earlier today). We will implement the difference (A&!B) and symmetric difference (A xor B), we will implement intersections for counter clockwise polygons, but in this submission it is not and we knew that beforehand. I wanted to research this case further, because of the small differences in input coordinates in this testcase, resulting in a difference in behaviour of our algorithm using float, double and long double. I therefore worked out the GMP and CLN types in the intersections. As I mailed earlier these high precision arithmetic types were in area, centroid and a few other algorithms but not yet in intersections. That is done now. Using GMP the behaviour is again different, all because these differences in input data (normally they are, of course, the same). Both double and GMP give the same output, but there are intersection points detected in the GMP/CLN which are not in the double version. This is why I mentioned "challenging conditions" above (and "to the limits"); I didn't mean the two reversed polygons of course (at that moment I didn't know that). This testcase is interesting because it shows differences detected intersection points (not in intersected polygons). In GMP and in CLN they are exactly the same, in float, double and long double they are all a little different amongst each other. Still, they give the same output polygon with this testcase. Again, about robustness, we *are *aware of the problems which might occur and we have our approach, using high precision arithmetics to avoid these from happening, either in coordinate type, or only in the calculations. In summary, our robustness approach, using GMP and CLN, have be applied easily, is done today. On valid input, nothing goes wrong. On invalid input, things go wrong on purpose, GGL contains functions to correct wrong windings (ggl::correct). Regards, Barend
participants (3)
-
Barend Gehrels -
Brandon Kohn -
Jose