Как называется этот алгоритм выпуклой оболочки для двумерных выпуклых плоскостей? - PullRequest
Новая
       56

Как называется этот алгоритм выпуклой оболочки для двумерных выпуклых плоскостей?

1 голос
/ 10 июня 2019

Я нашел алгоритм выпуклой оболочки, который упорядочивает набор заданных точек трехмерной выпуклой плоскости после проекции в 2D. Как называется этот алгоритм? Я посмотрел общие алгоритмы: марш Джарвиса, QuickHall, Чана, сканирование Грэма и ни один из них не подходит. Код: 

private void buildConvexHull() {
        Point3D[] projPoints = new Point3D[unorderedPoints.length];

        for (int i = 0; i < unorderedPoints.length; i++) {
            Point p = orthoView.project(unorderedPoints[i]); //Orthogonal projection for representing three-dimensional points in two dimensions.
            projPoints[i] = new Point3D(p.x, p.y, 0.0); //projected point without third dimension
        }

        vertices = new Point3D[1];

        //determine the point with smallest x coordinate.
        Point3D bottom = projPoints[0];
        vertices[0] = unorderedPoints[0];
        for (int i = 1; i < projPoints.length; i++) {
            if (projPoints[i].x < bottom.x) {   // if (projPoints[i].y < bottom.y) {
                bottom = projPoints[i];
                vertices[0] = unorderedPoints[i];
            }
        }

        Point3D p = bottom;

        Point3D[] v = new Point3D[1];
        v[0] = p;

        do {
            int i = 0;
            if (projPoints[0] == p) {
                i = 1;
            }

            Point3D candidate = projPoints[i];

            HalfSpace h = new HalfSpace(p, candidate);

            int index = i;

            for (i = i + 1; i < projPoints.length; i++) {
                if (projPoints[i] != p && h.isInside(projPoints[i]) < 0) {
                    candidate = projPoints[i];
                    h = new HalfSpace(p, candidate);
                    index = i;
                }
            }

            Point3D[] vnew = new Point3D[v.length + 1];
            System.arraycopy(v, 0, vnew, 0, v.length);
            v = vnew;
            v[v.length - 1] = candidate;

            Point3D[] verticesnew = new Point3D[vertices.length + 1];
            System.arraycopy(vertices, 0, verticesnew, 0, vertices.length);
            vertices = verticesnew;
            vertices[vertices.length - 1] = unorderedPoints[index];

            p = candidate;
        } while (p != bottom);
    }

Метод isInside класса Halfspace: 

/**
     * A method checking if the given point is inside the halfspace.
     *
     * @return 1 if it is inside, 0 if it is on the line and otherwise -1.
     */
    int isInside(Point3D x) {
        Point3D n = a.normal(b, x);

        double dz = n.z - a.z;

        if (dz > 0) {
            return 1;
        } else if (dz < 0) {
            return -1;
        } else {
            return 0;
        }
    }

Насколько я понимаю, алгоритм выбирает точку в каждой итерации из набора точек, которые еще не принадлежат выпуклой оболочке и последней, которая была добавлена ​​в оболочку. Затем создается линия между этими двумя. Если ни одна из других точек не находится на внешней стороне, то выбранная точка является следующей точкой и добавляется к набору обработанных точек. Это правильно?

...