Boost::convex_hull 个 STL 容器中的分散二维点
Boost::convex_hull of scattered 2-D points in STL container
我有一个二维点向量。让我们假设它们的形式是 std::pair。我想用boost来计算凸包。这就是问题所在。我该怎么做?
我找到的唯一文档就像基本原理和琐事课程的毕业论文。
填空:
#include <iostream>
#include <vector>
#include <utility>
// BLANK boost include-files
// #include <boost/geometry.hpp>
// #include <boost/geometry/geometries/polygon.hpp> // Noop.
// #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
// BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
int main() {
// Serving suggestion
std::vector<std::pair<int, int>> A{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 }, \
{0,0},{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
std::vector<std::pair<int, int>> the_hull; // Fill this, please.
// BLANK - Boost magic goes here.
// Print convex hull of A
for (auto h: the_hull) {
std::cout << h.first << "," << h.second << "\n";
}
std::cout<< std::endl;
return 0;
}
VC++ 用户请注意。使用 VC++ 2017,我在编译以下答案时遇到了很多麻烦。我终于让它工作了。我使用 boost 1.66 的 windows 二进制文件重新安装了 boost。接下来我必须将以下两行添加到项目属性
_SILENCE_ALL_CXX17_DEPRECATION_WARNINGS;_SCL_SECURE_NO_WARNINGS
IDE 将那些 "warnings" 视为致命的。禁用所有警告是不够的。此外,一些 "deprecation warnings" 似乎是微软的指责,而不是正式弃用的 C++ 东西。
您可以将点向量转换为多点类型。
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
int main(){
typedef boost::geometry::model::d2::point_xy<double> point_type;
std::vector<std::pair<int, int>> A{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 },
{0,0},{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
boost::geometry::model::multi_point<point_type> pts;
for (const auto& pt : A){
pts.emplace_back(pt.first,pt.second);
}
boost::geometry::model::polygon<point_type> poly;
boost::geometry::convex_hull (pts, poly);
std::cout << boost::geometry::wkt(poly) << std::endl;
std::vector<std::pair<int, int>> the_hull; // Fill this, please.
for (auto it = poly.outer().begin(); it != poly.outer().end(); ++it)
the_hull.emplace_back(it->x(), it->y());
// Print convex hull of A
for (auto h: the_hull) {
std::cout << h.first << "," << h.second << "\n";
}
return 0;
}
有一种方法可以在不将数据从容器复制到 multi_point
的情况下执行此操作,反之亦然。
您必须将向量容器和对注册为 multi_point
和 point
实体。
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/multi/geometries/register/multi_point.hpp>
#include<iostream>
BOOST_GEOMETRY_REGISTER_POINT_2D(decltype(std::pair<int, int>{}), int, cs::cartesian, first, second)
BOOST_GEOMETRY_REGISTER_MULTI_POINT(decltype(std::vector<std::pair<int, int>>{}))
int main(){
std::vector<std::pair<int, int>> A{
{ 0,3 },{ 1,4 },{ 2,2 },{ 1,0 }, { 0,0 }, { 2,0 }, { 0,1 }, { 0,2 },
{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 }, { 4,2 }
};
std::cout << "A: " << boost::geometry::wkt(A) << std::endl;
std::vector<std::pair<int, int>> B;
boost::geometry::convex_hull(A, B);
std::cout << "B: " << boost::geometry::wkt(B) << std::endl;
}
输出:
A: MULTIPOINT((0 3),(1 4),(2 2),(1 0),(0 0),(2 0),(0 1),(0 2),(3 1),(3 3),(4 4),(4 3),(4 2))
B: MULTIPOINT((0 0),(0 3),(1 4),(4 4),(4 2),(2 0),(0 0)
这适用于 Fedora 27、gcc 7.2.1、clang++ 4.0.1、Boost 1.64
对于 Visual C++ 2017,Boost 1.66,有必要将这些添加到 properties/C C++/Preprocessor/Preprocessor 定义
_SILENCE_ALL_CXX17_DEPRECATION_WARNINGS;_SCL_SECURE_NO_WARNINGS
Visual Studio IDE 将那些 "warnings" 视为致命的。禁用所有警告是不够的。此外,一些 "deprecation warnings" 似乎是 Microsoft 特定的,而不是正式弃用的 C++ 东西。
您可以使用 BOOST_GEOMETRY_REGISTER_POINT_2D 宏注册您的点类型 std::pair<int,int>
,然后使用它。而且您不需要多点。这里有一个例子。希望对您有所帮助:
#include <iostream>
#include <utility>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/polygon.hpp>
using Point = std::pair<int,int>;
BOOST_GEOMETRY_REGISTER_POINT_2D(Point, int, boost::geometry::cs::cartesian, first, second)
int main()
{
std::vector<Point> v{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 },{ 0,0 },{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
using Polygon = boost::geometry::model::polygon<Point>;
Polygon poly, hull;
poly.outer().assign(v.begin(), v.end());
boost::geometry::convex_hull (poly, hull);
using boost::geometry::dsv;
std::cout << "polygon" << dsv(poly) << std::endl
<< "hull: " << dsv(hull) << std::endl;
return 0;
}
我有一个二维点向量。让我们假设它们的形式是 std::pair
我找到的唯一文档就像基本原理和琐事课程的毕业论文。
填空:
#include <iostream>
#include <vector>
#include <utility>
// BLANK boost include-files
// #include <boost/geometry.hpp>
// #include <boost/geometry/geometries/polygon.hpp> // Noop.
// #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
// BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
int main() {
// Serving suggestion
std::vector<std::pair<int, int>> A{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 }, \
{0,0},{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
std::vector<std::pair<int, int>> the_hull; // Fill this, please.
// BLANK - Boost magic goes here.
// Print convex hull of A
for (auto h: the_hull) {
std::cout << h.first << "," << h.second << "\n";
}
std::cout<< std::endl;
return 0;
}
VC++ 用户请注意。使用 VC++ 2017,我在编译以下答案时遇到了很多麻烦。我终于让它工作了。我使用 boost 1.66 的 windows 二进制文件重新安装了 boost。接下来我必须将以下两行添加到项目属性
_SILENCE_ALL_CXX17_DEPRECATION_WARNINGS;_SCL_SECURE_NO_WARNINGS
IDE 将那些 "warnings" 视为致命的。禁用所有警告是不够的。此外,一些 "deprecation warnings" 似乎是微软的指责,而不是正式弃用的 C++ 东西。
您可以将点向量转换为多点类型。
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
int main(){
typedef boost::geometry::model::d2::point_xy<double> point_type;
std::vector<std::pair<int, int>> A{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 },
{0,0},{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
boost::geometry::model::multi_point<point_type> pts;
for (const auto& pt : A){
pts.emplace_back(pt.first,pt.second);
}
boost::geometry::model::polygon<point_type> poly;
boost::geometry::convex_hull (pts, poly);
std::cout << boost::geometry::wkt(poly) << std::endl;
std::vector<std::pair<int, int>> the_hull; // Fill this, please.
for (auto it = poly.outer().begin(); it != poly.outer().end(); ++it)
the_hull.emplace_back(it->x(), it->y());
// Print convex hull of A
for (auto h: the_hull) {
std::cout << h.first << "," << h.second << "\n";
}
return 0;
}
有一种方法可以在不将数据从容器复制到 multi_point
的情况下执行此操作,反之亦然。
您必须将向量容器和对注册为 multi_point
和 point
实体。
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/multi/geometries/register/multi_point.hpp>
#include<iostream>
BOOST_GEOMETRY_REGISTER_POINT_2D(decltype(std::pair<int, int>{}), int, cs::cartesian, first, second)
BOOST_GEOMETRY_REGISTER_MULTI_POINT(decltype(std::vector<std::pair<int, int>>{}))
int main(){
std::vector<std::pair<int, int>> A{
{ 0,3 },{ 1,4 },{ 2,2 },{ 1,0 }, { 0,0 }, { 2,0 }, { 0,1 }, { 0,2 },
{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 }, { 4,2 }
};
std::cout << "A: " << boost::geometry::wkt(A) << std::endl;
std::vector<std::pair<int, int>> B;
boost::geometry::convex_hull(A, B);
std::cout << "B: " << boost::geometry::wkt(B) << std::endl;
}
输出:
A: MULTIPOINT((0 3),(1 4),(2 2),(1 0),(0 0),(2 0),(0 1),(0 2),(3 1),(3 3),(4 4),(4 3),(4 2))
B: MULTIPOINT((0 0),(0 3),(1 4),(4 4),(4 2),(2 0),(0 0)
这适用于 Fedora 27、gcc 7.2.1、clang++ 4.0.1、Boost 1.64
对于 Visual C++ 2017,Boost 1.66,有必要将这些添加到 properties/C C++/Preprocessor/Preprocessor 定义
_SILENCE_ALL_CXX17_DEPRECATION_WARNINGS;_SCL_SECURE_NO_WARNINGS
Visual Studio IDE 将那些 "warnings" 视为致命的。禁用所有警告是不够的。此外,一些 "deprecation warnings" 似乎是 Microsoft 特定的,而不是正式弃用的 C++ 东西。
您可以使用 BOOST_GEOMETRY_REGISTER_POINT_2D 宏注册您的点类型 std::pair<int,int>
,然后使用它。而且您不需要多点。这里有一个例子。希望对您有所帮助:
#include <iostream>
#include <utility>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/polygon.hpp>
using Point = std::pair<int,int>;
BOOST_GEOMETRY_REGISTER_POINT_2D(Point, int, boost::geometry::cs::cartesian, first, second)
int main()
{
std::vector<Point> v{ { 0,3 },{ 1,4 },{ 2,2 },{ 1,0 },{ 0,0 },{ 2,0 },{ 0,1 },{ 0,2 },{ 3,1 },{ 3,3 },{ 4,4 },{ 4,3 },{ 4,2 } };
using Polygon = boost::geometry::model::polygon<Point>;
Polygon poly, hull;
poly.outer().assign(v.begin(), v.end());
boost::geometry::convex_hull (poly, hull);
using boost::geometry::dsv;
std::cout << "polygon" << dsv(poly) << std::endl
<< "hull: " << dsv(hull) << std::endl;
return 0;
}