최외곽 좌표 찾기 (Convexhull)

최외곽 포인트를 찾는 방법을 이용하면 다양한 분야에 응용될 수 있습니다.
그 방법중 시계반대방향으로 좌표를 찾아 라인의 왼쪽 오른쪽 방향을 판단하여 최외곽 위치를
판단하는 방법을 사용할 수 있습니다.(Graham's scan)
세좌표 가 순서데로 있다고 할때 ((x2-x1)×(y3-y1))-((x3-x1)×(y2-y1)) 의 값이 양수면 왼쪽 음수
면 오른쪽 같으면 직선으로 볼 수 있습니다.
다음의 주소에서 자세한 내용을 확인할 수 있습니다.(http://en.m.wikipedia.org/wiki/Graham_scan)

다음은 실행 해 볼 수 있는 소스입니다.
기본적인 작동 원리만 구현해 보았습니다.(에러를 하나 하나 확인한 소스는 아닙니다.)


function makeRandomPoints(size,maxRadious,startX,startY) {
var pointsArray = [];
for ( var i = 0; i < size; i++ ) {

var pDis = Math.round(Math.random()*maxRadious);
pDis = pDis%maxRadious;
var pAngle = Math.round(Math.random()*360);
pAngle = pAngle%360;
var px = Math.round(Math.cos(pAngle*Math.PI/180.0)*pDis)+startX;
var py = Math.round(-Math.sin(pAngle*Math.PI/180.0)*pDis)+startY;

var ptArray = [];
ptArray.push(px);
ptArray.push(py);
pointsArray.push(ptArray);
}

return pointsArray;
}

function getCounterClockwiseTurn(x1,y1,x2,y2,x3,y3) {
return ( (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1) );
}

function getConvexHullValues(points) {
var fst = -1;
var scd = -1;
var thd = -1;
var size = points.length;

// y값중 최소값 파악
var stdIdx = -1;
var stdX = -1;
var stdY = -1;
for ( var i = 0; i < size; i++ ) {
if ( stdIdx == -1 ) {
stdIdx = i;
stdX = points[i][0];
stdY = points[i][1];
continue;
}
if ( stdY > points[i][1] ) {
stdIdx = i;
stdX = points[i][0];
stdY = points[i][1];
} else if ( stdY == points[i][1] ) {
// 왼쪽 혹은 오른쪽 으로 정렬 ( 동일 선상에 있을 경우 처리를 위함)
// 이 코드에서는 왼쪽 정렬
if ( points[i][0] < stdX ) {
stdIdx = i;
stdX = points[i][0];
stdY = points[i][1];
}
}
}

var sortedArray = [];
// 최소 위치로 부터 시계 반대 방향으로 배열 - 각도를 이용한 소팅
for ( var i = 0; i < size; i++ ) {
var arr = [];
var degree =  (Math.atan2(points[i][1]-stdY,points[i][0]-stdX)*180)/Math.PI;
arr.push(degree);
arr.push(points[i][1]);
arr.push(i);
sortedArray.push(arr);
}

// 정렬 1.각도, 2, Y 값이 작은 수로 선택
// X가 왼쪽 정렬이면 X가 작은 값이 먼저 선택되도록 조치 skip ..
sortedArray.sort( function(a,b) {
var aa = parseFloat(a[0]);
var bb = parseFloat(b[0]);
if ( aa > bb ) {
return 1;
} else if ( aa < bb ) {
return -1;
} else {
var aaa = parseFloat(a[1]);
var bbb = parseFloat(b[1]);
return (aaa<bbb?1:-1);
}
});

// 마지막 항목 다시 계산
sortedArray.push(sortedArray[0]);
//alert ( sortedArray );
var convexPoints = [];
convexPoints.push(sortedArray[0][2]);
for ( var i = 2; i <= size; i++ ) {
fst = convexPoints[convexPoints.length-1];
scd = sortedArray[i-1][2];
thd = sortedArray[i][2];

var dv = getCounterClockwiseTurn(points[fst][0],points[fst][1]
, points[scd][0], points[scd][1], points[thd][0], points[thd][1]);
if ( dv > 0 ) {
convexPoints.push(scd);
} else {
while ( convexPoints.length > 1 ) {
scd = convexPoints.pop();
fst = convexPoints[convexPoints.length-1];
dv = getCounterClockwiseTurn(points[fst][0],points[fst][1]
, points[scd][0], points[scd][1], points[thd][0], points[thd][1]);
if ( dv > 0 ) {
convexPoints.push(scd);
break;
}
}
}
}
return convexPoints;
}

function drawPoint(ownerObj,x,y,w,h,colStr) {
var pObj = document.createElement("DIV");
if ( !colStr ){
colStr = "#FFFFFF";
}
pObj.style.position = "absolute";
pObj.style.margin = "0px";
pObj.style.padding = "0px";
pObj.style.border = "2px solid black";

pObj.style.backgroundColor = colStr;
pObj.style.top = y + "px";
pObj.style.left = x + "px";
pObj.style.width = w+"px";
pObj.style.height = h+"px";
if ( ownerObj ) {
ownerObj.appendChild(pObj);
}
return pObj;
}

window.onload = function() {
var size = 1000;
var maxRadious = 300;
var startX = 350;
var startY = 350;
var points = makeRandomPoints(size,maxRadious,startX,startY);
//alert ( points);
for ( var i = 0; i < size; i++ ) {
drawPoint(document.body,points[i][0], points[i][1],2,2,null);
}

var convexPoints = getConvexHullValues(points);
for ( var i = 0; i < convexPoints.length; i++ ) {
var pt = convexPoints[i];
//alert ( pt );
drawPoint(document.body,points[pt][0], points[pt][1],10,10,"#FF0000");
}
}