내 솔루션에 무엇이 누락 되었습니까? 컨벡스 선체 찾기 알고리즘

Question

나는이 문제를 해결하기 위해 몇 일 동안 내 머리를 감쌌다. 내 알고리즘이 누락 될 수 있음을 알 수 없다. 이것은 내가 다소 원형 시계 반대 방향 순서로 포인트를 얻고 수집 것에서 문제 here.

입니다. 그래서 그레이엄 스캔 버전을 구현했습니다. 그레이엄 스캔은 볼록 선체를 찾기 위해 항상 오른손 회전을하는 점을 사용하여이를 확인합니다.

내 알고리즘은 모든 주어진 테스트 입력을 위해 작동하고 모든 입력 내가 그것을 위해 올 수 있지만 단지 '완료'로 할당에 필요한 것입니다 온라인 판사에 의해 허용되지 않습니다.

어쨌든, 여기 누군가가 내가 빠진 것을 발견 할 수 있다면 내 빚이 영원히 남을 것입니다.

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; 
} 
} 

Answer 1

소리에서 Graham Scan이 적용되는 지점이 정렬됩니다. 따라서 스택 작업 (handlePoints) 아마 맞지 않을 것 같아요.

나는 앤드류의 알고리즘 (그레이엄 스캔의 변경)에 더 많이 사용 해요,하지만 난 당신이 볼록 선체 내부와 while 루프의 외부에 포인트를 추가하지 않아야 상당히 확신합니다. 그 이유는 while 루프의 목적이 어떤 알고리즘이 사용되는지에 관계없이 똑같이 유지된다는 것이 확실하기 때문입니다. 볼록 선체에서 잘못된 점을 제거하는 것입니다. 그러나 while 루프 중에 포인트를 추가 할 가능성이 있습니다.

그게 모두 다 고쳐야 할 필요는 없지만, 지금 자바를 실행하도록 설정 한 것이 없습니다.