获取凸包指数

Question

我想计算一组点的凸包。我在网上找到的大多数算法 return 点列表，但我需要点的索引列表。

为此，我采用了一些计算点的现有代码，并尝试将其更改为 return 点索引。

return 凸包点向量的原始函数

#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 向量。然后，我尝试将每个循环中的当前索引添加到此向量，以 return 基于传递给函数的点的索引。

新函数更改为return点索引

#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

我希望看到相同的结果。

我错过了什么？

Answer 1

在您的 program/function 中，您正在对点进行排序，然后计算索引以及船体。而你 return 索引（基于排序的向量）。然后将索引应用于未排序的向量。

请记住，C++ 可以通过引用或 value/copy（我可能有点含糊，但我希望你能理解；如果你不知道我在说什么，那么这就是你的主题了解）。

你可以在第二个程序中做的是：在打印之前对矢量进行排序。也许这会给你预期的结果。

更好的解决方案需要更多的努力：通过引用传递

获取凸包指数

Get convex hull indices

c++

algorithm

convex-polygon