forked from TamimEhsan/AlgorithmVisualizer
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgrahamScan.js
More file actions
76 lines (70 loc) · 2.06 KB
/
grahamScan.js
File metadata and controls
76 lines (70 loc) · 2.06 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
export function convex_hull(points){
if( points.size === 1 ){
return;
}
const pointStart = points[0];
const pointEnd = points[ points.length-1 ];
const up = [], down = [];
const pairs = [];
const lines=[];
up.push( pointStart);
down.push(pointStart);
for( let i = 1; i< points.length ;i++ ){
if( (i === (points.length - 1)) || cw( pointStart,points[i],pointEnd ) ){
while( up.length >=2 && !cw(up[up.length-2],up[up.length-1],points[i] ) ){
lines.push({
from:up[up.length-2],
to:up[up.length-1],
add:false
});
up.pop();
}
up.push( points[i] );
lines.push({
from:up[up.length-2],
to:up[up.length-1],
add:true
})
}
}
for(let i = 0; i< points.length;i++){
if( (i === (points.length - 1)) || ccw( pointStart,points[i],pointEnd ) ){
while( down.length >=2 && !ccw(down[down.length-2],down[down.length-1],points[i] ) ){
lines.push({
from:down[down.length-2],
to:down[down.length-1],
add:false
});
down.pop();
}
down.push( points[i] );
lines.push({
from:down[down.length-2],
to:down[down.length-1],
add:true
})
}
}
for (let i = 0; i < up.length; i++){
pairs.push(up[i]);
}
for (let i = down.length - 2; i > 0; i--) {
pairs.push(down[i]);
}
return [pairs,lines];
}
function cw(a, b, c) {
const f = a.xx*(b.yy-c.yy)+b.xx*(c.yy-a.yy)+c.xx*(a.yy-b.yy);
if( a.xx*(b.yy-c.yy)+b.xx*(c.yy-a.yy)+c.xx*(a.yy-b.yy) < 0 ){
return true;
} else{
return false;
}
}
function ccw(a, b, c){
if( a.xx * (b.yy - c.yy) + b.xx * (c.yy - a.yy) + c.xx * (a.yy - b.yy) > 0 ){
return true;
} else {
return false;
}
}