java - 顺时针排序顶点

Question

我正在使用此算法对 Point ClockWise 列表进行排序:

private List<Point2D> SortClockWise(List<Point2D> Points) {
    // First Calculate Center of Points
    double CenterX = 0;
    double CenterY = 0;
    for (int i = 0; i < Points.size(); i++) {
        CenterX += Points.get(i).getX();
        CenterY += Points.get(i).getY();
    }
    Point2D Center = new Point2D(CenterX / Points.size(), CenterY
            / Points.size());
    int n = Points.size();
    int k;
    for (int m = n; m >= 0; m--) {
        for (int i = 0; i < n - 1; i++) {
            k = i + 1;
            if (!less(Points.get(i), Points.get(k), Center)) {
                Point2D tmp = new Point2D();
                tmp = Points.get(i);
                Points.set(i, Points.get(k));
                Points.set(k, tmp);
            }
        }
    }
    for (int i = 0; i < Points.size(); i++) {
        mTempShape.add(Points.get(i));
    }
    return mTempShape;
}

private Boolean less(Point2D a, Point2D b, Point2D center) {
    if (a.getX() - center.getX() >= 0 && b.getX() - center.getX() < 0)
        return true;
    if (a.getX() - center.getX() < 0 && b.getX() - center.getX() >= 0)
        return false;
    if (a.getX() - center.getX() == 0 && b.getX() - center.getX() == 0) {
        if (a.getY() - center.getY() >= 0 || b.getY() - center.getY() >= 0)
            return (a.getY() > b.getY());
        return b.getY() > a.getY();
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    double det = (a.getX() - center.getX()) * (b.getY() - center.getY())
            - (b.getX() - center.getX()) * (a.getY() - center.getY());
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    double d1 = (a.getX() - center.getX()) * (a.getX() - center.getX())
            + (a.getY() - center.getY()) * (a.getY() - center.getY());
    double d2 = (b.getX() - center.getX()) * (b.getX() - center.getX())
            + (b.getY() - center.getY()) * (b.getY() - center.getY());
    return d1 > d2;
}

问题在某些情况下是这样的:

算法给了我在图片中绘制的黑线，但我想要得到的是图片中的编号顶点。

Answer 1

我会尝试一种首先将所有内容拆分为多边形的方法。从点 1 开始，然后遍历多边形中的顶点，直到到达共享的顶点。然后你必须改变多边形。毕竟，如果你只有点，而没有定义边(隐式或显式)，你只能有一个凸形。