3

だから私は凸包アルゴリズムについて学んでいて、単純なブルートフォースからグラハム スキャンまでのすべてのアルゴリズムを書き上げています。

これは私のブルートフォース O(n^4) アルゴリズムです。最初に、すべてのポイントが船体の一部であると想定します。可能な三角形ごとに、三角形の内側にあるすべての点を削除します。最終的に、排除されなかったポイントは船体の一部になります。

Javaコードは次のとおりです（修正済み：Thomashのソリューションを使用）

public List<Point> naive(List<Point> points) {
    if (points == null)
        return Collections.emptyList();
    if (points.size() <= 3)
        return points;
    boolean[] extremePoints = new boolean[points.size()];
    Arrays.fill(extremePoints, true);
    for (int i = 0, sz = points.size(); i < sz; i++) {
        if (extremePoints[i])
            for (int j = 0; j < sz; j++) {
                if (i != j && extremePoints[j]) {
                    for (int k = 0; k < sz; k++) {
                        if (k != i && k != j) {
                            for (int l = 0; l < sz; l++) {
                                if (extremePoints[l] && l != i && l != j
                                        && l != k) {
                                    // Check if P[l] lies in triangle formed
                                    // by
                                    // P[i],P[j],P[k]

                                    Polygon p = new Polygon();
                                    p.addPoint(points.get(i).x,
                                            points.get(i).y);
                                    p.addPoint(points.get(j).x,
                                            points.get(j).y);
                                    p.addPoint(points.get(k).x,
                                            points.get(k).y);
                                    if (p.contains(points.get(l)))
                                        extremePoints[l] = false;
                                }
                            }
                        }
                    }
                }
            }
    }

    Point centerOfHull = null; // Arbitrary point inside the hull
    // Order?
    for (int i = 0; i < extremePoints.length; i++) {
        if (!extremePoints[i]) {
            centerOfHull = points.get(i);
            break;
        }
    }
    List<Point> convexHull = new ArrayList<Point>();
    for (int i = 0; i < extremePoints.length; i++) {
        if (extremePoints[i]) {
            convexHull.add(points.get(i));
        }
    }
    Collections.sort(convexHull, new PointComp(centerOfHull));
    // or use a heap. still O(nlogn)
    return convexHull;
}

private class PointComp implements Comparator<Point> {

    private Point center;

    public PointComp(Point center) {
        this.center = center;
    }

    @Override
    public int compare(Point o1, Point o2) {
        double angle1 = Math.atan2(o1.y - center.y, o1.x - center.x);
        double angle2 = Math.atan2(o2.y - center.y, o2.x - center.x);
        if (angle1 < angle2)
            return 1;
        else if (angle2 > angle1)
            return -1;
        return 0;
    }
}

これらの点を視覚的に見てみましたが、正しいようですが、凸包ポリゴンを描画するための点の順序を確立する方法がわかりませんか? どんな助けでも大歓迎です。

4

2 に答える 2

2

どの点が船体の一部であるかを力ずくで見つける場合は、点の順序を見つけるために醜いことを続けたほうがよいでしょう。

  1. 左上のポイントから始めます。
  2. その点から他のすべての点までの角度を計算します。
  3. 角度が 0 度に最も近い点をピックします。これは船体を時計回りに回る次のポイントです。
  4. すすぎ、泡立て、繰り返します。

船体を一周するときにターゲット角度を調整する必要がありますが、これでうまくいきます (紙の上で行う方法の 1 つです)。

于 2012-05-09T10:13:14.147 に答える
1

凸包内の点 O と別の点 A を選択します。凸包内の各 B について、角度 AÔB を計算し、これらの角度を使用して点を並べ替えます (AÔB < AÔB' の場合、B < B' と見なします)。

于 2012-05-09T10:18:35.613 に答える