0

我正在尝试将此处给出的 C++ 代码翻译 成 MATLAB：

// Implementation of Andrew's monotone chain 2D convex hull algorithm.
// Asymptotic complexity: O(n log n).
// Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine.
#include <algorithm>
#include <vector>
using namespace std;

typedef int coord_t;         // coordinate type
typedef long long coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2

struct Point {
    coord_t x, y;

    bool operator <(const Point &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> convex_hull(vector<Point> P)
{
    int n = P.size(), k = 0;
    vector<Point> H(2*n);

    // Sort points lexicographically
    sort(P.begin(), P.end());

    // Build lower hull
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    // Build upper hull
    for (int i = n-2, t = k+1; i >= 0; i--) {
        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    H.resize(k);
    return H;
}

我遇到了一些麻烦，因为在 C++ 程序中，遍历这些点更容易。我希望在 MATLAB 中做同样的事情，但希望一次取一个点（x 和 y 坐标），而不是一次在给定索引处取一个特定值。

为了生成坐标矩阵，我现在使用以下 -

x = randi(1000,100,1);
y = randi(1000,100,1);
points = [x,y];
4

2 回答 2

1

在 Matlab 中，迭代通常是不必要的。鉴于您的向量x，y我认为 C++ 代码转换为

convhull(x,y)

在 Matlab 中。没有（程序员编写的）迭代，也没有太多。

于 2013-09-03T05:53:11.987 回答
0

如果你有一个矩阵 C 列乘 2 行 M，你就可以了。（其中第 1 行 =x 和第 2 行 = y）

M=[x;y]
FOR point = drange(M)
    //code
end
于 2013-09-02T20:59:41.503 回答