볼록 선체 - 점의 순서를 결정합니다.

Question

그래서 볼록 선체 알고리즘에 대해 배우고 순진한 Bruteforce에서 Graham Scan까지 모든 알고리즘을 작성합니다.

이것은 내 Bruteforce O (n^4) 알고리즘입니다. 처음에는 모든 점이 선체의 일부라고 가정합니다. 가능한 한 각 삼각형에 대해 삼각형 내부에있는 모든 점을 제거하십시오. 끝 부분에서 제거되지 않은 포인트는 선체의 일부가됩니다. 나는 시각적으로 이러한 점을보고, 그들이 올바른 것 같다 시도, 그러나 나는 점의 순서를 설정하는 방법을 모르는

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

:

여기에 자바 코드 (Thomash의 솔루션 고정이)입니다 볼록 선체 다각형을 그리는거야? 어떤 도움을 주셔서 감사합니다.

Answer 1

가 볼록 선체 내부의 점 O를 선택하고 다른 점 A. 볼록 선체의 각 B에 대해 각도 AÔB를 계산하고이 각도를 사용하여 점을 정렬합니다 (AA'B '이면 B < B'로 간주).

Answer 2

어떤 점이 선체의 일부인지 찾기 위해 무차별 적으로 힘 쓰는 사람이라면, 추악한 일을 계속하여 점의 순서를 찾을 수도 있습니다.

1. 왼쪽 상단부터 시작하십시오.
2. 그 지점부터 다른 모든 지점까지의 각도를 계산하십시오.
3. 0도에 가장 가까운 각도로 점을 지정합니다. 이것은 선체 주변 시계 방향으로 다음 지점입니다.
4. 린스, 비누 거품, 반복.

당신은 당신이 선체 주위에 가서 대상 각도를 조정해야하지만,이 작품 (그리고 당신이 종이에 할 거라고 하나의 방법입니다.)