我想计算一组点的凸包。我在网上找到的大多数算法都会返回一个点列表,但我需要一个点的索引列表。
为此,我采用了一些计算点的现有代码,并尝试将其更改为返回点索引。
返回凸包点向量的原始函数
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
typedef std::tuple<int, int> point;
// returns true if the three points make a counter-clockwise turn
bool ccw(const point &a, const point &b, const point &c) {
return ((std::get<0>(b) - std::get<0>(a)) * (std::get<1>(c) - std::get<1>(a)))
> ((std::get<1>(b) - std::get<1>(a)) * (std::get<0>(c) - std::get<0>(a)));
}
std::vector<point> convexHull(std::vector<point> p) {
if (p.size() == 0) return std::vector<point>();
std::sort(p.begin(), p.end(), [](point &a, point &b) {
if (std::get<0>(a) < std::get<0>(b)) return true;
return false;
});
std::vector<point> h;
// lower hull
for (const auto &pt: p) {
while (h.size() >= 2 && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
h.pop_back();
}
h.push_back(pt);
}
// upper hull
auto t = h.size() + 1;
for (auto it = p.crbegin(); it != p.crend(); it = std::next(it)) {
auto pt = *it;
while (h.size() >= t && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
h.pop_back();
}
h.push_back(pt);
}
h.pop_back();
return h;
}
int main() {
using namespace std;
vector<point> points = {
make_pair(16, 3), make_pair(12, 17), make_pair(0, 6), make_pair(-4, -6), make_pair(16, 6),
make_pair(16, -7), make_pair(16, -3), make_pair(17, -4), make_pair(5, 19), make_pair(19, -8),
make_pair(3, 16), make_pair(12, 13), make_pair(3, -4), make_pair(17, 5), make_pair(-3, 15),
make_pair(-3, -9), make_pair(0, 11), make_pair(-9, -3), make_pair(-4, -2), make_pair(12, 10)
};
auto hull = convexHull(points);
for (const auto &point: hull) {
std::cout << get<0>(point) << ", " << get<1>(point) << std::endl;
}
return 0;
}
结果
-9, -3
-3, -9
19, -8
17, 5
12, 17
5, 19
-3, 15
我已经使用了这段代码,还添加了一个indices
向量。然后,我尝试将每个循环中的当前索引添加到此向量,以根据传递给函数的点返回索引。
新函数更改为返回点的索引
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
typedef std::tuple<int, int> point;
// returns true if the three points make a counter-clockwise turn
bool ccw(const point &a, const point &b, const point &c) {
return ((std::get<0>(b) - std::get<0>(a)) * (std::get<1>(c) - std::get<1>(a)))
> ((std::get<1>(b) - std::get<1>(a)) * (std::get<0>(c) - std::get<0>(a)));
}
std::vector<int> convexHull(std::vector<point> p) {
if (p.size() == 0) return {};
std::sort(p.begin(), p.end(), [](point &a, point &b) {
if (std::get<0>(a) < std::get<0>(b)) return true;
return false;
});
std::vector<point> h;
std::vector<int> indices;
// lower hull
for (int i = 0; i < p.size(); i++) {
auto pt = p[i];
while (h.size() >= 2 && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
h.pop_back();
indices.pop_back();
}
h.push_back(pt);
indices.push_back(i);
}
// upper hull
auto t = h.size() + 1;
for (int i = p.size() - 1; i >= 0; i--) {
auto pt = p[i];
while (h.size() >= t && !ccw(h.at(h.size() - 2), h.at(h.size() - 1), pt)) {
h.pop_back();
indices.pop_back();
}
h.push_back(pt);
indices.push_back(i);
}
h.pop_back();
indices.pop_back();
return indices;
}
int main() {
using namespace std;
vector<point> points = {
make_pair(16, 3), make_pair(12, 17), make_pair(0, 6), make_pair(-4, -6), make_pair(16, 6),
make_pair(16, -7), make_pair(16, -3), make_pair(17, -4), make_pair(5, 19), make_pair(19, -8),
make_pair(3, 16), make_pair(12, 13), make_pair(3, -4), make_pair(17, 5), make_pair(-3, 15),
make_pair(-3, -9), make_pair(0, 11), make_pair(-9, -3), make_pair(-4, -2), make_pair(12, 10)
};
auto hull = convexHull(points);
for (const auto &index: hull) {
std::cout << get<0>(points[index]) << ", " << get<1>(points[index]) << std::endl;
}
return 0;
}
结果
16, 3
-4, -6
12, 10
-9, -3
3, -4
19, -8
16, 6
我希望看到相同的结果。
我错过了什么?