Boost.Geometry intersects

boost::geometry::intersects()アルゴリズムは、1つまたは2つのジオメトリが、少なくてもひとつの交点を持っているかどうかを判定する関数です。


以下は、2本の線が交わっているか判定する処理です:

#include <boost/assert.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/assign/list_of.hpp>

namespace bg = boost::geometry;

int main()
{
    typedef bg::model::d2::point_xy<double> point;

    //  line2
    //    |
    // ---+---- line1
    //    |
    {
        const bg::model::linestring<point> line1 = boost::assign::list_of<point>(0, 2)(2, 2);
        const bg::model::linestring<point> line2 = boost::assign::list_of<point>(1, 0)(1, 4);

        const bool result = bg::intersects(line1, line2);
        BOOST_ASSERT(result);
    }
    // -------- line1
    // -------- line2
    {
        const bg::model::linestring<point> line1 = boost::assign::list_of<point>(0, 0)(2, 0);
        const bg::model::linestring<point> line2 = boost::assign::list_of<point>(0, 2)(2, 2);

        const bool result = bg::intersects(line1, line2);
        BOOST_ASSERT(!result);
    }
}

また、linestringは複数の線を表現することもできるので、一筆書きの線の中に線同士が交わっているところがあるかどうかにも使用できます:

#include <boost/assert.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/assign/list_of.hpp>

namespace bg = boost::geometry;

int main()
{
    typedef bg::model::d2::point_xy<double> point;

    //        c
    //        +
    //        | +
    // a +----+---+ b
    //        |
    //        d
    {
        const bg::model::linestring<point> line = boost::assign::list_of<point>
            (0, 4)
            (4, 4)
            (2, 2)
            (2, 5)
            ;

        const bool result = bg::intersects(line);
        BOOST_ASSERT(result);
    }
    //   a
    //   |
    //   |
    //   |
    // b +-------- c
    {
        const bg::model::linestring<point> line = boost::assign::list_of<point>
            (0, 0)
            (0, 4)
            (4, 4)
            ;

        const bool result = bg::intersects(line);
        BOOST_ASSERT(!result);
     }
}
Intersects: NO
Intersects: NO

最初のでfalseが返るのは、Boost.Geometryのバグのようです。
報告したら、「今週末くらいに見てみるよ」と言ってたので、おそらく1.48.0では直るでしょう。

intersects bug?


追記 start {

2011/07/29 12:36
直してもらいました。trunkで修正バージョンを使用することができます。
firstとlastの交差がうまくいってなかったそうです。

}



ちなみに、2引数バージョンのintersects()の実装は、単に!disjoint()してるだけです。


参照:
intersects algorithm(1引数バージョン)
intersects algorithm(2引数バージョン)