c++algorithm graph-algorithm convex-polygon

Multiple convex shape corner connection

I have an immutable array structure holding convex shapes as in the image above (they may vary in size and count, however they are always convex and never overlapping). What I want to do is connect the corners between them that can be connected without overlaping any edge, as in the image bellow where the blue lines represent the connections.

The data I have available are data structures holding the corner positions in the convex shapes, represented as a Vector structure similar to the following:

class Vector2
{
public:
   float x, y;
}

The convex shape structure looks something like this:

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

What I want to return from the function is an std::vector of a structure similar to the following:

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

So each linked vector is supposed to have a pointer to each other linked vector it is connected to.

The final function will thereby have this format:

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;
}

All of these links I then want to save for use in a later function which connects two points to the already linked shapes, along the lines of this:

The function should not alter the already existing connections and should look something like this:

// 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;
}

Could someone help me with how this could be done?

Solution

This is a description for an algorithm with example implementation to get you going.

Step 1

Preprocess every edge of the two shapes (s0 and s1) and extract the following information:

Distances from every edge in one shape to the vertices in the other
An ordered set of the vertices in one shape facing towards the other

Finding the distances is an exhaustive task (O(|V(s0)| * |V(s1)|)), it is also very cheap (line-point distance) and embarrassingly parallelisable. The facing vertices are found using the distances from above:

Start with the first vertex on the first shape, where the other shape is completely outside of its two adjacent edges (i.e. for any adjacent edge there exist outside values in its distances).

Since the facing set is a unique sequential set of vertices for convex polygons, continue adding vertices...

...until you reach a vertex where all vertices from the other shape lie inside of its adjacent edges

Doing this for both sides results in two sequences of facing vertices in each shape (the green dots per shape):

Step 2

To connect the two facing sets a scanline approach can be used:

In the ordered set of facing vertices the first vertex from one shape is always in line of sight of the last vertex from the other shape (first and last in case the shapes are oriented the same). From there we'll search sequentially, using the angle criteria from above for both the query from the first and the candidate vertex from the other shape, in the facing set to initialise our loop.

Looping sequentially over the facing vertices of the first shape, remove vertices that have broken line of sight (red line) and add vertices that came within line of sight (green line).

Step 3

Connecting the two outside points with the shapes is equivalent to finding the facing set of one shape in step 1 but instead of to another shape now there are only those individual outside points.

I've implemented step 1 and 2 in the following little browser demo as a prove of concept:

Click on the canvas and drag to move the camera
Click inside a shape and drag to move the shape

(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>