boost::geometry: intersection of a point with a linestring

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

boost::geometry: intersection of a point with a linestring

Boost - Users mailing list
Hi there,

Is there any boost functionality to "split" a linestring with an intersecting point?
I was expecting that boost::geometry::intersection could return a multi-linestring (of size two) or a vector of linestrings (size two). 

For example, please see a very simple case below which doesn't compile:

  point_2d pt(0.5, 0);
  linestring_2d ls({ point_2d(0, 0), point_2d(1, 0), point_2d(3, 0), point_2d(5, 0) });
  std::vector<linestring_2d> inter;
  bg::intersection(pt, ls, inter);

Is there any way to get inter vector with two linestrings (linestring_2d({point_2d(0, 0), point_2d(0.5, 0) }) and linestring_2d({point_2d(0.5, 0), point_2d(1, 0), point_2d(3, 0), point_2d(5, 0) }) ) or any multi geometry container that will hold the spatial information of two lines connected in this point? Or should I create these two lines myself by working out which points of the linestring are left and right of the intersecting point?

Many thanks in advance.

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::geometry: intersection of a point with a linestring

Boost - Users mailing list
On Thu, 3 Oct 2019 at 18:04, Giorgino R via Boost-users
<[hidden email]> wrote:
>
> Is there any boost functionality to "split" a linestring with an intersecting point?

I'm not aware of any such algorithm in Boost.Geometry.

> I was expecting that boost::geometry::intersection could return a multi-linestring (of size two) or a vector of linestrings (size two).

That would be a different algorithm, presumably split, but not
intersection according to OGC.

Mind you, the Boost.Geometry documentation at
https://www.boost.org/libs/geometry/doc/html/geometry/reference/algorithms/intersection/intersection_3.html
says "The function intersection implements function Intersection from
the OGC Simple Feature Specification.",
what is similar to PostGIS, https://postgis.net/docs/ST_Intersection.html.
The OGC Simple Feature Specification says the algorithm returns
point set intersection of input geometries.

> For example, please see a very simple case below which doesn't compile:
>
>>   point_2d pt(0.5, 0);
>>   linestring_2d ls({ point_2d(0, 0), point_2d(1, 0), point_2d(3, 0), point_2d(5, 0) });
>>   std::vector<linestring_2d> inter;
>>   bg::intersection(pt, ls, inter);
>
>
> Is there any way to get inter vector with two linestrings (...) or any multi geometry container
> that will hold the spatial information of two lines connected in this point?
> Or should I create these two lines myself by working out which points of the linestring
> are left and right of the intersecting point?

There is a way and yes you need to build a solution your self,
but it should be not a hair-pulling experience using the building blocks
provided by Boost.Geometry.

For example, here is a quick example with possible solution:

```
#include <boost/geometry.hpp>
#include <algorithm>
#include <iostream>
#include <vector>
namespace bg = boost::geometry;
using point_2d = bg::model::d2::point_xy<double>;
using linestring_2d = bg::model::linestring<point_2d>;

int main()
{
    point_2d pt(2.5, 0);
    linestring_2d ls({{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}});

    auto split_begin = std::find_if(bg::segments_begin(ls),
bg::segments_end(ls),
        [&pt](auto const& segment) { return bg::intersects(segment, pt); });

    linestring_2d line1;
    std::for_each(bg::segments_begin(ls), split_begin, [&line1](auto const& s)
    {
        bg::append(line1, s.first);
    });
    bg::append(line1, split_begin->first);
    bg::append(line1, pt);

    linestring_2d line2;
    bg::append(line2, pt);
    bg::append(line2, split_begin->second);
    std::for_each(++split_begin, bg::segments_end(ls), [&line2](auto const& s)
    {
        bg::append(line2, s.second);
    });

    std::cout << bg::dsv(line1) << std::endl;
    std::cout << bg::dsv(line2) << std::endl;
}
```

It does take some time to get familiar with Geometry LEGO, but the docs are good
and the .cpp files with examples should be useful as well.

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::geometry: intersection of a point with a linestring

Boost - Users mailing list
Hi Mateus,

