用经度和纬度提升凸包

Question

我正在尝试将 boost 的 convex_hull 算法与 longitude/latitude 坐标一起使用。

从这里开始：https://archive.fosdem.org/2017/schedule/event/geo_boost_geography/attachments/slides/1748/export/events/attachments/geo_boost_geography/slides/1748/FOSDEM17_vissarion.pdf

我看到我们可以计算两点之间的距离，甚至可以使用 longitude/latitude 坐标求出面积（参见 PDF 文档的第 19 和 22 页）。

结合 https://www.boost.org/doc/libs/1_75_0/libs/geometry/doc/html/geometry/reference/algorithms/convex_hull.html

我想出了这个：https://wandbox.org/permlink/2AGPUtHPWrlGFMTf，但它不能编译，为了方便，这里代码：

#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>

namespace bg = boost::geometry;

int main()
{
    typedef bg::model::point<double, 2, bg::cs::geographic<bg::degree>> point;
    typedef boost::geometry::model::polygon<point> polygon;
    polygon poly;
    bg::read_wkt(" POLYGON ((4.346693 50.858306, 4.367945 50.852455, 4.366227 50.840809, 4.344961 50.833264, 4.338074 50.848677,4.346693 50.858306))",
    poly );
    
    polygon hull;
    boost::geometry::convex_hull(poly, hull);

    using boost::geometry::dsv;
    std::cout << "polygon: " << dsv(poly) << std::endl << "hull: " << dsv(hull) << std::endl;
}

非常感谢任何帮助。

Answer 1

是的，虽然你可能是对的，/可以/制定一个策略，但没有实施。

一个小并排测试器清楚地表明该策略未针对地理坐标系实施：

template <typename cs> void test() {
    using point   = bg::model::point<double, 2, cs>;
    using polygon = bg::model::polygon<point>;
    polygon poly;
    bg::read_wkt("POLYGON((4.346693 50.858306, 4.367945 50.852455, 4.366227 "
                 "50.840809, 4.344961 50.833264, 4.338074 50.848677,4.346693 "
                 "50.858306))",
                 poly);

    std::cout << std::fixed;
    std::cout << "Polygon:   " << bg::dsv(poly)       << std::endl;
    std::cout << "Perimeter: " << bg::perimeter(poly) << std::endl;
    std::cout << "Area:      " << bg::area(poly)      << std::endl;

    using Strategy = typename bg::strategy_convex_hull<polygon, point>::type;
    std::cout << "Strategy " << boost::core::demangle(typeid(Strategy).name()) << "\n";

    if constexpr (not std::is_same_v<Strategy, bg::strategy::not_implemented>) {
        polygon hull;
        bg::convex_hull(poly, hull);
        std::cout << "Hull: " << bg::dsv(hull) << std::endl;
    }
}

它还表明实施了其他一些策略（例如距离）。

看到了Live On Coliru

int main() {
    std::cout << "Cartesian:\n";
    std::cout << "----------\n";
    test<bg::cs::cartesian>();

    std::cout << "\nGeographic:\n";
    std::cout <<   "-----------\n";
    test<bg::cs::geographic<bg::degree>>();
}

简化输出中的类型名称：

    Cartesian:
    ----------
    Polygon:   (((4.346693, 50.858306), (4.367945, 50.852455), (4.366227, 50.840809), (4.344961, 50.833264), (4.338074, 50.848677), (4.346693, 50.858306)))
    Perimeter: 0.086184
    Area:      0.000488
    Strategy bg::strategy::convex_hull::graham_andrew<polygon, point>
    Hull: (((4.338074, 50.848677), (4.346693, 50.858306), (4.367945, 50.852455), (4.366227, 50.840809), (4.344961, 50.833264), (4.338074, 50.848677)))

    Geographic:
    -----------
    Polygon:   (((4.346693, 50.858306), (4.367945, 50.852455), (4.366227, 50.840809), (4.344961, 50.833264), (4.338074, 50.848677), (4.346693, 50.858306)))
    Perimeter: 7663.398262
    Area:      3848183.734567
    Strategy bg::strategy::not_implemented

查看 documented strategies 表明 graham_andrew 实际上是唯一可用的。

您可能应该找出需要进行哪些调整才能使事情正常进行。从技术上讲，强制 convex_hull 使用 Graham/Andrew 策略是可行的，但这似乎是不明智的，因为该特征暗示该策略是 特别地 根据坐标系：

/*!
    \brief Traits class binding a convex hull calculation strategy to a coordinate system
    \ingroup convex_hull
    \tparam Tag tag of coordinate system
    \tparam Geometry the geometry type (hull operates internally per hull over geometry)
    \tparam Point point-type of output points
*/
template
<
    typename Geometry1,
    typename Point,
    typename CsTag = typename cs_tag<Point>::type
>
struct strategy_convex_hull
{
    typedef strategy::not_implemented type;
};

深入研究战略的实施，这里有一个充满希望的提示：

    // TODO: User-defiend CS-specific side strategy
    typename strategy::side::services::default_strategy<cs_tag>::type side;

也许我们可以“完成”“只是”专门针对您的坐标系的 Side Strategy？更有趣的是：a strategy::side::geographic 存在。我对参数的理解超出了我的理解范围（例如大地测量解决方案策略意味着什么？），但也许你自己可以从那里得到它？

我相信，如果您知道需要做什么，邮件列表中乐于助人的开发人员将非常愿意指导有关如何将其放入库中的技术问题。

用经度和纬度提升凸包

Boost convex hull with longitude and latitude

c++

boost

convex-hull

boost-geometry