如何找到在两个矩形之间形成最近距离的两个点？

Question

我正在尝试寻找算法来找到代表两个矩形之间最近距离的两个点。像下图中形成最小距离的点 C 和 J：

我不想在这里重新发明轮子，而是使用已经经过实战测试的东西，比如 boost::geometry::distance，但它只有 return 距离，而不是点数。

Answer 1

不要让事情过于通用（通过假设浮点坐标和笛卡尔坐标系），这里是点到线段距离的实现，returns 投影点和距离：

struct DistancePoint {
    double distance;
    P projected_point;
};

template <typename Strategy = bg::strategy::distance::pythagoras<> >
DistancePoint point_to_segment(P const& p, P const& p1, P const& p2) {
    P v = p2, w = p;
    bg::subtract_point(v, p1);
    bg::subtract_point(w, p1);

    auto const c1 = bg::dot_product(w, v);
    if (c1 <= 0)  return { Strategy::apply(p, p1), p1 };

    auto const c2 = bg::dot_product(v, v);
    if (c2 <= c1) return { Strategy::apply(p, p2), p2 };

    P prj = p1;
    bg::multiply_value(v, c1/c2);
    bg::add_point(prj, v);

    return { Strategy::apply(p, prj), prj };
}

现在您可以将它用于您的几何图形。我不想满足距离策略概念的所有标准，因此您不能将上述内容与 boost::geometry::distance.

一起使用

但是由于您的输入几何图形点数较少，您可能会使用 "brute-forcing"（不需要库内部 closest_feature 选择）：

R a = gen_rect(),
  b = gen_rect();

// make sure a and b don't overlap (distance > 0)
while (!bg::disjoint(a,b)) { b = gen_rect(); }

std::cout
    << wkt(a) << "\n"
    << wkt(b) << "\n"
    << bg::distance(a, b) << " apart\n";

DistancePoint nearest;
P const* which = nullptr;

for (auto& [a,b] : { std::tie(a,b), std::tie(b,a) } ) {
    auto segments = boost::make_iterator_range(bg::segments_begin(a), bg::segments_end(a));
    auto points   = boost::make_iterator_range(bg::points_begin(b), bg::points_end(b));

    for (auto&& pq : segments) {
        for (auto&& r : points) {
            auto d = point_to_segment(r, *pq.first, *pq.second);

            if (!which || d.distance < nearest.distance) {
                which = &r;
                nearest = d;
            }
        }
    }
}

std::cout << wkt(which) << " at " << nearest.distance << " from " << wkt(nearest.projected_point) << "\n";

演示

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/util/range.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/algorithms/convex_hull.hpp>
#include <boost/geometry/algorithms/point_on_surface.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/range/adaptors.hpp>
#include <iostream>
#include <fstream>

namespace bg = boost::geometry;
namespace bgm = boost::geometry::model;
using namespace boost::adaptors;
using bg::wkt;

using P = bgm::d2::point_xy<double>;
using B = bgm::box<P>;
using S = bgm::segment<P>;
using R = bgm::polygon<P>;

R gen_rect(); // generates a random rectangle

namespace {
    struct DistancePoint {
        double distance;
        P projected_point;
    };

    // after strategy::distance::projected_point<>
    template <typename Strategy = bg::strategy::distance::pythagoras<> >
    DistancePoint point_to_segment(P const& p, P const& p1, P const& p2) {
        P v = p2, w = p;
        bg::subtract_point(v, p1);
        bg::subtract_point(w, p1);

        auto const c1 = bg::dot_product(w, v);
        if (c1 <= 0)  return { Strategy::apply(p, p1), p1 };

        auto const c2 = bg::dot_product(v, v);
        if (c2 <= c1) return { Strategy::apply(p, p2), p2 };

        P prj = p1;
        bg::multiply_value(v, c1/c2);
        bg::add_point(prj, v);

        return { Strategy::apply(p, prj), prj };
    }
}

int main() {
    std::cout << std::setprecision(2);

    for (auto i = 0; i<10; ++i) {
        R a = gen_rect(),
          b = gen_rect();

        // make sure a and b don't overlap (distance > 0)
        while (!bg::disjoint(a,b)) { b = gen_rect(); }

        std::cout
            << wkt(a) << "\n"
            << wkt(b) << "\n"
            << bg::distance(a, b) << " apart\n";

        DistancePoint nearest;
        P const* which = nullptr;

        for (auto& [a,b] : { std::tie(a,b), std::tie(b,a) } ) {
            auto segments = boost::make_iterator_range(bg::segments_begin(a), bg::segments_end(a));
            auto points   = boost::make_iterator_range(bg::points_begin(b), bg::points_end(b));

            for (auto&& pq : segments) {
                for (auto&& r : points) {
                    auto d = point_to_segment(r, *pq.first, *pq.second);

                    if (!which || d.distance < nearest.distance) {
                        which = &r;
                        nearest = d;
                    }
                }
            }
        }

        std::cout << wkt(which) << " at " << nearest.distance << " from " << wkt(nearest.projected_point) << "\n";

        {
            std::ofstream svg("output" + std::to_string(i) + ".svg");
            boost::geometry::svg_mapper<P> mapper(svg, 400, 400, "style='fill-opacity:1;fill:rgb(255,255,255)'");
            mapper.add(a);
            mapper.add(b);
            S dline {*which, nearest.projected_point};
            mapper.add(dline);

            mapper.map(a, "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:2");
            mapper.map(b, "fill-opacity:0.5;fill:rgb(204,153,0);stroke:rgb(202,153,0);stroke-width:2");
            mapper.map(dline, "stroke-dasharray:1,1;stroke:rgb(255,0,0);stroke-width:1");
        }
    }
}

// details for generating the rectangles
#include <boost/geometry/strategies/transform/matrix_transformers.hpp>
#include <random>
std::mt19937 prng { std::random_device{}() };

static auto rand(double b, double e) { 
    return std::uniform_real_distribution<double>(b, e)(prng);
}

R gen_rect() {
    B initial {{0, 0}, { rand(0.1, 1), rand(0.1, 1) } };
    R raw, rect; // todo rotate and stuff
    bg::assign(raw, initial);

    using namespace bg::strategy::transform;
    auto rot   = rand(-M_PI, +M_PI);
    auto scale = rand(1, 3);
    auto x     = rand(-5, 5),
         y     = rand(-5, 5);

    matrix_transformer<double, 2, 2> xfrm(
         scale* cos(rot), scale*sin(rot), x,
         scale*-sin(rot), scale*cos(rot), y,
                       0,              0, 1);

    bg::transform(raw, rect, xfrm);
    bg::correct(rect);
    return rect;
}

这会生成一些随机场景，例如：

如何找到在两个矩形之间形成最近距离的两个点？

How to find two points that form closest distance between two rectangles?

geometry

boost

boost-geometry

演示