Many thanks for your descriptive response.
The library is indeed very nice and most of the time we don't have to pull our hair 😂.
Your example is exactly what I was thinking as a solution. However, I just wanted to know whether an "optimised split" algorithm has been implemented. The PostGIS link was very helpful as well.

Many thanks once again.

BW
G

On Thu, Oct 3, 2019 at 6:31 PM Mateusz Loskot via Boost-users <[hidden email]> wrote:
On Thu, 3 Oct 2019 at 18:04, Giorgino R via Boost-users
<[hidden email]> wrote:
>
> Is there any boost functionality to "split" a linestring with an intersecting point?

I'm not aware of any such algorithm in Boost.Geometry.

> I was expecting that boost::geometry::intersection could return a multi-linestring (of size two) or a vector of linestrings (size two).

That would be a different algorithm, presumably split, but not
intersection according to OGC.

Mind you, the Boost.Geometry documentation at
https://www.boost.org/libs/geometry/doc/html/geometry/reference/algorithms/intersection/intersection_3.html
says "The function intersection implements function Intersection from
the OGC Simple Feature Specification.",
what is similar to PostGIS, https://postgis.net/docs/ST_Intersection.html.
The OGC Simple Feature Specification says the algorithm returns
point set intersection of input geometries.

> For example, please see a very simple case below which doesn't compile:
>
>>   point_2d pt(0.5, 0);
>>   linestring_2d ls({ point_2d(0, 0), point_2d(1, 0), point_2d(3, 0), point_2d(5, 0) });
>>   std::vector<linestring_2d> inter;
>>   bg::intersection(pt, ls, inter);
>
>
> Is there any way to get inter vector with two linestrings (...) or any multi geometry container
> that will hold the spatial information of two lines connected in this point?
> Or should I create these two lines myself by working out which points of the linestring
> are left and right of the intersecting point?

There is a way and yes you need to build a solution your self,
but it should be not a hair-pulling experience using the building blocks
provided by Boost.Geometry.

For example, here is a quick example with possible solution:

```
#include <boost/geometry.hpp>
#include <algorithm>
#include <iostream>
#include <vector>
namespace bg = boost::geometry;
using point_2d = bg::model::d2::point_xy<double>;
using linestring_2d = bg::model::linestring<point_2d>;

int main()
{
    point_2d pt(2.5, 0);
    linestring_2d ls({{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}});

    auto split_begin = std::find_if(bg::segments_begin(ls),
bg::segments_end(ls),
        [&pt](auto const& segment) { return bg::intersects(segment, pt); });

    linestring_2d line1;
    std::for_each(bg::segments_begin(ls), split_begin, [&line1](auto const& s)
    {
        bg::append(line1, s.first);
    });
    bg::append(line1, split_begin->first);
    bg::append(line1, pt);

    linestring_2d line2;
    bg::append(line2, pt);
    bg::append(line2, split_begin->second);
    std::for_each(++split_begin, bg::segments_end(ls), [&line2](auto const& s)
    {
        bg::append(line2, s.second);
    });

    std::cout << bg::dsv(line1) << std::endl;
    std::cout << bg::dsv(line2) << std::endl;
}
```

It does take some time to get familiar with Geometry LEGO, but the docs are good
and the .cpp files with examples should be useful as well.

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: boost::geometry: intersection of a point with a linestring

Boost - Users mailing list

On Fri, 4 Oct 2019 at 10:53, Giorgino R <[hidden email]> wrote:
Your example is exactly what I was thinking as a solution.
However, I just wanted to know whether an "optimised split" algorithm has been implemented. The PostGIS link was very helpful as well.

I'm not aware of any, but this you can check (or hope) if the `intersect` function is
optimised for point and line case, calculating distance.
I can't remember or am not up to date myself on that.

You may want to post question specifically about to Boost.Geometry mailing list
(actually, much better place to discuss BG issues, than general boost-users).

If not, you can try to optimise the proposed solution by testing easy to optimise
and shortcut cases yourself. It may be a good idea to learn from PostGIS again,
see what the ST_Split function does. For line and point case,
ST_Split is implemented in terms of this function


Best regards,
--

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users