Чтобы развернуть выпуклый многоугольник, нарисуйте линию, параллельную каждому ребру и на расстоянии заданного количества единиц.Затем используйте точки пересечения новых линий в качестве вершин расширенного многоугольника.Javascript / canvas в конце следует за этой функциональной разбивкой:
Шаг 1: выяснить, какая сторона "вне"
Порядок вершин (точек) имеет значение,В выпуклом многоугольнике они могут быть перечислены в порядке по часовой стрелке (CW) или против часовой стрелки (CCW).В многоугольнике CW поверните одно из ребер на 90 градусов CCW , чтобы получить нормаль, обращенную наружу.На многоугольнике против часовой стрелки поверните его CW .
Если направление поворота вершин заранее неизвестно, проверьте, как поворачивается второй край.от первой.В выпуклом многоугольнике остальные ребра будут продолжать вращаться в том же направлении:
Найти нормальную CW первого ребра .Мы пока не знаем, обращены ли они внутрь или наружу.
Вычислим точечное произведение второго ребра с вычисленной нами нормалью.Если второе ребро повернет CW, скалярное произведение будет положительным.В противном случае оно будет отрицательным.
Математика:
// in vector terms:
v01 = p1 - p0 // first edge, as a vector
v12 = p2 - p1 // second edge, as a vector
n01 = (v01.y, -v01.x) // CW normal of first edge
d = v12 * n01 // dot product
// and in x,y terms:
v01 = (p1.x-p0.x, p1.y-p0.y) // first edge, as a vector
v12 = (p2.x-p1.x, p2.y-p1.y) // second edge, as a vector
n01 = (v01.y, -v01.x) // CW normal of first edge
d = v12.x * n01.x + v12.y * n01.y; // dot product: v12 * n01
if (d > 0) {
// the polygon is CW
} else {
// the polygon is CCW
}
// and what if d==0 ?
// -- that means the second edge continues in the same
// direction as a first. keep looking for an edge that
// actually turns either CW or CCW.
Код:
function vecDot(v1, v2) {
return v1.x * v2.x + v1.y * v2.y;
}
function vecRot90CW(v) {
return { x: v.y, y: -v.x };
}
function vecRot90CCW(v) {
return { x: -v.y, y: v.x };
}
function polyIsCw(p) {
return vecDot(
vecRot90CW({ x: p[1].x - p[0].x, y: p[1].y - p[0].y }),
{ x: p[2].x - p[1].x, y: p[2].y - p[1].y }) >= 0;
}
var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW;
Шаг 2: Найти линии, параллельные ребрам многоугольника
Теперь, когда мы знаем, какая сторона вышла, мы можем вычислить линии, параллельные каждому ребру многоугольника, на точно требуемом расстоянии.Вот наша стратегия:
Для каждого ребра вычислите его нормаль, обращенную наружу
Нормализуйте нормаль так, чтобыего длина становится одной единицей
Умножьте нормаль на расстояние, которое мы хотим, чтобы расширенный многоугольник был от оригинала
Добавьте умноженную нормаль коба конца края.Это даст нам две точки на параллельной линии.Этих двух точек достаточно для определения параллельной линии.
Код:
// given two vertices pt0 and pt1, a desired distance, and a function rot()
// that turns a vector 90 degrees outward:
function vecUnit(v) {
var len = Math.sqrt(v.x * v.x + v.y * v.y);
return { x: v.x / len, y: v.y / len };
}
function vecMul(v, s) {
return { x: v.x * s, y: v.y * s };
}
var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y }; // edge vector
var d01 = vecMul(vecUnit(rot(v01)), distance); // multiplied unit normal
var ptx0 = { x: pt0.x + d01.x, y: pt0.y + d01.y }; // two points on the
var ptx1 = { x: pt1.x + d01.x, y: pt1.y + d01.y }; // parallel line
Шаг 3: вычислениепересечения параллельных линий
- это будут вершины расширенного многоугольника.
Math:
Линия, проходящая через две точки P1 , P2 , может быть описана как:
P = P1 + t * (P2 - P1)
Две линии могут быть описаны как
P = P1 + t * (P2 - P1)
P = P3 + u * (P4 - P3)
И их пересечение должно быть на обеих линиях:
P = P1 + t * (P2 - P1) = P3 + u * (P4 - P3)
Это можно поменять, чтобы оно выглядело так:
(P2 - P1) * t + (P3 - P4) * u = P3 - P1
Что в терминах x, y равно:
(P2.x - P1.x) * t + (P3.x - P4.x) * u = P3.x - P1.x
(P2.y - P1.y) * t + (P3.y - P4.y) * u = P3.y - P1.y
Поскольку точки P1, P2, P3 и P4 известны, также известны следующие значения:
a1 = P2.x - P1.x a2 = P2.y - P1.y
b1 = P3.x - P4.x b2 = P3.y - P4.y
c1 = P3.x - P1.x c2 = P3.y - P1.y
Это сокращает наши уравнения до:
a1*t + b1*u = c1
a2*t + b2*u = c2
Решение для t получает нас:
t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2)
Что позволяет нам найти пересечение в P = P1 + t * (P2 - P1).
Код:
function intersect(line1, line2) {
var a1 = line1[1].x - line1[0].x;
var b1 = line2[0].x - line2[1].x;
var c1 = line2[0].x - line1[0].x;
var a2 = line1[1].y - line1[0].y;
var b2 = line2[0].y - line2[1].y;
var c2 = line2[0].y - line1[0].y;
var t = (b1*c2 - b2*c1) / (a2*b1 - a1*b2);
return {
x: line1[0].x + t * (line1[1].x - line1[0].x),
y: line1[0].y + t * (line1[1].y - line1[0].y)
};
}
Шаг 4: Работа с особыми случаями
Существует ряд особых случаев, которыезаслуживают внимания.Оставленное читателю в качестве упражнения ...
Когда между двумя ребрами очень острый угол, расширенная вершина может быть очень далека от исходной.Возможно, вы захотите обрезать расширенный край, если он выходит за пределы некоторого порога.В крайнем случае угол равен нулю, что говорит о том, что расширенная вершина находится на бесконечности, вызывая деление на ноль в арифметике.Осторожно.
Когда первые два ребра находятся на одной линии, вы не можете определить, является ли это многоугольником CW или CCW, просто взглянув на них.Посмотрите на другие ребра.
Невыпуклые многоугольники гораздо интереснее ... и здесь не рассматриваются.
Полная выборкакод
Перетащите это в браузер с поддержкой Canvas.Я использовал Chrome 6 на Windows.Треугольник и его расширенная версия должны анимировать.
<html>
<head>
<style type="text/css">
canvas { border: 1px solid #ccc; }
</style>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
<script type="text/javascript">
$(function() {
var canvas = document.getElementById('canvas');
if (canvas.getContext) {
var context = canvas.getContext('2d');
// math for expanding a polygon
function vecUnit(v) {
var len = Math.sqrt(v.x * v.x + v.y * v.y);
return { x: v.x / len, y: v.y / len };
}
function vecMul(v, s) {
return { x: v.x * s, y: v.y * s };
}
function vecDot(v1, v2) {
return v1.x * v2.x + v1.y * v2.y;
}
function vecRot90CW(v) {
return { x: v.y, y: -v.x };
}
function vecRot90CCW(v) {
return { x: -v.y, y: v.x };
}
function intersect(line1, line2) {
var a1 = line1[1].x - line1[0].x;
var b1 = line2[0].x - line2[1].x;
var c1 = line2[0].x - line1[0].x;
var a2 = line1[1].y - line1[0].y;
var b2 = line2[0].y - line2[1].y;
var c2 = line2[0].y - line1[0].y;
var t = (b1*c2 - b2*c1) / (a2*b1 - a1*b2);
return {
x: line1[0].x + t * (line1[1].x - line1[0].x),
y: line1[0].y + t * (line1[1].y - line1[0].y)
};
}
function polyIsCw(p) {
return vecDot(
vecRot90CW({ x: p[1].x - p[0].x, y: p[1].y - p[0].y }),
{ x: p[2].x - p[1].x, y: p[2].y - p[1].y }) >= 0;
}
function expandPoly(p, distance) {
var expanded = [];
var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW;
for (var i = 0; i < p.length; ++i) {
// get this point (pt1), the point before it
// (pt0) and the point that follows it (pt2)
var pt0 = p[(i > 0) ? i - 1 : p.length - 1];
var pt1 = p[i];
var pt2 = p[(i < p.length - 1) ? i + 1 : 0];
// find the line vectors of the lines going
// into the current point
var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y };
var v12 = { x: pt2.x - pt1.x, y: pt2.y - pt1.y };
// find the normals of the two lines, multiplied
// to the distance that polygon should inflate
var d01 = vecMul(vecUnit(rot(v01)), distance);
var d12 = vecMul(vecUnit(rot(v12)), distance);
// use the normals to find two points on the
// lines parallel to the polygon lines
var ptx0 = { x: pt0.x + d01.x, y: pt0.y + d01.y };
var ptx10 = { x: pt1.x + d01.x, y: pt1.y + d01.y };
var ptx12 = { x: pt1.x + d12.x, y: pt1.y + d12.y };
var ptx2 = { x: pt2.x + d12.x, y: pt2.y + d12.y };
// find the intersection of the two lines, and
// add it to the expanded polygon
expanded.push(intersect([ptx0, ptx10], [ptx12, ptx2]));
}
return expanded;
}
// drawing and animating a sample polygon on a canvas
function drawPoly(p) {
context.beginPath();
context.moveTo(p[0].x, p[0].y);
for (var i = 0; i < p.length; ++i) {
context.lineTo(p[i].x, p[i].y);
}
context.closePath();
context.fill();
context.stroke();
}
function drawPolyWithMargin(p, margin) {
context.fillStyle = "rgb(255,255,255)";
context.strokeStyle = "rgb(200,150,150)";
drawPoly(expandPoly(p, margin));
context.fillStyle = "rgb(150,100,100)";
context.strokeStyle = "rgb(200,150,150)";
drawPoly(p);
}
var p = [{ x: 100, y: 100 }, { x: 200, y: 120 }, { x: 80, y: 200 }];
setInterval(function() {
for (var i in p) {
var pt = p[i];
if (pt.vx === undefined) {
pt.vx = 5 * (Math.random() - 0.5);
pt.vy = 5 * (Math.random() - 0.5);
}
pt.x += pt.vx;
pt.y += pt.vy;
if (pt.x < 0 || pt.x > 400) { pt.vx = -pt.vx; }
if (pt.y < 0 || pt.y > 400) { pt.vy = -pt.vy; }
}
context.clearRect(0, 0, 800, 400);
drawPolyWithMargin(p, 10);
}, 50);
}
});
</script>
</head>
<body>
<canvas id="canvas" width="400" height="400"></canvas>
</body>
</html>
пример кода отказа от ответственности:
образец жертвует некоторой эффективностью ради ясности. В вашем коде вы можете вычислить развернутую параллель каждого ребра только один раз, а не дважды, как здесь
координата y холста растет вниз, что инвертирует логику CW / CCW. Вещи продолжают работать, хотя нам просто нужно повернуть внешние нормали в направлении, противоположном многоугольнику - и оба перевернуты.