Skip to content

Redundant segment intersection check in segment-segment distance computation during polygon-polygon distance calculation #1136

@huangzq2016

Description

@huangzq2016

When using Boost 1.67.0 to compute polygon-polygon distance, the internal rt::query step for solving segment-segment distance still checks whether the two segments intersect, even though polygon intersection has already been checked before calling rt::query (see boost/geometry/algorithms/detail/distance/linear_or_areal_to_areal.hpp).
I have two questions regarding this:

  1. In the segment-segment distance computation of polygon-polygon distance computation, does the call to geometry::intersects always return false?
  2. If it always returns false, can I add a new solving path by creating new template specializations (or classes) that removes the intersects check, so that polygon-polygon distance calculation uses this new path?

example test code:

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

namespace bg = boost::geometry;
typedef bg::model::d2::point_xy point_type;
typedef bg::model::polygon<point_type> polygon_type;

void create_rect(polygon_type& p, double x1, double y1, double x2, double y2) {
p.outer().push_back(point_type(x1, y1));
p.outer().push_back(point_type(x2, y1));
p.outer().push_back(point_type(x2, y2));
p.outer().push_back(point_type(x1, y2));
p.outer().push_back(point_type(x1, y1));
}

int main(int argc, char **argv){
polygon_type p1, p2;
create_rect(p1, 0, 0, 10, 10);
create_rect(p2, 100, 100, 110, 110);
volatile double d = bg::distance(p1, p2);
return 0
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions