boost geometry polygon distance for inside point

Question

I am using boost::geometry to handle some geometrical tasks. I have two requirements that I need to cover:

• Handle point -> polygon intersection (inside or not). This works great with boost::geometry::within so thats good
• Get the distance of an arbitrary point to the closest edge of the polygon. While points outside of the polygon are handled correctly by boost::geometry::distance, however it seems that it considers polygons solid. So every point inside the polygon obviously has a distance of 0 to the polygon.

I tried experimenting with inner/outer stuff and was wondering if there is a possbility to get the distance for both inside and outside points of a polygon.

Answer 1

In case where point is inside polygon you may speed your code up using comparable_distance instead of distance algorithm. You don't need to calculate the exact distance for every segment-point pair. Find the nearest segment of polygon to the given point using comparable_distance and then calculate the real distance using distance algorithm.

auto distance = std::numeric_limits<float>::max();
if(boost::geometry::within(pt, mPolygon)) 
{
  Segment nearestSegment;
  boost::geometry::for_each_segment(mPolygon, 
    [&distance, &pt, &nearestSegment](const auto& segment) 
     {
        double cmpDst = boost::geometry::comparable_distance(segment,pt);
        if (cmpDst < distance)
        {
          distance = cmpDst;
          nearestSegment = segment; // UPDATE NEAREST SEGMENT
        }
      });
      // CALCULATE EXACT DST
      distance = boost::geometry::distance(nearestSegment,pt);
} else {
  distance = boost::geometry::distance(pt, mPolygon);
}

Answer 2

I have decided to use the following approach which seems to provide the right results so far:

const TPolygonPoint pt{ x, y };
auto distance = std::numeric_limits<float>::max();

if(boost::geometry::within(pt, mPolygon)) {
    boost::geometry::for_each_segment(mPolygon, [&distance, &pt](const auto& segment) {
        distance = std::min<float>(distance, boost::geometry::distance(segment, pt));
    });
} else {
    distance = boost::geometry::distance(pt, mPolygon);
}

return distance;

If anyone knows a faster or nicer way, please leave a comment :)

Answer 3

For best performances you should use an RTree with boost::geometry::index. Creating the RTree has a cost, but then computing the ditance of a point to any of the (multi)polygon ring will be much fast. Example code:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <iostream>
#include <vector>

int main()
{
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<double, 2, bg::cs::cartesian> point;
    typedef bg::model::polygon<point> polygon;

    point p{ 0, 0 };
    // create some polygon and fill it with data
    polygon poly;
    double a = 0;
    double as = bg::math::two_pi<double>() / 100;
    for (int i = 0; i < 100; ++i, a += as)
    {
        double c = cos(a);
        double s = sin(a);
        poly.outer().push_back(point{10 * c, 10 * s});
        poly.inners().resize(1);
        poly.inners()[0].push_back(point{5 * c, 5 * s});
    }
    // make sure it is valid
    bg::correct(poly);

    // create rtree containing objects of type bg::model::pointing_segment
    typedef bg::segment_iterator<polygon const> segment_iterator;
    typedef std::iterator_traits<segment_iterator>::value_type segment_type;

    bgi::rtree<segment_type, bgi::rstar<4> > rtree(bg::segments_begin(poly),
                                                   bg::segments_end(poly));

    // get 1 nearest segment
    std::vector<segment_type> result;
    rtree.query(bgi::nearest(p, 1), std::back_inserter(result));

    BOOST_ASSERT(!result.empty());

    std::cout << bg::wkt(result[0]) << ", " << bg::distance(p, result[0]) << std::endl;

    return 0;
}

Answer 4

You can directly use boost::geometry::distance if you add an inner boundary to the polygon coinciding with the outer boundary [Polygon Concept].

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

namespace bg = boost::geometry;

int main() {
    typedef bg::model::point<int, 2, bg::cs::cartesian> point_t;
    typedef bg::model::polygon<point_t> polygon_t;

    polygon_t poly1;    

    bg::append (poly1.outer(), point_t (1, -1));
    bg::append (poly1.outer(), point_t (1, 1));
    bg::append (poly1.outer(), point_t (-1, 1));
    bg::append (poly1.outer(), point_t (-1, -1));
    bg::append (poly1.outer(), point_t (1, -1));

    poly1.inners().resize (1);
    bg::append (poly1.inners()[0], point_t (1, -1));
    bg::append (poly1.inners()[0], point_t (1, 1));
    bg::append (poly1.inners()[0], point_t (-1, 1));
    bg::append (poly1.inners()[0], point_t (-1, -1));
    bg::append (poly1.inners()[0], point_t (1, -1));


    point_t myPoint (0, 0);
    std::cout << "Minimal distance: " << bg::distance (poly1, myPoint) << std::endl;
    std::cout << "Is within: " << bg::within (myPoint, poly1) << std::endl;

    return 0;
}

-> Will return:

    Minimal distance: 1
    Is within: 0

However, if you do that, points strictly inside the polygon will be considered to lie 'outside' the polygon by boost::geometry::within. If you want both functionalities, you can maintain two separate polygons- one with an inner boundary and one without.