graham-scan.tex

\subsection{Graham Scan -- Konvexe Huelle}
        \begin{enumerate}
        \item Finde $p_0$ mit min $y$, Unentschieden: betrachte $x$
        \item Sortiere $p_{1\ldots n}$. $p_i < p_j = ccw(p_0,p_i,p_j)$\\
        (colinear $\rightarrow$ naechster zuerst)
        \item Setze $p_{n+1}=p_0$
        \item Push($p_0$); Push($p_1$); Push($p_2$);
        \item for $i=3$ to $n+1$
        \begin{enumerate}
            \item Solange Winkel der letzten zwei des Stacks und $p_i$ rechtskurve: Pop()
            \item Push($p_i$)
        \end{enumerate}
        \end{enumerate}
\begin{lstlisting}[language=Java]
int minPoint = 0;
for(int i = 1; i < n; ++i) {
	if(points[i].y < points[minPoint].y ||
		(points[i].y == points[minPoint].y &&
			points[i].x < points[minPoint].x)) {
	minPoint = i;
	}
}
final int mx = points[minPoint].x;
final int my = points[minPoint].y;
Arrays.sort(points, new Comparator<Point>() {
	@Override
	public int compare(Point a, Point b) {
		int ccw = Line2D.relativeCCW(mx, my, a.x, a.y, b.x, b.y);
		if(ccw == 0 || Line2D.relativeCCW(mx, my, b.x, b.y, a.x, a.y) == 0) {
			// gleich...
			double d1 = a.distance(mx, my);
			double d2 = b.distance(mx, my);
			if((d2 < d1 && d2 != 0) || d1 == 0) {
				return 1;
			} else {
				return -1;
			}
		} else if(ccw == 1) {
			// clockwise... -> zuerst b -> a > b
			return 1;
		} else if(ccw == -1) {
			return -1;
		} else {
			System.out.println("shouldnt happen");
			System.exit(1);
		}
		return 0;
	}
});

ArrayList<Integer> stack = new ArrayList<Integer>();
stack.add(n-1);
for(int i = 0; i < n; ++i) {
	if(stack.size() < 2) {
		stack.add(i);
		continue;
	}
	int last = stack.get(stack.size() - 1);
	int l2 = stack.get(stack.size() - 2);
	int ccw = Line2D.relativeCCW(points[l2].x, points[l2].y,
	 points[last].x, points[last].y, points[i].x, points[i].y);
	if(ccw != -1) {
		// clockwise oder gleiche Linie
		stack.remove(stack.size() - 1);
		i--;
	} else {
		stack.add(i);
	}
}
\end{lstlisting}