Re: [Boost-bugs] [Boost C++ Libraries] #10868: Intersecting integer polygons produces incorrect or self-intersecting result

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #10868: Intersecting integer polygons produces incorrect or self-intersecting result
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-05-27 21:27:18

#10868: Intersecting integer polygons produces incorrect or self-intersecting
result
-------------------------------+---------------------------
  Reporter:  starinshak1@…     |      Owner:  barendgehrels
      Type:  Bugs              |     Status:  new
 Milestone:  To Be Determined  |  Component:  geometry
   Version:  Boost 1.57.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+---------------------------

Comment (by starinshak1@…):

 Replying to [comment:2 mkaravel]:

 Hi Menelaos,

 The polygons in my original example are CCW and closed. In testing, I
 initialize them with an open string of coordinates can call
 boost::geometry::correct to close them.

 Using the 1.58.0 release of Boost.Geometry, I now reproduce your findings
 for this problem: the polygon resulting from the intersection is self-
 intersecting for int32_t coordinates but non-self-intersecting for int64_t
 coordinates. However, when you plot the result, it is incorrect for both
 integer types (and incorrect in different ways).

 I have another example that further compounds this error:
 POLYGON((241774944 270613768, 249104265 268648604, 258263822 277993222,
 262822082 304885727, 253206525 344982011, 240074874 272654983))
 POLYGON((225182076 225182076, 292290940 225182076, 292290940 292290940,
 225182076 292290940))

 These are also CCW-oriented polygons. I now get the reverse behavior as
 the original example:

 If I intersect them using int32_t coordinates, the result
 POLYGON((252873436 292290940, 240074874 272654983, 241774944 270613768,
 249104265 268648604, 258263822 277993222, 268109663 336081032, 252873436
 292290940))
 does NOT self-intersect.

 If I intersect them using int64_t coordinates, the result
 POLYGON((240075109 272653826, 240074874 272654983, 241774944 270613768,
 249104265 268648604, 258263822 277993222, 262823538 304883653, 240075109
 272653826))
 does self-intersect.

 As before, the polygon resulting from the intersection is not correct.

 Dave

 > Hi.
 >
 > AFAIC, the macro BOOST_GEOMETRY_NO_ROBUSTNESS has nothing to do with
 your findings, as rescaling is only activated for floating-point
 coordinates.
 >
 > I tried your example polygons, and I could reproduce the problem when
 the coordinate type is int32_t, but could not reproduce it for int64_t.
 Could you please check again against the latest Boost.Geometry version in
 the develop branch, and also report the output polygons you get?
 >
 > My understanding is that your polygons are CCW and open. Correct?
 >
 > Menelaos

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10868#comment:3>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.