[Boost-users] measuring distance between a point and a segment

[Juliette Pera]

Dear all,

I am currently trying to use the boost library in order to measure the shortest distance between a point and a list of segments.

I am declaring a segment to which I append the two points of my segment and the I calculate the distance from my point P to the segment.

   xsegment_t segment;
   geom::append(segment,geom::make_point(A[0],A[1]));
   geom::append(segment,geom::make_point(B[0],B[1]));
   double distance2 = geom::distance(segment,geom::make_point(P[0],P[1]));

The issue is that I measure every time the same distance even if the segment is different.

Does anyone knows from where that issue can come from?

Thank you in advance,

Juliette Pera

 

[Adam Wulkiewicz]

Hi Juliette,

Juliette Pera wrote:

Sorry, but I don't have enough data to say what's the problem. It'd be the best if you could share some small but complete example showing this issue.

Does the algorithm return this result when geometries of types bg::model::segment and bg::model::point are passed?
What coordinate system do you use?

Or do you use your own types adapted to Segment and Point concepts?
If the answer is yes, then I'd start from checking if the adaptation was done correctly.

Regards,
Adam

[Juliette Pera]

Hi Adam,

Thanks for your answer.

Here's some more information.

I am going through the list of vertices of a segment, stored in a vector of Eigen::Vector2D and then I am computing the distance from a point stored in Eigen::vector2d to a each segment of my polygon.

I calculate the distance using my own function and then I calculate it using boost function distance.

I declare a segment of type  boost::geometry::model::segment<double>  in which I add my two vertices that make the segment.

Then I display the result for each vertices and I get the same result for every segment using boost.

I hope it's more clear now.

Thank you for your help.

Juliette

        double closestDistance(std::vector<Eigen::Vector2d> polygon2D, Eigen::Vector2d P)
        {
                double minDist = DBL_MAX;
                for( unsigned int i = 0 ; i < polygon2D.size() ; i++ )
                {
                        Eigen::Vector2d A = polygon2D.at(i);
                        Eigen::Vector2d B;
                        if( i == polygon2D.size()-1 )
                        {
                                B = polygon2D.at(0);
                        }
                        else
                        {
                                B = polygon2D.at(i+1);
                        }
                        Eigen::Vector2d seg = B-A;

                        double U = (((P[0]-A[0])*seg[0])+((P[1]-A[1])*seg[1]))/(seg.norm()*seg.norm());

                        double distance;
                        if( U < 0 )
                        {
                                distance = (A-P).norm();
                        }
                        else if( U > 1 )
                        {
                                distance = (B-P).norm();
                        }
                        else
                        {
                            Eigen::Vector2d Ph = A + U*seg;
                            distance = (Ph-P).norm();
                        }

                        // testing boos distance here

                        xsegment_t segment;
                        geom::append(segment,geom::make_point(A[0],A[1]));
                        geom::append(segment,geom::make_point(B[0],B[1]));
                        double distance2 = geom::distance(segment,geom::make_point(P[0],P[1]));

                        std::cout << "Distance comparison : " << distance << " / " << distance2 << std::endl;

                        if( distance < minDist )
                        {
                                minDist = distance;
                        }
                }
                return minDist;
        }

Result obtained:

Distance comparison : 36.6926 / 4.37843

Distance comparison : 19.5823 / 4.37843

Distance comparison : 20.6683 / 4.37843

Distance comparison : -nan / 4.37843     --> two vertices are at the same point

Distance comparison : 12.2823 / 4.37843

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Adam Wulkiewicz]

Juliette Pera wrote:

Thanks for your answer.

Here's some more information.

I am going through the list of vertices of a segment, stored in a vector of Eigen::Vector2D and then I am computing the distance from a point stored in Eigen::vector2d to a each segment of my polygon.

I calculate the distance using my own function and then I calculate it using boost function distance.

I declare a segment of type  boost::geometry::model::segment<double>  in which I add my two vertices that make the segment.

You probably mean boost::geometry::model::segment<boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian> > ?

Then I display the result for each vertices and I get the same result for every segment using boost.

I hope it's more clear now.

If xsegment_t is of type boost::geometry::model::segment and geom::append() is boost::geometry::append() then it doesn't set the endpoints of a segment. It's because a segment is not a container so appending to it doesn't change it. If xsegment_t was e.g. boost::geometry::model::linestring or instead of bg::append() the endpoints of a segment was passed into the constructor it should work.

