【JavaScript】 볼록함 그라함 스캔을 구현, 애니메이션화한다! ? 【canvas】
개요
JavaScript에서 그레이엄 스캔에 의해 정렬되어 가는 애니메이션을 구현했다.
아래쪽에서 데모로 소개.
참고
【JavaScript】 볼록포(그라함스캔)를 가시화·애니메이션【Canvas】
【JavaScript】 볼록포(기프트포장법)를 가시화·애니메이션【Canvas】
환경
JavaScript
Canvas
도서관은 사용하지 않고
데모
일단 데모.
htps : // js 푹 dぇ. 네 t/s_요시키/wn tshy3m/쇼w
실장은, 좀 더 아래쪽으로 소개.
볼록함
볼록함에 대해
볼록함 | Wikipedia
다양한 알고리즘이 있는 것 같지만,
그 중에서도 대표적인 그레이엄 스캔을 구현했다.
처리의 흐름은 다음과 같다.
- 점군 중에서 x, y 모두 가장 작은 점을 찾아 이것을 기준점으로 한다(오름차순으로 정렬했을 때의 index=0).
- 기준점에서 나머지 점군에 대해 편각 순서로 정렬합니다.
- 정렬 된 배열에 그레이엄 스캔 적용
- 결과 그리기
실제로,
※그레이엄 스캔의 점의 비교에 관해서는, 외적을 이용하여 비교하고 있다.
※편각순서의 정렬은 실제로는 기울기를 이용하여 계산하고 있다.
구현
중요한 처리만 발췌하여 소개.
그레이엄 스캔
※편각순으로 정렬된 것으로 가정
//グラハムスキャン
function grahamScan(map){
var path = []
var k = 0
for (var i = 0; i < map.length; ++i) {
while (true) {
if (k < 2) {
break
}
var current = [
map[path[k-1]][0] - map[path[k - 2]][0],
map[path[k-1]][1] - map[path[k - 2]][1]
]
var next = [
map[i][0] - map[path[k - 2]][0],
map[i][1] - map[path[k - 2]][1]
]
if (crossVec(current, next) < 0) {
k--
} else {
break
}
}
path[k++] = i
}
path = path.slice(0, k)
path.push(path[0])
return path
}
//外積
function crossVec(v1,v2){
return v1[0]*v2[1] - v1[1]*v2[0]
}
오름차순 정렬
function sortMat(map ,index) {
if (index === null || index === undefined) {
index = 0
}
return map.sort(function(a,b){
if( a[index] > b[index] ) {
return 1
}
if( a[index] < b[index] ) {
return -1
}
return 0
})
}
편각 순서 정렬
function sortMatByAngle(map ,p) {
function norm(v){
var sum = 0
for (var j = 0; j < v.length; j++) {
sum += v[j]*v[j]
}
sum = Math.sqrt(sum)
for (var i = 0; i < v.length; i++) {
v[i] /= sum
}
return v
}
return map.sort(function(a,b){
var p1 = [
p[0] - a[0],
p[1] - a[1],
]
var p2 = [
p[0] - b[0],
p[1] - b[1],
]
// iOSの場合浮動小数点によるバグが発生する
if(!navigator.userAgent.match(/(iPhone|iPad|iPod|Android)/)){
p1 = norm(p1)
p2 = norm(p2)
}
if (p1[0] === 0 || p2[0] === 0) {
return 1
}
if( p1[1]/p1[0] > p2[1]/p2[0] ) {
return 1
} else {
return -1
}
return 0
})
}
참고
【JavaScript】 볼록포(그라함스캔)를 가시화·애니메이션【Canvas】
【JavaScript】 볼록포(기프트포장법)를 가시화·애니메이션【Canvas】
Reference
이 문제에 관하여(【JavaScript】 볼록함 그라함 스캔을 구현, 애니메이션화한다! ? 【canvas】), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/s-yoshiki/items/3c6fcaa2ffa4bb79936e텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
