Trouble with polygon/box intersection when polygon/box point types are different

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Trouble with polygon/box intersection when polygon/box point types are different

Gratton, Michael
Hello,

I'm trying to adapt polygons using Eigen::Vector2d point types (http://eigen.tuxfamily.org) for use with boost::geometry.  Things mostly work great, but the rtree implementation uses the internal boost::geometry box type, and I get errors when attempting to intersect my Eigen polygon with the internal box.

I made a small program to isolate the compilation error I get:

%<------------------------------------------------
#include <Eigen/Core>
#include <Eigen/StdVector>
#include <Eigen/Geometry>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/geometries/register/ring.hpp>
#include <boost/geometry/geometries/register/linestring.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry.hpp>

using Eigen::Vector2d;
typedef std::vector<Vector2d, Eigen::aligned_allocator<Vector2d> > EigenVector2d;

BOOST_GEOMETRY_REGISTER_POINT_2D(Vector2d, double, cs::cartesian, coeffRef(0), coeffRef(1))
BOOST_GEOMETRY_REGISTER_LINESTRING(EigenVector2d)
BOOST_GEOMETRY_REGISTER_BOX(Eigen::AlignedBox2d, Vector2d, min(), max());

typedef boost::geometry::model::polygon<
                    Vector2d,                   // Point type
               true,                     // Orientation is counter-clockwises in NED sense (south-east-north-west)
               false,                    // Closure is implied (last point != first point)
               std::vector,              // Store for points (efficient if all points known in advance)
               std::vector,              // Store for rings (efficient if all holes known in advance)
               Eigen::aligned_allocator  // Need to allocate Vector2d with special allocator
               >
               EigenPolygon;


int main(int argc, char** argv)
{
    namespace bg = boost::geometry;
    EigenVector2d point(3);
    point[0] << 0.5, 0.5;
    point[1] << 0.5, 6.0;
    point[2] << -1.0, 2.0;
    EigenPolygon poly;
    bg::append(poly, point);
    Vector2d ll(0,0);
    Vector2d ur(5.0,5.0);
    Eigen::AlignedBox2d box(ll, ur);
    std::cout << "poly intersect box? " << bg::intersects(poly, box) << "\n";
    bg::model::box<bg::model::point<double, 2ul, bg::cs::cartesian> > bbox;
    bbox.min_corner().set<0>(ll(0));
    bbox.min_corner().set<1>(ll(1));
    bbox.max_corner().set<0>(ur(0));
    bbox.max_corner().set<1>(ur(1));
    // Fails
    std::cout << "poly intersect bbox? " << bg::intersects(poly, bbox) << "\n";
    bg::model::polygon<bg::model::point<double, 2ul, bg::cs::cartesian>, true, false> poly2;
    bg::append(poly2, point);
    std::cout << "poly2 intersect bbox? " << bg::intersects(poly2, bbox) << "\n";
    // Fails
    std::cout << "poly2 intersect box? " << bg::intersects(poly2, box) << "\n";
}
%<------------------------------------------------------------------

I don't know if I am doing something wrong with the registration macros, but it looks okay to me.  Working from the 1.60 source, I found that boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp@222 is trying to use a strategy::apply that assumes Point1 is the same type as Point2.  If I change

    intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
                      Point2 const& qi, Point2 const& qj, Point2 const& qk,
                      RobustPolicy const& robust_policy)
        : base(pi, pj, pk, qi, qj, qk, robust_policy)
        , m_result(strategy::apply(segment_type1(pi, pj),
                                   segment_type2(qi, qj),
                                   robust_policy,
                                   base::rpi(), base::rpj(),
                                   base::rqi(), base::rqj()))
        , m_robust_policy(robust_policy)
    {}

to read

    intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
                      Point2 const& qi, Point2 const& qj, Point2 const& qk,
                      RobustPolicy const& robust_policy)
        : base(pi, pj, pk, qi, qj, qk, robust_policy)
        , m_result(strategy::apply(segment_type1(pi, pj),
                                   segment_type2(qi, qj),
                                   robust_policy))
        , m_robust_policy(robust_policy)
    {}

then everything builds and works.  Looking inside, it looks like the later makes copies of the four points, storing them in the point type of the first segment type.  So this change would be a bit of a performance hit compared to what is already there.

Is this a bug or am I mixing something up with my custom polygon type?

Thanks,

Michael Gratton, Ph.D. | Senior Research Analyst

Metron | Computing and Engineering Technologies for Unmanned Systems (CETUS) Division

1818 Library St Ste 600 | Reston VA 20190

703.326.2833 | [hidden email]<mailto:[hidden email]>
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Trouble with polygon/box intersection when polygon/box point types are different

Adam Wulkiewicz
Gratton, Michael wrote:
Hello,

I'm trying to adapt polygons using Eigen::Vector2d point types (http://eigen.tuxfamily.org) for use with boost::geometry.  Things mostly work great, but the rtree implementation uses the internal boost::geometry box type, and I get errors when attempting to intersect my Eigen polygon with the internal box.

Hi Michael,

Thanks for the info about the bug.
This bug was reported recently: https://svn.boost.org/trac/boost/ticket/12189
See also a discussion (workaround): http://boost-geometry.203548.n3.nabble.com/R-tree-spacial-predicates-intersects-Ring-in-boost-1-59-upwards-td4026700.html

