I have been using boost::geometry
library in a program, mostly for handling polygon objects.
I am now trying to optimize my code to scale better with larger polygons. One my functions checks for a given polygon and a given point (usually inside the polygon) the minimum and maximum distance between the point and polygon outer ring.
I do it by looping on the polygon edges:
polygon pol;
point myPoint;
double min = 9999999, max = 0;
for(auto it1 = boost::begin(bg::exterior_ring(pol)); it1 != boost::end(bg::exterior_ring(pol)); ++it1){
double distance = bg::distance(*it1, myPoint);
if(max < distance)
max = distance;
if(min > distance)
min = distance;
}
I am hoping that there are algorithms faster than this one, linear in the polygon number of edges. Is there such a thing already inside the boost::geometry
library?
I'd suggest you can use the builtin strategies for finding the minimum distance between the polygon and the point:
#include <boost/geometry.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/algorithms/distance.hpp>
namespace bg = boost::geometry;
using point = bg::model::d2::point_xy<double>;
using polygon = bg::model::polygon<point>;
int main() {
polygon pol;
boost::geometry::read_wkt(
"POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
"(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))", pol);
point myPoint(7, 7);
double min = 9999999, max = 0;
std::cout << "Minimal distance: " << bg::distance(pol, myPoint);
}
Prints
Minimal distance: 4.71699
You should consider ranking the distances first using comparable_distance
. As you can see the sample there suggests looping over all the sampled distances... so I don't think the library has a better offering at this time.
More sophisticated algorithms are planned, of which a number may be related to this problem:
Note also that Boost Geometry Index has a related predicate comparable_distance_far
but it's not exposed as of yet.
You can improve at least a bit by using comparable_distance here for now.
Features have been planned and it looks like there is a good chance that requesting them on the mailing list/Boost Trac will help getting them there.