计算几何02-用叉积比较极角大小并对点集进行排序

一个点 p1 相对于原点 p0 的极角（polar angle）也就是向量 p1-p0 在常规坐标系中的角度。例如，点（3，5）相对于（2，4）的极角即为向量（1，1）的极角，即 45 度或 π/4 弧度。点（3，3）相对于（2，4）的极角即为向量（1，-1）的极角，即 315 度或 7π/4 弧度。请编写一段代码，根据相对于某个给定的原点 p0 的极角，对一个由 n 个点构成的序列（p1,p2,···,pn）进行排序。

/**
 * @author corlymeng.com
 * @date  2015年9月18日
 */
package geometry;

import java.util.Scanner;

public class PolarAngle {
	//点的数量
	private int nums;
	// 存放输入的点集
	private int[][] points;
	/**
	 * 存放点的顺序，sorts[0] = 0，默认的相对点，后面的点1，2，3...都是以 0 为参考点
	 * sorts[1]=4,表示点集中相对于参考点极角最小的是点 4
	 */
	private int[] sorts;
	
	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积。
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	private int direction(int[] pi, int[] pk, int[] pj){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	
	/**
	 * ！核心代码
	 * 采用插入排序的思想对点集进行排序。
	 */
	public void sortPoints() {
		init();
		int i,j;
		int[] tmp;
		for (i = 2; i < nums; i++) {
			tmp = points[i];
			j = i-1;
			while(j>0 && direction(points[0], points[sorts[j]], tmp) < 0){
				sorts[j+1] = sorts[j];
				j--;
			}
			sorts[j+1] = i;
		}
	}
	
	public void init(){
		Scanner in = new Scanner(System.in);
		nums = in.nextInt();
		points = new int[nums][2];
		sorts = new int[nums];
		for (int i = 0; i < nums; i++) {
			sorts[i] = i;
			points[i][0] = in.nextInt();
			points[i][1] = in.nextInt();
		}
	}
	
	public static void main(String[] args) {
		PolarAngle ch = new PolarAngle();
		ch.sortPoints();
	}

}

输入样例：

6
1 1
2 2
1 3
2 3
3 1
3 3

排序后的 sorts 数组：[0, 4, 1, 5, 3, 2]，即序列为 p4,p1,p5,p3,p2 。