50567

Geometry, intersection

Question:

I have a problem. I would like to intersect a quad with a quad.

int main(){ typedef boost::geometry::model::point_xy<double> TBoostPoint; typedef boost::geometry::model::polygon<TBoostPoint> TBoostPoly; TBoostPoint point; TBoostPoly firstPoly, secondPoly; boost::geometry::read_wkt("POLYGON( (1.504477611940313, 3.761194029850755), (1.504477611940305, 3.573134328358203), (1.316417910447765, 3.573134328358206), (1.316417910447769, 3.761194029850752))", firstPoly); boost::geometry::read_wkt("POLYGON( (1.504477611940313, 3.761194029850755), (1.504477611940305, 3.573134328358203), (1.316417910447765, 3.573134328358206), (1.316417910447751, 3.761194029850769))", secondPoly); std::vector<TBoostPoly> outPoly; boost::geometry::intersection(firstPoly,secondPoly,outPoly); }

outPoly - is empty, but it not so.

Answer1:

There were 2 main issues.

The output is undefined because the input is invalid.

<ol><li>

The input WKT specifies a lot of invalid inner rings (consisting of single points), instead of what you expected, a single outer ring of 5 points (excl. closing point). Fix it:

bg::read_wkt("POLYGON(( 1.504477611940313 3.761194029850755, 1.504477611940305 3.573134328358203, 1.316417910447765 3.573134328358206, 1.316417910447769 3.761194029850752))", first); bg::read_wkt("POLYGON(( 1.504477611940313 3.761194029850755, 1.504477611940305 3.573134328358203, 1.316417910447765 3.573134328358206, 1.316417910447751 3.761194029850769))", second); </li> <li>

Boost Geometry assumes throughout that you never make errors against the documented preconditions. If you read in the polygon concept page and preconditions for intersection you'll see thew full list¹.

If you don't, you get no friendly errors, just silent failure, corruption or just wrong answers. Yeah. That's bad.

What's worse, BGeo didn't even have a is_valid facility to test the bulk of requirements until Boost 1_57 (IIRC). The good news is, if you upgrade to this version or later your life will be much simpler.

</li> </ol>

In this case you would have learned that the polygons weren't properly closed:

<strong><kbd><a href="http://coliru.stacked-crooked.com/a/99a089782c642374" rel="nofollow">Live On Coliru</a></kbd></strong>

#include <boost/geometry.hpp> #include <boost/geometry/geometries/point_xy.hpp> #include <boost/geometry/geometries/polygon.hpp> #include <boost/geometry/geometries/multi_polygon.hpp> #include <boost/geometry/io/io.hpp> #include <boost/geometry/algorithms/intersection.hpp> #include <boost/geometry/algorithms/correct.hpp> #include <boost/geometry/algorithms/is_valid.hpp> namespace bg = boost::geometry; int main(){ typedef bg::model::d2::point_xy<double> TPoint; typedef bg::model::polygon<TPoint> TPoly; TPoly first, second; bg::read_wkt("POLYGON(( 1.504477611940313 3.761194029850755, 1.504477611940305 3.573134328358203, 1.316417910447765 3.573134328358206, 1.316417910447769 3.761194029850752))", first); bg::read_wkt("POLYGON(( 1.504477611940313 3.761194029850755, 1.504477611940305 3.573134328358203, 1.316417910447765 3.573134328358206, 1.316417910447751 3.761194029850769))", second); std::string reason; // polys not closed! if (!bg::is_valid(first, reason)) std::cout << "First polygon not valid: " << reason << "\n"; if (!bg::is_valid(second, reason)) std::cout << "Second polygon not valid: " << reason << "\n"; bg::correct(first); bg::correct(second); // no more output! if (!bg::is_valid(first, reason)) std::cout << "First polygon not valid: " << reason << "\n"; if (!bg::is_valid(second, reason)) std::cout << "Second polygon not valid: " << reason << "\n"; std::vector<TPoly> out; bg::intersection(first, second, out); for (auto& g : out) std::cout << "\nresult: " << bg::wkt(g) << "\n"; }

Prints:

First polygon not valid: Geometry is defined as closed but is open Second polygon not valid: Geometry is defined as closed but is open

Oops. The geos weren't closed! correct(poly) fixes this for us on auto-pilot:

result: POLYGON((1.50448 3.57313,1.31642 3.57313,1.31642 3.76119,1.50448 3.76119,1.50448 3.57313)) <hr />

¹ outer ring must be counter clockwise, inner cw, polys must be closed... stuff like that.

Recommend

  • PHP using regular expression to parse query string
  • Convert XML to/from JSON in Java (without extra and elements)
  • How to stop Android AlarmManager when there is a manual system time change?
  • Native alarm clock notification on iOS
  • Three-way xor-like function
  • Concat in an empty array in Javascript
  • how to calculate shannon entropy of byte bigrams
  • KRL RSS parser: Handle encoding issues?
  • Simple way to get more sensible colors in gscatter
  • Javascript to Excel: bad performance for lack of “range” method
  • Is the scope of a variable initialized in a for loop declaration actually more than just block scope
  • Get Distinct rows from a result of JOIN in SQL Server
  • How do I conditionally select a field from one of two tables?
  • Java Date object constructor for getting string is deprecated
  • Regex for Specific Tag
  • How can we prepend rows to a react native list-view?
  • hibernate sets dirty flag (and issues update) even though client did not change value
  • Basic many-to-many left join query
  • Find group of records that match multiple values
  • Android Studio Can't Find tools.jar
  • SonarQube: Cannot deactivate rule with missing quality profile
  • How to detect interior vertices in groups of 2d polygons? (E.g. ZIP Codes to determine a territory)
  • How to generate and display a QR Code in ionic 2
  • What's the purpose of QString?
  • Jackson Parser: ignore deserializing for type mismatch
  • PHP buffered output depending on server setting?
  • Functions in global context
  • Atlas images wrong size on iPad iOS 9
  • Sails.js/waterline: Executing waterline queries in toJSON function of a model?
  • How reduce the height of an mschart by breaking up the y-axis
  • Is possible to count alias result on mysql
  • Check if a string to interpolate provides expected placeholders
  • Deserializing XML into class C#
  • Redux, normalised entities and lodash merge
  • Do create extension work in single-user mode in postgres?
  • Function pointer “assignment from incompatible pointer type” only when using vararg ellipsis
  • Traverse Array and Display in markup
  • VB.net deserialize, JSON Conversion from type 'Dictionary(Of String,Object)' to type '
  • python draw pie shapes with colour filled
  • How to Embed XSL into XML