Что мне не хватает в моем решении? Алгоритм поиска выпуклой оболочки

Я уже несколько дней ломаю голову над этой проблемой... Я не вижу, чего может не хватать в моем алгоритме. Это проблема здесь.

Из того, что я понял, я получаю очки в несколько круговом порядке против часовой стрелки. Поэтому я реализовал версию сканирования Грэма, которая выполняет поиск выпуклой оболочки, гарантируя, что она использует точки, которые всегда дают повороты вправо.

Мой алгоритм работает для всех входных данных теста и всех входных данных, которые я могу для него придумать, но он просто не будет принят онлайн-судьей, что требуется для того, чтобы задание было «завершенным».

В любом случае, вот мой код. Я буду вечно у вас в долгу, если кто-нибудь сможет найти то, что мне не хватает.

import java.util.Scanner;
import java.util.Vector;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

public Main() {}

public void handlePoints(Point[] points) throws Exception {
    int m = 1;
    Vector<Point> convexHull = new Vector<Point>();
    // This is THE ONLY gaurunteed point to be in the hull - and it is the lowest left point so that's ok. 
    convexHull.add(points[0]);
    // Can be removed if ill-suited. 
    convexHull.add(points[1]);
    for (int i = 2; i < points.length; i++) {
        // Find the next valid point on the hull. 
        while (counterClockWise(convexHull.elementAt(m-1), convexHull.elementAt(m), points[i]) <= 0) {
            convexHull.removeElementAt(m);
            if (m > 1) {
                m -= 1;
            }
            // All points are colinear
            else if (i == points.length - 1) {
                break;
            }
            else {
                convexHull.add(points[i]);
                i++;
            }
        }
        convexHull.add(points[i]);
        m++;
    }   
    if (convexHull.size() <= 3) {
        throw new Exception();
    }

    String test = "" + convexHull.size() + '\n';
    for (Point p : convexHull) {
        test += p.x + " " + p.y + '\n';
    }
    System.out.print(test);
}

// Simply calculated whether or not the 3 points form a countedClockWise turn.
public int counterClockWise(Point p1, Point p2, Point p3) {
    return ((p2.x - p1.x) * (p3.y - p1.y)) - ((p2.y - p1.y) * (p3.x - p1.x));
}

// Rearranges the array to maintain its order but be started and ended by the point with the lowest y value
private static Point[] moveLowestToFront(Point[] array) {
    // Rearrange for y:
    int lowestY = 99999;
    int lowestIndex = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i].y < lowestY) {
            lowestY = array[i].y;
            lowestIndex = i;
        }
    }
    // Scan through again to see if there are any competing low-y values. 
    int lowestX = 99999;
    for (int i = 0; i < array.length; i++) {
        if (array[i].y == lowestY) {
            if (array[i].x < lowestX) {
                lowestX = array[i].x;
                lowestIndex = i;
            }
        }
    }
    Point[] rearrangedPoints = new Point[array.length];
    int j = 0;
    // Take from low to end cutting off repeated start point. 
    for (int i = lowestIndex; i < array.length - 1; i++) {
        rearrangedPoints[j] = array[i];
        j++;
    }
    // Throw the remaining and put them at the end.
    for (int i = 0; i < lowestIndex; i++) {
        rearrangedPoints[j] = array[i];
        j++;
    }
    // End the array with the repeated first point. 
    rearrangedPoints[array.length - 1] = array[lowestIndex];
    return rearrangedPoints;
}

public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    Main convexHullFinder = new Main();
    int numDataSets = sc.nextInt();
    System.out.println(numDataSets);
    for (int z = 0; z < numDataSets; z++) {
        int numPoints = sc.nextInt();
        Vector<Point> points = new Vector<Point>();
        // Read in all the points for this set. 
        points.add(new Point(sc.nextInt(), sc.nextInt()));
        int j = 1;
        for (int i = 1; i < numPoints; i++) {
            Point p = new Point(sc.nextInt(), sc.nextInt());
            // Remove repeated points. 
            if (p.x < 0 || p.y < 0) {
                throw new Exception();
            }
            if ( (p.x == points.elementAt(j-1).x) && (p.y == points.elementAt(j-1).y) ) {}
            else {
                points.add(p);
                j++;
            }
        }
        Point[] reducedPoints = points.toArray(new Point[points.size()]);

        // Rearrange the set to start and end on the lowest Y point. 
        reducedPoints = moveLowestToFront(reducedPoints);

        if (numPoints >= 3) {
            convexHullFinder.handlePoints(reducedPoints);
        }
        else {
            throw new Exception();
        }

        try { 
            System.out.println(sc.nextInt());
        }
        catch (Exception e) {

        }
    }
}
}

class Point {
public int x;
public int y;

public Point(int x, int y) {
    this.x = x;
    this.y = y;
}
}

person Alex    schedule 18.12.2012    source источник
comment
Пожалуйста, не используйте тег homework, он объявлен устаревшим.   -  person Brian    schedule 18.12.2012
comment
@ Алекс Я предлагаю вам опубликовать этот вопрос в утреннее время, то есть по тихоокеанскому времени. Некоторые из опытных кодеров могут дать вам полезную информацию об этом, поскольку они доступны к тому времени.   -  person Smit    schedule 18.12.2012
comment
Вы знаете, почему ваша домашняя работа была отклонена?   -  person giampaolo    schedule 19.12.2012
comment
При реализации этого алгоритма А. трижды проверить правильность алгоритма поворота направо, b. убедиться, что точки отсортированы лексикографически, c. проверьте, что вы на самом деле создаете обе оболочки, верхнюю и нижнюю, проходя через точки как вперед, так и назад, d. убедитесь, что вы удаляете точку из каждой секции корпуса, это необходимо, чтобы избежать дублирования точек корпуса, так как верхняя и нижняя секции будут иметь одинаковые первую и последнюю точки.   -  person Nuclearman    schedule 24.12.2012
comment
О, я также не уверен, что вы должны создавать исключения, если размер корпуса меньше 3, так как это просто означает, что корпус состоит из всех точек.   -  person Nuclearman    schedule 24.12.2012


Ответы (1)


Судя по звукам, точки сортируются таким образом, что применяется сканирование Грэма. Поэтому я думаю, что ваша операция со стеком (handlePoints), вероятно, неверна.

Я больше привык к алгоритму Эндрю (модификация Graham Scan), но я совершенно уверен, что вам не следует добавлять точки к выпуклой оболочке как внутри, так и вне цикла while. Причина в том, что я совершенно уверен, что цель цикла while остается неизменной независимо от того, какой алгоритм используется. Это нужно для удаления недопустимых точек из выпуклой оболочки. Однако есть вероятность, что вы добавляете точки во время цикла while.

Я не уверен, что это все, что нужно исправить, но на данный момент у меня нет ничего настроенного для запуска Java.

person Nuclearman    schedule 24.12.2012