Geometry Boost List: [geometry] union of 2 polygons is wrong.AND an intersect bug

Subject: [geometry] union of 2 polygons is wrong.AND an intersect bug
From: Zachary Deretsky (zach.deretsky_at_[hidden])
Date: 2012-01-29 17:19:07

Barend,
thank you for taking a quick action.
I hope your cross product is using long long rather than doubles.

I bumped into another bug when I was trying to find out whether a point is
on a line, here is the code:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/foreach.hpp>

int main()
{
  typedef boost::geometry::model::d2::point_xy<int> point_xy;
  typedef boost::geometry::model::linestring<point_xy > line;

  line line1, line2;

  boost::geometry::read_wkt("LINESTRING(100 10, 0 10)", line1);
  boost::geometry::read_wkt("LINESTRING(50 10, 50 10)", line2);

  std::cout << "line1 " << boost::geometry::dsv(line1) << std::endl;
  std::cout << "line2 " << boost::geometry::dsv(line2) << std::endl;

  if(boost::geometry::intersects(line1, line2)) {
    std::cout << "line1 intersects line2" << std::endl;
    return 0;
  } else {
    std::cout << "BUG: line1 DOES NOT intersect line2" << std::endl;
    return 1;
  }

  return 0;
}

Thanks, Zach.

On Sat, Jan 28, 2012 at 11:04 AM, Barend Gehrels <barend_at_[hidden]> wrote:

> Hi Zachary,
>
> On 16-1-2012 0:55, Zachary Deretsky wrote:
>
>> Since at Aditazz we chose to utilize boost geometry it will be very
>> useful for us to know, which operations are guaranteed to be safe for which
>> objects with integer coordinates with abs values less than 2^30.
>>
>
> The sample you sent on this list calculating a union based on polygons
> with large integer coordinates is running correctly now.
>
> This is the result of my action to inventarize unsafe (w.r.t. large
> integers) actions. I've updated:
> - area, the area-result-type is a double (even for integer coordinates),
> and was assigned to a double, but coordinates were not casted. This is now
> corrected using the cross-product which at one place verifies this
> - (side: was already promoted, but uses cross-product now)
> - centroid, same
> - segment-intersection (three sources), now also using cross-product
> - correct, which is using area, but the internal predicate was not using
> area-result-type but coordinate_type. This took me a while. But fixed now
> (correct was not in your sample but I usually add it for my own tests).
>
>
> This makes the sample run. I've added large_integer tests to area/centroid
> (committed) and within (still to commit).
>
> The plan was to integrate cross_product (was in extensions) anyway, so
> this was a good moment to do this. I realize that it is not only
> inventarizing but also correcting, but this was the easiest way. It is
> sometimes not clear why it is not running (as in the case for "correct"
> above), so if there is a solution, I apply it.
>
> This makes most algorithms run for large integers, but I've still to check
> several.
>
> So this is a great enhancement, thanks again for your report.
>
> Note that it is not yet in 1.49, too late. Boost's trunk contains the new
> code.
>
> Regards, Barend
>
> ______________________________**_________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/**mailman/listinfo.cgi/geometry
>

>