在3D空间中，如何提升两条线段的相交性能？

Question

在3D空间中，如何提升两条线段的相交性能？

c++boostintersectionboost-geometryline-intersection

3

我尝试使用boost geometry计算3D中两条线段的交点。

以下是代码片段：

typedef boost::geometry::model::point<double, 3, boost::geometry::cs::cartesian> boost3dPoint;
typedef boost::geometry::model::segment<boost3dPoint> boost3dSegment;

const boost3dPoint bp0(0, 0, 0);
const boost3dPoint bp1(2, 0, 0);
boost3dSegment lineP(bp0, bp1);

// line m
const boost3dPoint bm0(1, 1, 2);
const boost3dPoint bm1(1, -1, 2);
boost3dSegment lineM(bm0, bm1);

std::vector<boost3dPoint> output;

boost::geometry::intersection(lineP, lineM, output);

if(output.size() == 0)
{
  result.intsec = false;
}
else if(output.size() == 1)
{
  std::cout << "test: output.size() " << std::endl;
  result.intsec = true;
  boost3dPoint bresult = output[0];
  mesh::Point cross(bresult.get<0>(), bresult.get<1>(), bresult.get<2>());
  result.pon = cross;
}
else
{
  // it may line on each other, cosider as no intersection for now
  result.intsec = false;
}

很明显，上述情况没有交集，但仍然返回结果：(1，0，6.94593e-310)

它只在二维中有效吗？

- H'H

没有答案的投票... - H'H

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sehe · Accepted Answer

在我看来，它确实只适用于二维情况。这很令人惊讶，因为通常这些约束条件会被库以相当积极主动的方式断言。

但是，通过以下测试用例，很明显z坐标值只是未初始化/不确定的：

Live On Coliru

#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/io/wkt/stream.hpp>
#include <boost/geometry/geometries/segment.hpp>
#include <boost/geometry/algorithms/intersection.hpp>
#include <boost/geometry/algorithms/correct.hpp>

#include <iomanip>
#include <fstream>
#include <iostream>

#if 0
#include <boost/multiprecision/cpp_dec_float.hpp>
typedef boost::multiprecision::cpp_dec_float<50> dec_float_backend;
typedef boost::multiprecision::number<dec_float_backend, boost::multiprecision::expression_template_option::et_off> T;
#else
typedef int T;
#endif

typedef boost::geometry::model::point<T, 3, boost::geometry::cs::cartesian> boostPoint;
typedef boost::geometry::model::segment<boostPoint> boostSegment;

int main() {
    std::cout << std::setprecision(std::numeric_limits<double>::max_digits10+2);

    for (auto&& segments : {
                // a simple test with intersection [ 5,0,0 ]
                std::make_pair(
                    boostSegment(boostPoint(0 , 0 , 0), boostPoint(10, 0 , 0)),
                    boostSegment(boostPoint(+3, +1, 0), boostPoint(+7, -1, 0))
                ),
                // the test from the OP:
                std::make_pair(
                    boostSegment(boostPoint(0, 0, 0), boostPoint(2, 0, 0)),
                    boostSegment(boostPoint(1, 1, 2), boostPoint(1, -1, 2))
                ),
            })
    {
        std::vector<boostPoint> output;
        boost::geometry::correct(segments.first); // just in case o.O
        boost::geometry::correct(segments.second);
        boost::geometry::intersection(segments.first, segments.second, output);

        std::cout << "Intersecting " << segments.first << " and " << segments.second << "\n";
        std::cout << "Output size: " << output.size() << " ";
        if (!output.empty()) std::cout << output[0];
        std::cout << "\n";
    }
}

在我的本地系统上，输出结果是：

Intersecting LINESTRING(0 0 0,10 0 0) and LINESTRING(3 1 0,7 -1 0)
Output size: 1 POINT(5 0 -133276928)
Intersecting LINESTRING(0 0 0,2 0 0) and LINESTRING(1 1 2,1 -1 2)
Output size: 1 POINT(1 0 -133276928)

在下一次运行时

Intersecting LINESTRING(0 0 0,10 0 0) and LINESTRING(3 1 0,7 -1 0)
Output size: 1 POINT(5 0 1)
Intersecting LINESTRING(0 0 0,2 0 0) and LINESTRING(1 1 2,1 -1 2)
Output size: 1 POINT(1 0 1)

Valgrind确认该值是不确定的：

==13210== Conditional jump or move depends on uninitialised value(s)
==13210==    at 0x4EBFE9E: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.19)
==13210==    by 0x4EC047C: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.19)
==13210==    by 0x4ECC21D: std::ostream& std::ostream::_M_insert<long>(long) (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.19)
==13210==    by 0x401549: main (write.hpp:62)

我认为这个问题可以向库开发者报告。为了方便起见，我添加的“简单测试”案例仅限于二维，如下所示：

enter image description here