Почему мой выпуклый алгоритм Халла-Джарвиса в марте добавляет одни и те же строки несколько раз - PullRequest
Новая
       34

Почему мой выпуклый алгоритм Халла-Джарвиса в марте добавляет одни и те же строки несколько раз

0 голосов
/ 04 апреля 2020

Я пытаюсь написать свою собственную программу Convex Hull Jarvis March, и я знаю, что это определенно не лучший способ кодирования этого алгоритма, так как я впервые делаю эту проблему. Ниже приведен код, который я использую для вычисления выпуклой оболочки. 

public class Jarvis {

    //Find the cross product of two vectors
    public double crossProduct(Point p, Point q, Point r){
        double x1 = p.x-q.x;
        double x2 = p.x-r.x;
        double y1 = p.y-q.y;
        double y2 = p.y-r.y;

        double cross = (y2*x1) - (y1*x2);
        return cross;
    }


    public void convexHull(Point point[], Point p, Point q, int currIndex, int nextIndex, int lmIndex, Vector<Point> edge) {

        double cross;
        //Finds next point most counter clockwise away from current vector
        for (int i = 0; i < point.length; i++) {
            if (i == currIndex || i == nextIndex) {
                continue;
            } else {
                Point r = point[i];
                cross = crossProduct(p, q, r);
                if (cross > 0) {
                    q = point[i];
                    currIndex = i;

                }
            }
        }
        if(!edge.contains(q)){
            edge.add(q);
        }

        //Choose random next point to use in next recursion
        boolean done = false;
        do {
            int random = ThreadLocalRandom.current().nextInt(0, 7);
            if (!edge.contains(point[random])) {
               Point r = point[random];

                if (edge.contains(point[random])) {
                    continue;
                } else{
                    if(Math.abs(point[currIndex].x-point[lmIndex].x) == 0 && Math.abs(point[currIndex].y-point[lmIndex].y) == 0){
                        edge.add(point[currIndex]);
                        edge.add(p);
                        return;
                    }else {
                        edge.add(p);
                        convexHull(point, q, r, currIndex, random, lmIndex, edge);
                        done = true;
                    }
                }

            }
        } while(done != true);

        for (Point temp :edge){
            System.out.println("(" + temp.x + ", " +
                    temp.y + ")");

    }


}
}

Где все точки передаются в функцию через точку Point []. Каждая точка имеет значение x и ay, а lmIndex - это исходный индекс самой левой точки, переданный так, чтобы программа знала, когда остановиться. Насколько я понимаю, алгоритм заключается в том, что вы сначала находите самую левую точку, а затем выбираете другую случайную точку и находите следующую самую левую точку с точки зрения первой точки. поэтому я попытался реализовать этот алгоритм в своем коде. Это работает большую часть времени. Но иногда он добавляет одну и ту же точку в ребро Vector <> несколько раз, и с некоторыми наборами данных он пропускает несколько точек, которые должны быть на выпуклой оболочке. Кто-нибудь, почему это? Любая помощь приветствуется.

...