Regards,
Adam

I made a small program to isolate the compilation error I get:

%<------------------------------------------------
#include <Eigen/Core>
#include <Eigen/StdVector>
#include <Eigen/Geometry>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/geometries/register/ring.hpp>
#include <boost/geometry/geometries/register/linestring.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry.hpp>

using Eigen::Vector2d;
typedef std::vector<Vector2d, Eigen::aligned_allocator<Vector2d> > EigenVector2d;

BOOST_GEOMETRY_REGISTER_POINT_2D(Vector2d, double, cs::cartesian, coeffRef(0), coeffRef(1))
BOOST_GEOMETRY_REGISTER_LINESTRING(EigenVector2d)
BOOST_GEOMETRY_REGISTER_BOX(Eigen::AlignedBox2d, Vector2d, min(), max());

typedef boost::geometry::model::polygon<
                    Vector2d,                   // Point type
               true,                     // Orientation is counter-clockwises in NED sense (south-east-north-west)
               false,                    // Closure is implied (last point != first point)
               std::vector,              // Store for points (efficient if all points known in advance)
               std::vector,              // Store for rings (efficient if all holes known in advance)
               Eigen::aligned_allocator  // Need to allocate Vector2d with special allocator
               >
               EigenPolygon;


int main(int argc, char** argv)
{
    namespace bg = boost::geometry;
    EigenVector2d point(3);
    point[0] << 0.5, 0.5;
    point[1] << 0.5, 6.0;
    point[2] << -1.0, 2.0;
    EigenPolygon poly;
    bg::append(poly, point);
    Vector2d ll(0,0);
    Vector2d ur(5.0,5.0);
    Eigen::AlignedBox2d box(ll, ur);
    std::cout << "poly intersect box? " << bg::intersects(poly, box) << "\n";
    bg::model::box<bg::model::point<double, 2ul, bg::cs::cartesian> > bbox;
    bbox.min_corner().set<0>(ll(0));
    bbox.min_corner().set<1>(ll(1));
    bbox.max_corner().set<0>(ur(0));
    bbox.max_corner().set<1>(ur(1));
    // Fails
    std::cout << "poly intersect bbox? " << bg::intersects(poly, bbox) << "\n";
    bg::model::polygon<bg::model::point<double, 2ul, bg::cs::cartesian>, true, false> poly2;
    bg::append(poly2, point);
    std::cout << "poly2 intersect bbox? " << bg::intersects(poly2, bbox) << "\n";
    // Fails
    std::cout << "poly2 intersect box? " << bg::intersects(poly2, box) << "\n";
}
%<------------------------------------------------------------------

I don't know if I am doing something wrong with the registration macros, but it looks okay to me.  Working from the 1.60 source, I found that boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp@222 is trying to use a strategy::apply that assumes Point1 is the same type as Point2.  If I change

    intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
                      Point2 const& qi, Point2 const& qj, Point2 const& qk,
                      RobustPolicy const& robust_policy)
        : base(pi, pj, pk, qi, qj, qk, robust_policy)
        , m_result(strategy::apply(segment_type1(pi, pj),
                                   segment_type2(qi, qj),
                                   robust_policy,
                                   base::rpi(), base::rpj(),
                                   base::rqi(), base::rqj()))
        , m_robust_policy(robust_policy)
    {}

to read

    intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
                      Point2 const& qi, Point2 const& qj, Point2 const& qk,
                      RobustPolicy const& robust_policy)
        : base(pi, pj, pk, qi, qj, qk, robust_policy)
        , m_result(strategy::apply(segment_type1(pi, pj),
                                   segment_type2(qi, qj),
                                   robust_policy))
        , m_robust_policy(robust_policy)
    {}

then everything builds and works.  Looking inside, it looks like the later makes copies of the four points, storing them in the point type of the first segment type.  So this change would be a bit of a performance hit compared to what is already there.

Is this a bug or am I mixing something up with my custom polygon type?

Thanks,

Michael Gratton, Ph.D. | Senior Research Analyst

Metron | Computing and Engineering Technologies for Unmanned Systems (CETUS) Division

1818 Library St Ste 600 | Reston VA 20190

703.326.2833 | [hidden email][hidden email]
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



 

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Trouble with polygon/box intersection when polygon/box point types are different

Adam Wulkiewicz
In reply to this post by Gratton, Michael
Gratton, Michael wrote:
I'm trying to adapt polygons using Eigen::Vector2d point types (http://eigen.tuxfamily.org) for use with boost::geometry.  Things mostly work great, but the rtree implementation uses the internal boost::geometry box type, and I get errors when attempting to intersect my Eigen polygon with the internal box.

I made a small program to isolate the compilation error I get:

<snip>

then everything builds and works.  Looking inside, it looks like the later makes copies of the four points, storing them in the point type of the first segment type.  So this change would be a bit of a performance hit compared to what is already there.

Is this a bug or am I mixing something up with my custom polygon type?

I prepared a fix for this issue: https://github.com/boostorg/geometry/pull/351

Could you check if it works for you?
You could either checkout the branch with the fix from my repo or simply copy this file into your local copy of Boost.Geometry:
https://github.com/awulkiew/geometry/blob/ccd671f5aca5813ac7ffc2494438182ad281c807/include/boost/geometry/strategies/cartesian/cart_intersect.hpp

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...