我想計算一組點的凸包。我在網上找到的大多數演算法都會回傳一個點串列，但我需要一個點的索引串列。
為此，我采用了一些計算點的現有代碼，并嘗試將其更改為回傳點索引。
回傳凸包點向量的原始函式
#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
我希望看到相同的結果。
我錯過了什么？
uj5u.com熱心網友回復：
在您的程式/函式中，您正在對點進行排序，然后與船體一起計算索引。然后回傳索引（基于排序的向量）。然后將索引應用于未排序的向量。
請記住，C 可以通過參考或值/副本傳遞（我可能有點含糊，但我希望你明白；如果你不知道我在說什么，那么這是你必須學習的主題）。
你可以在第二個程式中做的是：在列印之前對向量進行排序。也許這會給你預期的結果。
更好的解決方案需要更多的努力：通過參考傳遞
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424335.html