update: Everything works except getMatrixDirection, see the end of the question.
I take arbitrary lines (any angle) and create shapes around them, some of which are reflected across those lines. The shapes can be triangular or quadrilateral, including non-parallelograms. My code to calculate the reflected points works, and I draw these points onto a canvas, clip, and stroke. Then I need to render the texture flipped and rotated to correspond to these points. I create a transform with DOMMatrix, using rotate and scale to create a reflection (flip) about the line and translating so the image aligns with the outline, which doesn't work.
Because the drawing orientation of the canvas sometimes (but not always) switches, I tried translating to the maxX/Y, but this runs into problems with non-axis-aligned shapes. The maxX, maxY float outside the shape. Using minX/Y for the top left also fails, which you can see looking at the second of my test cases in the example. This could mean the original bounding box isn't correct either.
I also tried using closest points on the new shape, with better results. But this still failed noticeably on shapes where the slope of the bottom edge was positive, since the bottom right point would have a smaller minY than the bottom left (so then the image wouldn't be drawn low enough).
I don't think I can just perform math on the height/width of the image, because the shapes are recursively folded, so they might only represent fractions of the canvas. I need the images to sit within the exact bounds dictated by calculating the reflected points (which are hardcoded in my example, sorry).
I made a more minimal version of my code to show here. It just has a few predefined test lines/shapes and it doesn't cover all scenarios unfortunately. The original code is way too big to post. The part of the canvas that reads '1' should draw from the origin.
"use strict";
const canvasWidth = 600;
const canvasHeight = 830;
const pieces = [
[{
points: [new DOMPoint(140, 50), new DOMPoint(140.00000000000003, -90), new DOMPoint(90.00000000000001, -90), new DOMPoint(90, 0), ],
line: {
start: new DOMPoint(283.6663192636163, 193.66631926361632),
end: new DOMPoint(-52.666319263616316, -142.66631926361632)
},
original: [new DOMPoint(140, 50), new DOMPoint(0, 50), new DOMPoint(0, 0), new DOMPoint(90, 0), ],
intersects: [new DOMPoint(90, 0), new DOMPoint(140, 50), ],
origTopLeft: new DOMPoint(0, 0),
width: 50.00000000000003,
height: 50.00000000000003
}, {
points: [new DOMPoint(158.36517719568567, 44.67326250912334), new DOMPoint(163.97896049896048, -53.783451143451146), new DOMPoint(213.82095634095634, -49.58802494802492), new DOMPoint(211.1386748844376, -2.5451301597599514), ],
line: {
start: new DOMPoint(252.24682141160773, -39.3261033682806),
end: new DOMPoint(101.75317858839227, 95.3261033682806)
},
original: [new DOMPoint(158.36517719568567, 44.67326250912335), new DOMPoint(256.8378378378378, 50), new DOMPoint(258.18918918918916, -1.6317320576126618e-15), new DOMPoint(211.1386748844376, -2.5451301597599563), ],
intersects: [new DOMPoint(211.1386748844376, -2.5451301597599514), new DOMPoint(158.36517719568567, 44.67326250912334), ],
origTopLeft: new DOMPoint(158.36517719568567, -2.5451301597599563),
width: 55.45577914527067,
height: 55.45577914527067
}, {
points: [new DOMPoint(198.38255973344914, 8.868236027966603), new DOMPoint(-153.64897521683866, 5.578032470538176), new DOMPoint(-154.11627140114496, 55.57584876561373), new DOMPoint(143.07549812764987, 58.3535016752606), ],
line: {
start: new DOMPoint(436.3443301443184, -204.04492697123226),
end: new DOMPoint(-82.3443301443184, 260.04492697123226)
},
original: [new DOMPoint(198.3825597334491, 8.868236027966553), new DOMPoint(162.65825355141538, 359.09787638799855), new DOMPoint(112.9163540869709, 354.0240772523315), new DOMPoint(143.0754981276499, 58.353501675260645), ],
intersects: [new DOMPoint(143.07549812764987, 58.3535016752606), new DOMPoint(198.38255973344914, 8.868236027966603), ],
origTopLeft: new DOMPoint(112.9163540869709, 8.868236027966553),
width: 352.49883113459407,
height: 352.49883113459407
}, ],
[{
points: [new DOMPoint(183, 0), new DOMPoint(-115.80000000000018, -398.4000000000001), new DOMPoint(-155.80000000000018, -368.4000000000001), new DOMPoint(158, 50), ],
line: {
start: new DOMPoint(466.81944546997806, -567.6388909399561),
end: new DOMPoint(-126.81944546997806, 619.6388909399561)
},
original: [new DOMPoint(183.00000000000003, 0), new DOMPoint(681, 0), new DOMPoint(681, 50), new DOMPoint(158, 50), ],
intersects: [new DOMPoint(158, 50), new DOMPoint(183, 0), ],
originalTopLeft: new DOMPoint(158, 0),
width: 338.8000000000002,
height: 338.8000000000002
}, ],
[{
points: [new DOMPoint(157.50666666666666, 24.98461538461538), new DOMPoint(232.01174895512395, 458.84515237596656), new DOMPoint(182.7330781575854, 467.307575458501), new DOMPoint(121.1733333333333, 108.830769230769), ],
line: {
start: new DOMPoint(358.8607804360353, -439.6787240831585),
end: new DOMPoint(-43.86078043603533, 489.6787240831585)
},
original: [new DOMPoint(157.50666666666666, 24.9846153846154), new DOMPoint(-210.00917431192647, 267.30275229357795), new DOMPoint(-182.48623853211006, 309.045871559633), new DOMPoint(121.17333333333352, 108.83076923076914), ],
intersects: [new DOMPoint(121.1733333333333, 108.830769230769), new DOMPoint(157.50666666666666, 24.98461538461538), ],
originalTopLeft: new DOMPoint(-210.00917431192647, 24.9846153846154),
width: 110.83841562179065,
height: 110.83841562179065
}, {
points: [new DOMPoint(118.49999999999997, 49.99999999999999), new DOMPoint(207.78082191780817, 127.91780821917807), new DOMPoint(240.6575342465753, 90.24657534246575), new DOMPoint(137.25, -4.9897642155143516e-15), ],
line: {
start: new DOMPoint(199.2848941516392, -165.42638440437122),
end: new DOMPoint(55.71510584836079, 217.42638440437122)
},
original: [new DOMPoint(118.5, 50), new DOMPoint(0, 50), new DOMPoint(0, 0), new DOMPoint(137.25, 0), ],
intersects: [new DOMPoint(137.25, -4.9897642155143516e-15), new DOMPoint(118.49999999999997, 49.99999999999999), ],
originalTopLeft: new DOMPoint(0, 0),
width: 122.15753424657532,
height: 122.15753424657532
}]
];
// reflect, rotate by angle of the longest edge of the pre-reflected shape so that the image renders at the right angle on the page
function getReflectionMatrix(piece, ctx) {
const {
line,
original,
points,
intersects
} = piece;
const anchor = intersects[0]; // point where the line and the other edges meet, used as an origin for reflection
const display = new DOMMatrix();
reflectMatrix(display, line, anchor);
rotateMatrix(display, original, anchor); // i do this so the image shows up at the right angle on the canvas
translateMatrix(display, original, points, ctx);
return display;
}
function reflectMatrix(matrix, line, anchor) {
const radians = getAngleFromOrigin(line);
const angle = getDegreesFromRadians(radians);
matrix.translateSelf(anchor.x, anchor.y);
matrix.rotateSelf(angle);
matrix.scaleSelf(1, -1);
matrix.rotateSelf(-angle);
}
function rotateMatrix(matrix, originalPoints, anchor) {
const longestEdgeAngle = getLongestEdgeAngle(originalPoints);
const degrees = getDegreesFromRadians(longestEdgeAngle);
matrix.rotateSelf(degrees);
matrix.translateSelf(-anchor.x, -anchor.y);
}
function translateMatrix(matrix, originalPoints, newPoints, ctx) {
const pt0T = new DOMPoint(0, 0).matrixTransform(matrix);
const { pointsUp, pointsLeft } = getMatrixDirection(matrix);
const corners = getRotatedBoundingBox(newPoints);
let d = "topLeft";
if (pointsUp && pointsLeft) d = "bottomRight";
if (pointsUp && !pointsLeft) d = "bottomLeft";
if (pointsLeft && !pointsUp) d = "topRight";
const target = corners[d];
const dx = target.x - pt0T.x;
const dy = target.y - pt0T.y;
const translated = new DOMMatrix().translateSelf(dx, dy);
matrix.preMultiplySelf(translated);
const debug = corners.topLeft, debug1 = corners.topRight, debug2 = corners.bottomLeft, debug3 = corners.bottomRight;
drawDebugMarker(debug.x, debug.y, "blue", ctx);
drawDebugMarker(debug1.x, debug1.y, "red", ctx);
drawDebugMarker(debug2.x, debug2.y, "green", ctx);
drawDebugMarker(debug3.x, debug3.y, "orange", ctx);
drawDebugMarker(target.x, target.y, "purple", ctx);
}
// rotated bounding box helpers
function getRotatedBoundingBox(points) {
const { angle, corners, width, height } = getBestBox(points);
const cos = Math.cos(-angle);
const sin = Math.sin(-angle);
const unrotated = corners.map(point => rotatePoint(point, sin, cos));
return sortCorners(unrotated);
}
function sortCorners(points) {
const sorted = points.toSorted((a, b) => a.y == b.y ? a.x - b.x : a.y - b.y);
const [pt1, pt2, pt3, pt4] = sorted;
const [topLeft, topRight] = pt1.x < pt2.x ? [pt1, pt2] : [pt2, pt1];
const [bottomLeft, bottomRight] = pt3.x < pt4.x ? [pt3, pt4] : [pt4, pt3];
return { topLeft, topRight, bottomRight, bottomLeft };
}
function getBestBox(points) {
let bestArea = Infinity;
let bestBox;
for (let i = 0; i < points.length; i++) {
const a = points[i];
const b = points[(i + 1) % points.length];
const angle = -Math.atan2(b.y - a.y, b.x - a.x);
const cos = Math.cos(angle);
const sin = Math.sin(angle);
const rotated = points.map(point => rotatePoint(point, sin, cos));
const { minX, maxX, minY, maxY } = getBoundingBox(rotated);
const { width, height } = getDimensions(rotated);
const area = width * height;
if (area < bestArea) {
bestArea = area;
bestBox = makeBoundingBox(minX, maxX, minY, maxY, width, height, angle);
}
}
return bestBox;
}
function rotatePoint(point, sin, cos) {
const { x, y } = point;
return new DOMPoint(rotateX(x, y, sin, cos), rotateY(x, y, sin, cos));
}
function rotateX(x, y, sin, cos) {
return x * cos - y * sin;
}
function rotateY(x, y, sin, cos) {
return x * sin + y * cos;
}
function makeBoundingBox(minX, maxX, minY, maxY, width, height, angle) {
return {
corners: [
new DOMPoint(minX, minY), // tl
new DOMPoint(maxX, minY), // tr
new DOMPoint(maxX, maxY), // br
new DOMPoint(minX, maxY), // bl
],
angle, width, height
};
}
// helpers for getting shape dimensions etc.
function getAngleFromOrigin(line) {
const {
start,
end
} = line;
const dx = end.x - start.x;
const dy = end.y - start.y;
return Math.atan2(dy, dx);
}
function getLongestEdgeAngle(points) {
let maxLength = 0;
let bestAngle = 0;
for (let i = 0; i < points.length; i++) {
const a = points[i];
const b = points[(i + 1) % points.length];
const dx = b.x - a.x;
const dy = b.y - a.y;
const length = Math.hypot(dx, dy);
if (length > maxLength) {
maxLength = length;
bestAngle = Math.atan2(dy, dx);
}
}
return bestAngle;
}
function getDegreesFromRadians(angle) {
const degrees = angle * 180 / Math.PI;
return ((degrees % 360) + 360) % 360;
}
function getTopLeft(points) {
const {
minX,
maxX,
minY,
maxY
} = getBoundingBox(points);
return new DOMPoint(minX, minY);
}
function getBoundingBox(points) {
const coordsX = points.map(point => point.x);
const minX = Math.min(...coordsX);
const maxX = Math.max(...coordsX);
const coordsY = points.map(point => point.y);
const minY = Math.min(...coordsY);
const maxY = Math.max(...coordsY);
return {
minX,
maxX,
minY,
maxY
};
}
function getDimensions(points) {
const {
minX,
maxX,
minY,
maxY
} = getBoundingBox(points);
const width = maxX - minX;
const height = maxY - minY;
return {
width,
height
};
}
function getMatrixDirection(matrix) {
const rightX = matrix.a;
const rightY = matrix.b;
const downX = matrix.c;
const downY = matrix.d;
const pointsLeft = Math.abs(rightX) >= Math.abs(rightY) ? rightX < 0 : rightY < 0;
const pointsUp = Math.abs(downY) >= Math.abs(downX) ? downY < 0 : downX < 0;
return {
pointsLeft,
pointsUp
};
}
function findClosestPoint(points, x, y) {
let minDist = Infinity;
let closest = points[0];
for (const point of points) {
const dist = Math.hypot(point.x - x, point.y - y);
if (dist < minDist) {
minDist = dist;
closest = point;
}
}
return closest;
}
// drawing
function loopThroughPieces(test, ctx) {
for (let i = 0; i < test.length; i++) {
ctx.setTransform(canvasTransform);
const piece = test[i];
const colour = getColour(i);
const display = getReflectionMatrix(piece, ctx);
drawPiece(piece, colour, display, ctx);
}
}
function getColour(i) {
// red comes first
const hue = (i * 45) % 360;
const lightness = 100 - (40 + 10);
const alpha = 0.5;
return `hsla(${hue}, 90%, ${lightness}%, ${alpha})`;
}
function drawPiece(piece, colour, display, ctx) {
ctx.save();
tracePiecePath(piece.points, ctx);
ctx.globalAlpha = 0.65;
//ctx.clip(); // it's supposed to be clipped, but i unclipped for visualisation, since sometimes the image floats outside of the outline
ctx.setTransform(canvasTransform.multiply(display));
ctx.drawImage(image, 0, 0, image.width, image.height);
ctx.strokeStyle = colour;
ctx.lineWidth = 3;
ctx.globalAlpha = 1;
ctx.stroke();
ctx.restore();
ctx.save();
}
function tracePiecePath(points, ctx) {
ctx.beginPath();
const firstPoint = points[0];
ctx.moveTo(firstPoint.x, firstPoint.y);
points.slice(1).forEach(point => {
ctx.lineTo(point.x, point.y);
});
ctx.closePath();
}
function drawDebugMarker(x, y, colour, ctx) {
ctx.beginPath();
ctx.arc(x, y, 5, 0, 2 * Math.PI);
ctx.fillStyle = colour;
ctx.fill();
}
// everything below is just assembling test cases etc. and rendering them
function makeCanvasTransform() {
canvasTransform.scaleSelf(0.6, 0.6);
canvasTransform.translateSelf(canvasWidth / 2, canvasHeight / 2);
}
function drawDebugImage() {
const imgCtx = image.getContext("2d");
imgCtx.fillStyle = "white";
imgCtx.fillRect(0, 0, image.width, image.height);
imgCtx.font = "20px arial";
imgCtx.textAlign = "center";
imgCtx.fillStyle = "black";
const segmentWidth = image.width / 12;
let offsetX = 0;
for (let i = 0; i < Math.ceil(image.width / segmentWidth); i++) {
imgCtx.strokeRect(offsetX, 0, segmentWidth, image.height);
imgCtx.fillText(i + 1, offsetX + segmentWidth / 2, image.height / 2);
offsetX += segmentWidth;
}
}
function gatherCtxs() {
const ctxs = [];
for (let i = 0; i < pieces.length; i++) {
const canvas = document.createElement("canvas");
canvas.width = canvasWidth;
canvas.height = canvasHeight;
canvases.appendChild(canvas);
if (i % 2 == 1) {
const br = document.createElement("br");
canvases.appendChild(br);
}
ctxs.push(canvas.getContext("2d"));
}
return ctxs;
}
const image = document.getElementById("image");
const canvases = document.getElementById("canvases");
const canvasTransform = new DOMMatrix();
drawDebugImage();
makeCanvasTransform();
const ctxs = gatherCtxs();
for (let i = 0; i < pieces.length; i++) {
loopThroughPieces(pieces[i], ctxs[i]);
}canvas {
border: 1px solid grey;
margin: 2px;
}<p><canvas id="image" width="680" height="50"></canvas></p>
<p id="canvases"></p>Thank you for reading! :)
edit: Okay, so I tried to implement something called rotating calipers to get the tightest width and height possible and I'm getting the correct values, except width and height are along the wrong axes for some of them due to the rotation.
So, because of that I'm adjusting for the angle (I don't know if it's too naïvely), then adding width and height where necessary to get the other corners. That seems to solve one problem (fingers crossed), but leaves the problem of picking the correct origin.
I drew the caliper corners on the canvas and the point I want (as far as I can tell) is within them for all the test cases, so I need a logical way to select the right corner, because rotation changes the relationship between x/y magnitude on the canvas and order in the list of corners.
Updated snippet (I think)
edit2: I mostly solved the problem, not posting it as an answer yet because there's still a big piece of the puzzle missing.
I sorted the corners based on their coordinates in the normal (unrotated) bounding box, then snapped to the appropriate one based on pointsUp/pointsLeft. I'm not sure if there's a better way to do it, but it works, and it snaps properly to the sides of the outline.
The problem is pointsUp/pointsLeft is wrong for one of the tests (the last test, the orange piece), so that the image is drawn up from the top right instead of up from the bottom right. This means getMatrixDirection is wrong, but I don't know what to do instead. The function is intended to extract the left/right and up/down orientation that an image will draw from the origin on the canvas.
I'm pretty sure I have it fully solved now! I am posting my answer here as a summary in case anyone needs it in the future. It seems kind of unlikely, but you never know.
I iterate over the angles of each edge of the polygon and (rotating each point by the negative of the edge's atan2) create a bounding box from the polygon points, then take the tightest one found by doing so.
Then I re-rotate the corners by the positive of the edge's atan2 to put the box back into reflected spaces, giving me the final coordinates of the tightest bounding box. If you draw the points onto the polygon at this point, the ideal origin is always one of the corners of the bbox.
function getRotatedBoundingBox(points) {
const { angle, corners } = getBestBox(points);
const cos = Math.cos(-angle);
const sin = Math.sin(-angle);
return corners.map(point => rotatePoint(point, sin, cos));
function getBestBox(points) {
let bestArea = Infinity;
let bestBox;
for (let i = 0; i < points.length; i++) {
const a = points[i];
const b = points[(i + 1) % points.length];
const angle = -Math.atan2(b.y - a.y, b.x - a.x);
const cos = Math.cos(angle);
const sin = Math.sin(angle);
const rotated = points.map(point => rotatePoint(point, sin, cos));
const { width, height } = getDimensions(rotated);
const area = width * height;
if (area < bestArea) {
bestArea = area;
bestBox = makeBoundingBox(rotated, angle);
}
}
return bestBox;
}
function rotatePoint(point, sin, cos) {
const { x, y } = point;
return new DOMPoint(rotateX(x, y, sin, cos), rotateY(x, y, sin, cos));
}
function rotateX(x, y, sin, cos) {
return x * cos - y * sin;
}
function rotateY(x, y, sin, cos) {
return x * sin + y * cos;
}
function makeBoundingBox(points, angle) {
const { minX, maxX, minY, maxY } = getBoundingBox(points);
return {
corners: [
new DOMPoint(minX, minY),
new DOMPoint(maxX, minY),
new DOMPoint(maxX, maxY),
new DOMPoint(minX, maxY),
],
angle
};
}
The next problem was working out which spot on the box to snap to. I project the extent of the image (image.width/height) as a DOMPoint and transform it with the existing matrix, then create a unit vector. I then compare the dot products of the unit and each corner's distance from the origin to see which is the opposite corner directionally.
function translateMatrix(matrix, newPoints, ctx) {
const pt0T = new DOMPoint(0, 0).matrixTransform(matrix);
const corners = getRotatedBoundingBox(newPoints);
const dir = new DOMPoint(image.width, image.height).matrixTransform(matrix);
dir.x -= pt0T.x, dir.y -= pt0T.y;
const norm = { x: dir.x / Math.hypot(dir.x, dir.y), y: dir.y / Math.hypot(dir.x, dir.y) };
const target = corners.reduce((best, pt) => {
const dot = (pt.x - pt0T.x) * norm.x + (pt.y - pt0T.y) * norm.y;
return dot < best.dot ? { pt, dot } : best;
}, { pt: null, dot: Infinity }).pt;
const dx = target.x - pt0T.x;
const dy = target.y - pt0T.y;
const translated = new DOMMatrix().translateSelf(dx, dy);
matrix.preMultiplySelf(translated);
}
If this somehow doesn't work in future testing, I will come back and edit this, but as far as I can tell, it is working well.
edit: I solved getMatrixDirection, see Inferring the drawing direction of a rotation+reflection matrix applied to a canvas However, I ended up not needing it.
edit2: Sorting corners by y>x worked, but it still assigned the wrong corners, so I adopted a different approach.