Это описание алгоритма с примером реализации, которое поможет вам.
Шаг 1
Предварительная обработка каждого ребра двух фигур (s0 и s1) и извлечениеследующая информация:
- Расстояния от каждого ребра в одной форме до вершин в другой
- Упорядоченный набор вершин в одной форме, обращенных к другой
Поиск расстояний является исчерпывающей задачей (O(|V(s0)| * |V(s1)|)), он также очень дешев (расстояние от линии до точки) и смущающе параллелизуем.Вершины facing находятся с использованием distances сверху:
- Начните с первой вершины первой фигуры, где другая фигура полностью находится вне ее двухсмежные ребра (т. е. для любого смежного ребра существуют внешние значения в его
distances).
- Поскольку набор
facing является уникальным последовательным набором вершин для выпуклых многоугольников, продолжайте добавлять вершины ...
- ... пока вы не достигнете вершины, в которой все вершины другой формы лежат внутри смежных с ней ребер
- Выполнение этого для обеих сторон приводит к двум последовательностям
facing вершин в каждой форме (зеленые точки на фигуру):
Шаг 2
Чтобы соединить два набора facing, можно использовать подход сканирования:
- В упорядоченном наборе
facing вершин первый вершина из одной фигуры всегда находится на линии прямой видимости последняя вершина из другой фигуры ( первая и последняя , если фигуры ориентированы одинаково).Оттуда мы будем искать последовательно, используя критерии угла сверху как для запроса из первой, так и для вершины-кандидата из другой фигуры, в facing, установленном для инициализации нашего цикла.
Последовательное зацикливание по
facing вершинам первой фигуры, удаление вершин, которые имеют ломаную линию обзора (красная линия), и добавление вершин, попавших в зону прямой видимости (зеленая линия).*
Шаг 3
Соединение двух внешних точек с фигурами эквивалентно нахождению набора facing одной фигуры на шаге 1, но вместов другой форме теперь есть только эти отдельные внешние точки.
Я реализовал шаги 1 и 2 в следующей небольшой демонстрации браузера в качестве подтверждения концепции:
- Нажмите на холст и перетащите, чтобы переместить камеру
- Нажмите внутри фигуры и перетащите, чтобы переместить фигуру
(function(canvas) {
function v2(x, y) { return { x: x, y: y }; }
function v2mul(lhs, rhs) { lhs.x *= rhs.x; lhs.y *= rhs.y; }
function v2subed(lhs, rhs) { return v2(lhs.x - rhs.x, lhs.y - rhs.y); }
function v2dot(lhs, rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; }
function v2normalized(v) { var len = Math.sqrt(v2dot(v, v)); if(len < 1e-7) len = 1; return v2(v.x / len, v.y / len); }
function v2perped(v) { return v2(-v.y, v.x); }
// Line from origin o : v2 and direction d : v2
function Line(o, d) {
this.o = o;
this.d = d;
}
// Signed distance to a point v : v2, in units of direction this.d
Line.prototype.distance = function(v) {
var o = v2subed(v, this.o);
var d = v2perped(this.d);
return v2dot(o, d);
};
// A polygon is made up of a sequence of points (arguments[i] : v2)
function Polygon() {
this.positions = [].slice.call(arguments);
}
// Transform polygon to new base [bx, by] and translation t
Polygon.prototype.transform = function(bx, by, t) {
this.positions.forEach(function(v) {
var x = bx.x * v.x + by.x * v.y + t.x;
var y = bx.y * v.x + by.y * v.y + t.y;
v.x = x;
v.y = y;
});
};
// Naive point inside polygon test for polygon picking
Polygon.prototype.isInside = function(v) {
if(this.positions.length < 3)
return false;
var o0 = this.positions[this.positions.length - 1];
for(var i = 0, imax = this.positions.length; i < imax; ++i) {
var o1 = this.positions[i];
var line = new Line(o0, v2normalized(v2subed(o1, o0)));
if(line.distance(v) <= 0)
return false;
o0 = o1;
}
return true;
};
// A camera positioned at eye : v2
function Camera(eye) {
this.eye = eye;
}
// Prepare temporaries for screen conversions
Camera.prototype.prepare = function(w, h) {
this.screen = {
off: v2(w / 2, h / 2),
};
};
Camera.prototype.toScreenX = function(x) { return x + this.screen.off.x - this.eye.x; }
Camera.prototype.toScreenY = function(y) { return this.screen.off.y - y + this.eye.y; }
Camera.prototype.fromScreenX = function(x) { return x - this.screen.off.x + this.eye.x; }
Camera.prototype.fromScreenY = function(y) { return this.screen.off.y - y + this.eye.y; }
Camera.prototype.toScreen = function(v) { return v2(this.toScreenX(v.x), this.toScreenY(v.y)); };
Camera.prototype.fromScreen = function(v) { return v2(this.fromScreenX(v.x), this.fromScreenY(v.y)); }
// Compute the distances of the line through e0 in p0 to each vertex in p1
// @post e0.distances.length === p1.positions.length
function computeEdge(e0, p0, p1) {
var line = new Line(p0.positions[e0.start], v2normalized(v2subed(p0.positions[e0.end], p0.positions[e0.start])));
var distances = [];
p1.positions.forEach(function(v) { distances.push(line.distance(v)); });
e0.line = line;
e0.distances = distances;
return e0;
}
// Find vertices in a convex polygon p0 that face p1
// @pre edges.length === p0.positions.length
function computeFacing(edges, p0, p1) {
var facing = [];
var count0 = p0.positions.length;
var count1 = p1.positions.length;
function isFacingVertex(i0) {
var e0 = edges[(i0 + count0 - 1) % count0];
var e1 = edges[i0];
for(var i1 = 0; i1 < count1; ++i1)
if(e0.distances[i1] < 0 || e1.distances[i1] < 0)
return true;
return false;
}
// Find the first vertex in the facing set of two non-intersecting, convex polygons
for(var i0 = 0; i0 < count0; ++i0) {
// For the first chance facing vertex
if(isFacingVertex(i0)) {
if(i0 === 0) {
// Search backwards here, s.t. we can complete the loop in one sitting
var iStart = count0;
for(; iStart > 1 && isFacingVertex(iStart - 1); --iStart);
while(iStart < count0)
facing.push(iStart++);
}
facing.push(i0++);
// In a convex polygon the (single) set of facing vertices is sequential
while(i0 < count0 && isFacingVertex(i0))
facing.push(i0++);
break;
}
}
return facing;
}
// Preprocesses the convex polygon p0 building the edges and facing lists
function preprocessPolygon(p0, p1) {
var result = {
edges: [],
facing: null,
};
for(var i = 0, imax = p0.positions.length; i < imax; ++i)
result.edges.push(computeEdge({ start: i, end: (i + 1) % imax }, p0, p1));
result.facing = computeFacing(result.edges, p0, p1);
return result;
}
// Scanline-approach to find all line of sight connections between the facing vertices of two preprocessed convex polygons p0 : Polygon and p1 : Polygon
// Output is prep.connections where prep.connections[i] : { v0, v1 } describes an unobstructed line of sight edge between vertex index v0 in p0 and v1 in p1
function computeConnections(prep, p0, p1) {
var connections = [];
var facing1count = prep.p1.facing.length;
// For oriented polygons the first facing vertex in p0 must surely face the last facing vertex in p1
var facing1begin = facing1count - 1, facing1end = facing1count;
prep.p0.facing.forEach(function(v0) {
function isConnectingVertex(v1) {
// Is v1 outside of adjacent edge-lines from v0?
var count0 = prep.p0.edges.length;
var ep = prep.p0.edges[(v0 + count0 - 1) % count0];
var en = prep.p0.edges[v0];
if(!(ep.distances[v1] < 0 || en.distances[v1] < 0)) return false;
// Is v0 outside of adjacent edge-lines from v1?
var count1 = prep.p1.edges.length;
ep = prep.p1.edges[(v1 + count1 - 1) % count1];
en = prep.p1.edges[v1];
return ep.distances[v0] < 0 || en.distances[v0] < 0;
}
// Throw away vertices that are no longer facing the current vertex
for(; facing1end > 0 && !isConnectingVertex(prep.p1.facing[facing1end - 1]); --facing1end);
// Add newly facing vertices
for(; facing1begin > 0 && isConnectingVertex(prep.p1.facing[facing1begin - 1]); --facing1begin);
// Generate the connections in facing range
for(var facing1 = facing1begin; facing1 < facing1end; ++facing1)
connections.push({ v0: v0, v1: prep.p1.facing[facing1] });
});
prep.connections = connections;
}
function process(prep, p0, p1) {
delete prep.p0;
delete prep.p1;
delete prep.connections;
prep.p0 = preprocessPolygon(p0, p1);
prep.p1 = preprocessPolygon(p1, p0);
computeConnections(prep, p0, p1);
}
var polygons = null;
var prep = null;
var camera = null;
var ui = null;
function reset() {
polygons = [
new Polygon(v2(25, -75), v2(50, -175), v2(140, -225), v2(255, -200), v2(195, -65), v2(140, -40)),
new Polygon(v2(400, -100), v2(295, -70), v2(260, -80), v2(310, -220), v2(425, -230)),
];
// Scale to a fitting size and move to center
var bx = v2(0.5, 0), by = v2(0, 0.5), off = v2(-120, 70);
polygons[0].transform(bx, by, off);
polygons[1].transform(bx, by, off);
prep = {};
camera = new Camera(v2(0, 0));
ui = { pickedPolygon: -1 };
update();
draw();
}
function update() {
// Reprocess polygons
process(prep, polygons[0], polygons[1]);
}
function draw() {
var g = canvas.getContext("2d");
var w = canvas.width;
var h = canvas.height;
camera.prepare(w, h);
g.fillStyle = "linen";
g.fillRect(0, 0, w, h);
var iPick = 0;
polygons.forEach(function(polygon) {
var highlight = iPick++ === ui.pickedPolygon;
var positions = polygon.positions;
if(positions.length > 2) {
g.beginPath();
g.lineWidth = highlight ? 2 : 1;
g.strokeStyle = "black";
var pLast = camera.toScreen(positions[positions.length - 1]);
g.moveTo(pLast.x, pLast.y);
positions.forEach(function(pos) {
var pScreen = camera.toScreen(pos);
g.lineTo(pScreen.x, pScreen.y);
});
g.stroke();
}
});
prep.connections.forEach(function(connection) {
var v0 = camera.toScreen(polygons[0].positions[connection.v0]);
var v1 = camera.toScreen(polygons[1].positions[connection.v1]);
g.beginPath();
g.lineWidth = 2;
g.strokeStyle = "cyan";
g.moveTo(v0.x, v0.y);
g.lineTo(v1.x, v1.y);
g.stroke();
});
}
(function(c) {
reset();
var dragStartPos = null, dragLastPos = null;
var pickedPolygon = null;
var cameraStartPos = v2(0, 0);
function toScreen(client) {
var rect = c.getBoundingClientRect();
return v2(client.x - rect.left, client.y - rect.top);
}
function startDragging(x, y) {
dragStartPos = v2(x, y);
dragLastPos = v2(x, y);
if(pickedPolygon !== null) {
// Nothing to prepare
} else {
cameraStartPos.x = camera.eye.x;
cameraStartPos.y = camera.eye.y;
}
}
function continueDragging(x, y) {
if(pickedPolygon !== null) {
var dx = x - dragLastPos.x, dy = -(y - dragLastPos.y);
pickedPolygon.transform(v2(1, 0), v2(0, 1), v2(dx, dy));
update();
} else {
var dx = -(x - dragStartPos.x), dy = y - dragStartPos.y;
camera.eye.x = cameraStartPos.x + dx;
camera.eye.y = cameraStartPos.y + dy;
}
dragLastPos.x = x;
dragLastPos.y = y;
}
function stopDragging() {
dragStartPos = null;
dragLastPos = null;
if(pickedPolygon !== null) {
// Nothing to do here...
} else {
cameraStartPos.x = 0;
cameraStartPos.y = 0;
}
}
c.onmousemove = function(e) {
if(dragStartPos !== null)
continueDragging(e.clientX, e.clientY);
else {
pickedPolygon = null;
var iPick = 0;
var cursorPos = camera.fromScreen(toScreen(v2(e.clientX, e.clientY)));
for(var imax = polygons.length; iPick < imax; ++iPick) {
if(polygons[iPick].isInside(cursorPos)) {
pickedPolygon = polygons[iPick];
break;
}
}
ui.pickedPolygon = pickedPolygon !== null ? iPick : -1;
}
draw();
};
c.onmouseleave = function(e) {
if(dragStartPos !== null)
stopDragging();
pickedPolygon = null;
ui.pickedPolygon = -1;
draw();
};
c.onmousedown = function(e) {
if(e.button === 0)
startDragging(e.clientX, e.clientY);
draw();
};
c.onmouseup = function(e) {
if(e.button === 0 && dragStartPos !== null)
stopDragging();
draw();
};
})(canvas);
})(document.getElementById("screen"));
<canvas id="screen" width="300" height="300"></canvas>