Увеличение пересечения двух сегментов линии в 3D

Я пытаюсь использовать геометрию повышения для вычисления пересечения двух сегментов линии в 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 )

Он работает только в 2D?


person H'H    schedule 18.03.2015    source источник
comment
голосование без ответа....   -  person H'H    schedule 18.03.2015


Ответы (1)


Мне кажется, что это действительно работает только для 2d случаев. Это удивительно, потому что обычно эти ограничения довольно агрессивно упреждающе устанавливаются библиотекой.

Однако в следующих тестовых примерах становится ясно, что значение координаты z просто унифицировано/неопределенно:

Жить на 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)

Я думаю, так или иначе, это пахнет проблемой, о которой можно сообщить разработчикам библиотеки.

Для вашего удобства «простой тест», который я добавил, на самом деле является 2D, выглядит только так:

введите здесь описание изображения

person sehe    schedule 18.03.2015
comment
спасибо за ваш анализ. Можете ли вы дать мне подсказку для пересечения двух сегментов линии в 3D? есть библиотека CGAL, но мне очень сложно в ней разобраться. - person H'H; 18.03.2015
comment
Я честно не знаю. Я потратил довольно много времени, чтобы прийти к вышеуказанным выводам. Возможно, вы могли бы преобразовать отрезки в многоугольники? (Даже не уверен, поддерживается ли это, потому что технически вы пересекаете треугольники с нулевой шириной) - person sehe; 18.03.2015
comment
Еще раз спасибо, я даже хотел использовать увеличение расстояния, чтобы увидеть, есть ли какое-либо пересечение (к сожалению, это не поддерживается). Хотя я нашел библиотеку расширений cgm.cs.mcgill.ca/~stever/CGAL - person H'H; 18.03.2015
comment
вы можете найти кратчайшее расстояние между двумя сегментами в трехмерном пространстве. Если расстояние равно нулю (или меньше заданного допуска), то сегменты пересекаются. - person Jepessen; 19.03.2015
comment
@Jepessen, разве ОП не заявил, что, к сожалению, это не поддерживается в его последнем комментарии? Он ошибается? - person sehe; 19.03.2015
comment
Алгоритм кратчайшего расстояния довольно прост. Может быть, пока не поддерживается в boost, но должно быть довольно просто создать реализацию алгоритма, которая работает с boostSegment. - person Jepessen; 19.03.2015
comment
Очевидно. Я думаю, однако, что смысл использования библиотеки заключается в том, чтобы избежать реализации этих вещей вручную :) - person sehe; 19.03.2015