30 #ifndef EXOTICA_CORE_TASK_MAPS_CONVEXHULL_H_ 31 #define EXOTICA_CORE_TASK_MAPS_CONVEXHULL_H_ 33 #include <Eigen/Dense> 42 return (p(1) - p1(1)) * (p2(0) - p1(0)) - (p2(1) - p1(1)) * (p(0) - p1(0));
49 std::list<int> new_half_points;
50 for (
const int& i : half_points)
52 double d =
DetDiff2D(points.row(p1).transpose(), points.row(p2).transpose(), points.row(i).transpose());
55 new_half_points.push_back(i);
71 hull.splice(hull.begin(),
QuickHull(points, new_half_points, p1, ind));
72 hull.splice(hull.end(),
QuickHull(points, new_half_points, ind, p2));
80 if (points.cols() != 2)
ThrowPretty(
"Input must contain 2D points!");
82 int n = points.rows();
85 std::list<int> half_points;
88 for (
int i = 0; i < n; ++i) hull.push_back(i);
92 int min_x = 0, max_x = 0;
93 half_points.push_back(0);
94 for (
int i = 1; i < n; ++i)
96 if (points(i, 0) < points(min_x, 0))
98 if (points(i, 0) > points(max_x, 0))
100 half_points.push_back(i);
102 hull.splice(hull.begin(),
QuickHull(points, half_points, min_x, max_x));
103 hull.splice(hull.end(),
QuickHull(points, half_points, max_x, min_x));
110 #endif // EXOTICA_CORE_TASK_MAPS_CONVEXHULL_H_
const Eigen::Ref< const Eigen::MatrixXd > & MatrixXdRefConst
double DetDiff2D(Eigen::VectorXdRefConst p1, Eigen::VectorXdRefConst p2, Eigen::VectorXdRefConst p)
DetDiff2D Computes the 2D determinant (analogous to a 2D cross product) of a two vectors defined by P...
std::list< int > ConvexHull2D(Eigen::MatrixXdRefConst points)
const Eigen::Ref< const Eigen::VectorXd > & VectorXdRefConst
std::list< int > QuickHull(Eigen::MatrixXdRefConst points, std::list< int > &half_points, int p1, int p2)