多个凸形角连接

Question

我有一个不变的数组结构，保持凸形状，如上图所示（它们的大小和数量可能不同，但它们总是凸起的，永远不会重叠）。我想要做的是连接它们之间的角落，这些角落可以连接而不会覆盖任何边缘，如下图中蓝线代表连接的图像。

我可用的数据是保持凸起形状的角位置的数据结构，表示为类似于以下的Vector结构：

class Vector2
{
public:
   float x, y;
}

凸形结构看起来像这样：

class ConvexShape
{
public:
   std::vector<Vector2> edges;
}

我想从函数返回的是一个类似于以下结构的std :: vector：

class LinkedVector2 : public Vector2
{
public:
   std::vector<LinkedVector2*> links;
}

因此，每个链接的向量应该具有指向它所连接的每个其他链接向量的指针。

因此，最终函数将具有以下格式：

std::vector<LinkedVector>* generateLinks(const std::vector<ConvexShape>& shapes)
{
   std::vector<LinkedVector> links{ new std::vector<LinkedVector>{} };

   // Create a linked vector for each shape's corner.

   // Calculate links.

   return links;
}

我想要保存所有这些链接，以便在稍后的函数中使用，该函数将两个点连接到已经链接的形状，沿着这样的行：

该函数不应该改变已经存在的连接，应该看起来像这样：

// Argument 'links' will contain the previously generated links.
std::vector<LinkedVector>* connectPoints(const Vector2& a, const Vector2& b, const std::vector<LinkedVector>& links)
{
   std::vector<LinkedVector>* connections{ new std::vector<LinkedVector>{} };

   // Add old links to 'connections'.

   // Connect the new links to the old.

   // Add the new links to 'connections'.

   return connections;
}

有人可以帮我解决这个问题吗？

Answer 1

这是一个带有示例实现的算法的描述，以帮助您前进。

步骤1

预处理两个形状的每个边缘（s0和s1）并提取以下信息：

1. 从一个形状中的每个边到另一个形状中的顶点的距离
2. 一个有序的一组顶点，面向另一个

寻找距离是一项详尽的任务（O(|V(s0)| * |V(s1)|)），它也非常便宜（线点距离）并且令人尴尬地可并行化。使用上面的facing找到distances顶点：

• 从第一个形状上的第一个顶点开始，其中另一个形状完全位于其两个相邻边缘之外（即，对于任何相邻边缘，在其distances中存在外部值）。

• 由于facing集是凸多边形的唯一连续顶点集，因此继续添加顶点...

• ...直到到达顶点，其中来自另一个形状的所有顶点都位于其相邻边的内部

• 对两侧执行此操作会导致每个形状中的两个facing顶点序列（每个形状的绿点）：

第2步

要连接两个facing集，可以使用扫描线方法：

1. 在有序的facing顶点集中，来自一个形状的第一个顶点总是在与另一个形状的最后一个顶点的视线中（如果形状的方向相同，则为第一个和最后一个）。从那里我们将使用上面的角度标准顺序搜索来自第一个的查询和来自另一个形状的候选顶点，在facing集合中初始化我们的循环。

2. 在第一个形状的facing顶点上顺序循环，删除具有虚线（红线）的顶点并添加视线内的顶点（绿线）。

第3步

将两个外部点与形状连接相当于在步骤1中找到一个形状的facing集，但现在只有那些单独的外部点而不是另一个形状。

---

我在下面的小浏览器演示中实现了第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>