Map-geometry intersection of two 3d linestrings using Boost

Question

I'm trying to determine the point of intersection between two 3d linestring using Boost, but in certain cases I'm not getting the expected result.

From my understanding [1], Boost should be calculating the intersection using Map geometry - that is, the Z coordinate is not considered. This is the functionality I'm after.

However, my testing shows if one linestring is always above the other (case 1 in the code listing below), then I get no intersections.

But, if the second line crosses the plane containing the first line - case 2 - then an intersection is found - even though the two lines don't intersect in 3d space.

Is my understanding wrong? Or, is there a way to make case 1 work?

My workaround has been to ensure the first linestring will always cross the plane of the second... But it seems hacky.

Thanks

#include <iostream>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/algorithms/intersection.hpp>

namespace bg = boost::geometry;

int main()
{
    typedef bg::model::point<double, 3, bg::cs::cartesian> point_t;
    typedef bg::model::linestring<point_t> linestring_t;

    linestring_t ls1{{0, 0, 1}, {1, 1, 1}};
    linestring_t ls2{{0, 1, 0}, {1, 0, 0}};
    linestring_t ls3{{0, 1, 0}, {1, 0, 1}};

    std::vector<point_t> intersections;

    bg::intersection(ls1, ls2, intersections);


    std::cout << "Case 1: Intersection between l1 and l2? " << (intersections.size() > 0 ? "Yes" : "No") << std::endl;

    bg::intersection(ls1, ls3, intersections);
    std::cout << "Case 2: Intersection between l1 and l3? " << (intersections.size() > 0 ? "Yes" : "No") << std::endl;


    return 0;
}

output:

Case 1: Intersection between l1 and l2? No
Case 2: Intersection between l1 and l3? Yes

References:

[1] "How to intersection to 3D polygons by Boost C++ library?", https://stackoverflow.com/a/49012544/338230

sehe sehe · Accepted Answer · 2020-06-18T15:40:56

The linked answer merely states that

Boost Geometry area did support implement dimensions>2¹
The OGM standard allows conforming implementations to work in map geometry, although they can implement full 3d geometry, as long as it is consistent with another standard.

I can't find anything different with regards to intersection today. It is rather surprising to me that the documentation doesn't clearly warn against unspecified behaviour.

However, it would appear that the only way to get map-geo behavior is by manually mapping:

Live On Coliru

#include <iostream>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/geometries/multi_point.hpp>
#include <boost/geometry/algorithms/for_each.hpp>

namespace bg = boost::geometry;
static inline constexpr auto io = [](auto& g) { return bg::dsv(g); }; // switch to bg::wkt easily
using point_t      = bg::model::point<double, 3, bg::cs::cartesian>;
using points_t     = bg::model::multi_point<point_t>;
using linestring_t = bg::model::linestring<point_t>;

struct ZeroZ {
    inline void operator()(point_t& p)          const  { p.set<2>(0);                  } 
    template <typename G> void operator()(G& g) const  { bg::for_each_point(g, *this); } 
} static inline constexpr zeroz{};

int main() {
    std::cout << std::fixed << std::setprecision(2);

    linestring_t const lss[] = {
        {{0, 0, 1}, {1, 1, 1}},
        {{0, 1, 0}, {1, 0, 0}},
        {{0, 1, 0}, {1, 0, 1}},
    };

    for (auto a : lss) for (auto b : lss) {
        points_t c, d;
        bg::intersection(a, b, c);

        std::cout << "Normal:  " << io(a) << " with " << io(b) << " ->" << io(c) << "\n";
        zeroz(a);
        zeroz(b);

        bg::intersection(a, b, d);
        if (!bg::equals(c, d))
            std::cout << " -- but: " << io(a) << " with " << io(b) << " ->" << io(d) << "\n";
    }
}

Prints

Normal:  ((0.00, 0.00, 1.00), (1.00, 1.00, 1.00)) with ((0.00, 0.00, 1.00), (1.00, 1.00, 1.00)) ->((0.00, 0.00, 1.00), (1.00, 1.00, 1.00))
 -- but: ((0.00, 0.00, 0.00), (1.00, 1.00, 0.00)) with ((0.00, 0.00, 0.00), (1.00, 1.00, 0.00)) ->((0.00, 0.00, 0.00), (1.00, 1.00, 0.00))
Normal:  ((0.00, 0.00, 0.00), (1.00, 1.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) ->((0.50, 0.50, 0.00))
Normal:  ((0.00, 0.00, 0.00), (1.00, 1.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 1.00)) ->((0.50, 0.50, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 0.00, 1.00), (1.00, 1.00, 1.00)) ->()
 -- but: ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 0.00, 0.00), (1.00, 1.00, 0.00)) ->((0.50, 0.50, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) ->((0.00, 1.00, 0.00), (1.00, 0.00, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 1.00)) ->((0.00, 1.00, 0.00), (1.00, 0.00, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 1.00)) with ((0.00, 0.00, 1.00), (1.00, 1.00, 1.00)) ->((0.50, 0.50, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) ->((0.00, 1.00, 0.00), (1.00, 0.00, 0.00))
Normal:  ((0.00, 1.00, 0.00), (1.00, 0.00, 0.00)) with ((0.00, 1.00, 0.00), (1.00, 0.00, 1.00)) ->((0.00, 1.00, 0.00), (1.00, 0.00, 0.00))

¹ at the time, not even checked whether that changed

Map-geometry intersection of two 3d linestrings using Boost

1 Answers