Does Boost.Geometry support determination of straight line segment intersection?

[Hermann-SW]

This is a followup question of
boostorg/graph#388

Straight line drawing x- and y-coordinates are std::size_t.
Internally a double argument function intersects() is called, that causes wrong answers.
There is a simple testcase in the issue.

I tried to use intersection() with LineSegments from Boost.Geometry:
boostorg/graph#388 (comment)
But the compiler error says "not implemented".

Next I tried to represent straight line segment between vertex v and w as

    bg::append(poly1.outer(), P(vx,vy));
    bg::append(poly1.outer(), P(wx,wy));
    bg::append(poly1.outer(), P(vx,vy));

but the result does not determine the intersection in the example (is that a bug?).
So intersection() does not seem to work for area=0 polygons.

Is there another Boost.Geometry function that can determine intersection of straight line segments?
If yes, is it exact for integer type coordinates?

Or do I need to implement this?
https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment
Since std::size_t is is 64bit on 64bit systems, and the method involves multiplication, Boost.Multiprecision seems to be needed for implementation?

Regards,

Hermann.

[Hermann-SW]

Oops, while Geometry boost mailing list seems to be dead, the only and last posting from 2023 shows that intersection() is possible for line segments
https://lists.boost.org/geometry/2023/03/3866.php
and I must have done something wrong yesterday.

I modified the script for integer cordinates and two testcases:

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

#include <boost/foreach.hpp>

int main()
{
    using point2d = boost::geometry::model::point<int, 2,
boost::geometry::cs::cartesian>;
    using linestring = boost::geometry::model::linestring<point2d>;

    linestring linestring1{ {2, 0}, {0, 2} };
    linestring linestring2{ {0, 0}, {2, 1} };

    std::vector<point2d> result;

    boost::geometry::intersection(linestring1, linestring2, result); 

    int i = 0;
    BOOST_FOREACH(point2d const& p, result)
    {
        std::cout << i++ << ": " << boost::geometry::to_wkt(p) << std::endl;
    }

    std::cout << "======================" << std::endl;

    linestring linestring3{ {4143438, 86426}, {4064945, 7932} };
    linestring linestring4{ {4064945, 7932}, {4064944, 7931} };

    std::vector<point2d> result2;

    boost::geometry::intersection(linestring3, linestring4, result2); 

    i = 0;
    BOOST_FOREACH(point2d const& p, result2)
    {
        std::cout << i++ << ": " << boost::geometry::to_wkt(p) << std::endl;
    }

    return 0;
}

The 2nd result is exactly what is needed for the graph issue.
But what is the first result?
(0,0)--(2,1) and (0,2)--(2,0) intersect at rational point (4/3, 2/3).
Is the int coordinate result returned the integer coordinate point closest to (4/3, 2/3)?

hermann@j4105:~/graph/test$ ./a.out 
0: POINT(1 1)
======================
0: POINT(4064945 7932)
hermann@j4105:~/graph/test$ 

[barendgehrels]

Indeed, the result of two integer segments will be a point expressed in integers and rounded.

[barendgehrels]

I/o using a linestring, you could also use a segment. An example is here

https://github.com/boostorg/geometry/blob/develop/doc/src/examples/algorithms/intersection_segment.cpp
(this is an existing sample for documentation, but there is no usage of it yet in the documentation)