The behavior of bg::append() is indeed confusing. Anyway, try using the constructor of bg::model::segement instead:

xsegment_t segment(geom::make_point(A[0],A[1]),

                   geom::make_point(B[0],B[1]));

double distance2 = geom::distance(segment, geom::make_point(P[0],P[1]));

Please let me know if this helps.


TL;DR

A side note. If the overall goal was to calculate the distance from a point to Polygon2D then you could write your own Ring type (a Polygon without holes), e.g. wrap std::vector<Eigen::Vector2d> and adapt your type to Boost.Geometry Ring concept. Or simply register std::vector<Eigen::Vector2d> as a Ring (though then all std::vectors of Eigen::Vector2d points would be treated as Rings). It'd require to adapt Eigen::Vector2d type to Boost.Geometry Point concept and since Eigen::Vector2d provides operator[] for element access you would be forced to adapt it manually specializing traits. If the goal was to calculate the closest distance to the edge of Polygon2D then instead of adapting std::vector to the Ring concept you could adapt it to the Linestring concept. Then Boost.Geometry could calculate the distance for you.

Here Boost.Geometry point_xy is adapted:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/geometries/point_xy.hpp#L87

You could copy it and replace:
model::d2::point_xy<CoordinateType, CoordinateSystem> -> Eigen::Vector2d
CoordinateType                                        -> double
CoordinateSystem                                      -> cs::cartesian
return p.template get<Dimension>();                   -> return p[Dimension];
p.template set<Dimension>(value);                     -> p[Dimension] = value;

Here is an example of adapting std::vector to the Ring concept:
http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/adapted/register/boost_geometry_register_ring.html

So you could register your vector like this:
BOOST_GEOMETRY_REGISTER_RING(std::vector<Eigen::Vector2d>)

And then
bg::distance(polygon2D, P)
should return the distance between Polygon and Point.

See also:
http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html
http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/concepts/concept_ring.html
http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/concepts/concept_linestring.html
http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/reference/adapted/register/boost_geometry_register_linestring.html

Regards,
Adam

 

[Juliette Pera]

Thank you very much it works very well now!

I was considering using a ring type at first but I was having a wrong result too.

I was using the append function and then the correct one.

Maybe I was missing something to "close" the polygon?

Thank you

Juliette

[Adam Wulkiewicz]

Juliette Pera wrote:

Thank you very much it works very well now!

I was considering using a ring type at first but I was having a wrong result too.

I was using the append function and then the correct one.

Maybe I was missing something to "close" the polygon?

correct() should reverse and close the Ring for you if needed so it probably wasn't it.
What was wrong with the result?
Have in mind that for Points contained inside a Ring the distance is 0.


You could debug your code and see if the data stored in your objects is correct before passing it into an algorithm.
In order to debug Boost.Geometry conveniently you could use debugging visualizers/helpers:

Visual Studio 2015:
https://visualstudiogallery.msdn.microsoft.com/4b81868b-8901-408f-a28e-25a6580788fb

Visual Studio 2012-13:
https://github.com/awulkiew/graphical-debugging/blob/master/Visual_Studio_2015/GraphicalDebugging/BoostGeometry.natvis
How to use it: https://msdn.microsoft.com/en-us/library/jj620914%28v=vs.110%29.aspx

QtCreator:
https://github.com/awulkiew/debugging-helpers

Regards,
Adam

 

[Juliette Pera]

Actually it was for point inside the polygon so it explains the problem.

But can I access the elements of the polygon if I declare it as ring?

Then I can use the distance between the point and each segment to finally take the smallest value.

Thank you

Juliette

[Adam Wulkiewicz]

Juliette Pera wrote:

Actually it was for point inside the polygon so it explains the problem.

But can I access the elements of the polygon if I declare it as ring?

Of course, bg::model::ring is adapted to Boost.Range concept and also has operator[]. If you had your own Ring type you could use any methods defined in it. E.g. in my eariler email if you adapted std::vector<Eigen::Vector2d> to a Ring concept you could of still call any method and operator defined in std::vector.

Then I can use the distance between the point and each segment to finally take the smallest value.

My point was that maybe you could avoid doing it manually. I don't know what you're planning to do exactly but since you're ignoring the interior of a Polygon when calculating distance then maybe a Linestring would be a better representation? You could e.g. use bg::model::linestring<Point>.

Regards,
Adam

[Juliette Pera]

Hi Adam,

Thank you for your help! Now it's working perfectly!

Have a nice day.

Juliette