반응형
Minkowski Sum 입니다.
https://en.wikipedia.org/wiki/Minkowski_addition
2D Polygon A, B 가 존재할 때 각 Polygon 의 영역을 합한 새로운 영역을 얻습니다.
외각 Vertex 를 얻을 수 있으며 ( 0, 0 ) 을 기준으로 합하므로, 기준 좌표를 옮겨 A, B 도형 위로 옮길 수 있습니다.
<!DOCTYPE html>
<html>
<body>
<canvas id="myCanvas" width="500" height="500" style="border:1px solid #000000;">
Your browser does not support the HTML canvas tag.
</canvas>
<script>
// https://cp-algorithms.com/geometry/minkowski.html
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
// prepare for pivot to center
var width = c.width;
var height = c.height;
var half_width = c.width / 2;
var half_height = c.height / 2;
function draw_pivot_line() {
ctx.save();
ctx.beginPath();
ctx.moveTo(0, half_height);
ctx.lineTo(width, half_height);
ctx.moveTo(half_width, 0);
ctx.lineTo(half_width, height);
ctx.stroke();
ctx.restore();
}
draw_pivot_line();
var scale = 10;
function draw(from, color) {
var arr = from.slice(); // deep-copy
arr.push(arr[0]); // cyclic
ctx.save();
ctx.beginPath();
for (i = 0; i < arr.length - 1; i++) {
var [x, y] = arr[i];
var [x2, y2] = arr[i + 1];
ctx.moveTo(x * scale + half_width, half_height - y * scale);
ctx.lineTo(x2 * scale + half_width, half_height - y2 * scale);
ctx.strokeStyle = color;
ctx.stroke();
}
ctx.restore();
}
//#region vector utils
function add(a, b) {
return [a[0] + b[0], a[1] + b[1]];
}
function sub(a, b) {
return [a[0] - b[0], a[1] - b[1]];
}
function cross(a, b) {
return a[0] * b[1] - a[1] * b[0];
}
//#endregion vector utils
// find center pos from min, max
function center(poly) {
var [maxX, maxY] = poly[0];
var [minX, minY] = poly[0];
for (var i = 0; i < poly.length; i++) {
var [x, y] = poly[i]
if (x > maxX) maxX = x;
if (y > maxY) maxY = y;
if (x < minX) minX = x;
if (y < minY) minY = y;
}
return [(maxX + minX) / 2, (maxY + minY) / 2];
}
function minkowski(fromA, fromB, pivotToA, pivotToB) {
var a = fromA.slice(); // deep-copy
var b = fromB.slice(); // deep-copy
function reorder_polygon(arr) {
var p = 0;
for (var i = 1; i < arr.length; i++) {
var [x, y] = arr[i];
var [x2, y2] = arr[p];
if (y < y2 || (y == y2 && x < x2)) {
p = i;
}
}
// rotate to left
while (p-- > 0) {
arr.push(arr.shift());
}
return arr;
}
// the first vertex must be the lowest
a = reorder_polygon(a);
b = reorder_polygon(b);
// we must ensure cyclic indexing
a.push(a[0]);
a.push(a[1]);
b.push(b[0]);
b.push(b[1]);
var r = [];
var i = 0; j = 0;
while (i < a.length - 2 || j < b.length - 2) {
r.push(add(a[i], b[j]));
var c = cross(sub(a[i + 1], a[i]), sub(b[j + 1], b[j]));
if (c >= 0 && i < a.length - 2) {
++i;
}
if (c <= 0 && j < b.length - 2) {
++j;
}
}
// option 1.
if (pivotToA) {
var ac = center(a);
for (var k = 0; k < r.length; k++) {
r[k] = sub(r[k], ac);
}
}
// option 2.
else if (pivotToB) {
var bc = center(b);
for (var k = 0; k < r.length; k++) {
r[k] = sub(r[k], bc);
}
}
return r;
}
// test case 1.
{
var a = [[3, 8], [3, 6], [6, 6], [6, 8]];
draw(a, 'black');
var b = [[9, 9], [11, 9], [11, 11], [9, 11]];
draw(b, 'black');
var s = minkowski(a, b);
draw(s, 'red');
var s_a = minkowski(a, b, true);
draw(s_a, 'green');
var s_b = minkowski(a, b, false, true);
draw(s_b, 'blue');
}
// test case 2.
{
var a = [[-4, 2], [-3, 1], [-2, 2]];
draw(a, 'black');
var b = [[2, 3], [2, 1], [4, 1], [4, 3]];
draw(b, 'black');
var s = minkowski(a, b);
draw(s, 'red');
var s_a = minkowski(a, b, true);
draw(s_a, 'green');
var s_b = minkowski(a, b, false, true);
draw(s_b, 'blue');
}
</script>
</body>
</html>반응형
'알고리즘' 카테고리의 다른 글
| Alias method Algorithm (0) | 2023.04.27 |
|---|---|
| boids (0) | 2023.04.23 |
| 피보나치 힙 (0) | 2015.12.15 |
| 문자열 매칭 알고리즘 (0) | 2015.12.05 |
| A* Algorithm (0) | 2015.11.25 |