Я имею выпуклый многоугольник P1 точек N. Этот многоугольник может быть любой формы или пропорции (пока он еще выпуклый).
Мне нужно вычислить другой полигон P2 с использованием геометрии исходных многоугольников, но "расширен" на заданное количество единиц. Каким может быть алгоритм для расширения выпуклого многоугольника?
Чтобы развернуть выпуклый многоугольник, нарисуйте линию, параллельную каждому ребру и на заданном количестве единиц. Затем используйте точки пересечения новых линий в качестве вершин расширенного многоугольника. Javascript/canvas в конце следует за этой функциональной разбивкой:
Шаг 1: выяснить, какая сторона "вне"
Порядок вершин (точек) имеет значение. В выпуклом многоугольнике они могут быть перечислены в порядке по часовой стрелке (CW) или против часовой стрелки (CCW). В многоугольнике по часовой стрелке поверните одно из ребер на 90 градусов против часовой стрелки, чтобы получить нормаль, обращенную наружу. На полигоне против часовой стрелки поверните его вместо часовой стрелки.
Если направление поворота вершин заранее неизвестно, проверьте, как второе ребро поворачивается от первого. В выпуклом многоугольнике остальные ребра будут продолжать вращаться в одном направлении:
Найти нормальную 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: Вычислить пересечения параллельных линий
--these будет вершинами расширенного многоугольника.
Математика:
Линия, проходящая через две точки 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 = (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. Треугольник и его расширенная версия должны анимироваться.
canvas { border: 1px solid #ccc; }$(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);
}
});<html>
<head>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
</head>
<body>
<canvas id="canvas" width="400" height="400"></canvas>
</body>
</html>Если многоугольник центрирован в начале координат, просто умножьте каждую из точек на общий масштабный коэффициент.
Если многоугольник не центрирован в начале координат, тогда сначала переводите так, чтобы центр находился в начале, масштабе, а затем переводил его обратно туда, где он был.
После вашего комментария
Кажется, вы хотите, чтобы все точки были перемещены на такое же расстояние от начала координат. Вы можете сделать это для каждой точки, получив нормализованный вектор до этой точки. умножая это на "расширение константы" и добавив возвращаемый вектор обратно в исходную точку.
n.b. Вам все равно придется переводить-изменять-переводить, если центр не является также источником этого решения.
Для каждого сегмента линии оригинала найдите среднюю точку m и (единицу длины) наружу нормальную u сегмента. Соответствующий сегмент расширенного многоугольника будет тогда лежать на линии через m + n * u (где вы хотите развернуть оригинал по n) с нормальным u. Чтобы найти вершины расширенного многоугольника, вам нужно найти пересечение пар последовательных линий.
Пусть точки многоугольника равны A1, B1, C1... Теперь у вас есть линии от A1 до B1, затем от B1 до C1... Мы хотим вычислить точки A2, B2, C2 многоугольника P2.
Если вы разделите угол, например A1 B1 C1, у вас будет линия, которая идет в нужном направлении. Теперь вы можете найти точку B2 на ней, которая является подходящим расстоянием от B1 на линии биссектрисы. Повторите это для всех точек многоугольника P1.
Посмотрите на прямые скелеты. Как было подразумевается здесь, существует ряд сложных проблем с невыпуклыми многоугольниками, которые вы были беззаветно спасены!