boostorg / boostorg/boost

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

Open
#1,136 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
HTML
Stars
8.6k
Forks
1.9k
Avg merge
39m
Merged PRs (30d)
2

Description

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
#include
#include

namespace bg = boost::geometry;
typedef bg::model::d2::point_xy point_type;
typedef bg::model::polygon 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
}

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.