当前位置：首页 > news >正文

js使用run编码计算region的交集并集差集

news 来源：原创 2024/9/20 7:48:48

所有shape都转为run编码

转为run编码后再运算可以节约大量内存

subtractIntervals 函数的逻辑：目前的实现假设了所有的 subIntervals 都会与 intervals 完全重叠，这可能导致计算不准确。应该将 subIntervals 从 intervals 中去除时，考虑到可能的部分重叠。

差集计算：subtractIntervals 函数需要更准确地处理部分重叠和完整重叠的情况。

效果图

result

关键代码

/*** 绘制矩形* @param {CanvasRenderingContext2D} ctx - Canvas 2D 渲染上下文* @param {number[]} rect - 矩形 [x, y, width, height]* @param {string} color - 颜色*/function drawRect(ctx, rect, color) {ctx.fillStyle = color;ctx.fillRect(rect[0], rect[1], rect[2], rect[3]);}/*** 绘制 RLE 区域* @param {CanvasRenderingContext2D} ctx - Canvas 2D 渲染上下文* @param {Object[]} rle - RLE 区域数组* @param {string} color - 颜色*/function drawRLE(ctx, rle, color) {ctx.fillStyle = color;rle.forEach(({ row, intervals }) => {intervals.forEach(({ startCol, runLength }) => {ctx.fillRect(startCol, row, runLength, 1);});});}/*** 将矩形转换为 RLE 编码* @param {number[]} rect - 矩形 [x, y, width, height]* @returns {Object[]} - RLE 区域数组*/function rectangleToRLE(rect) {const [x, y, w, h] = rect;const rle = [];for (let i = y; i < y + h; i++) {rle.push({row: i,intervals: [{ startCol: x, runLength: w }]});}return rle;}/*** 计算两个 RLE 区域的交集* @param {Object[]} rle1 - 第一个 RLE 区域数组* @param {Object[]} rle2 - 第二个 RLE 区域数组* @returns {Object[]} - 交集 RLE 区域数组*/function intersectRLE(rle1, rle2) {const intersected = [];const rleMap = (rle) => {const map = new Map();rle.forEach(({ row, intervals }) => {if (!map.has(row)) {map.set(row, []);}map.get(row).push(...intervals);});return map;};const rleMap1 = rleMap(rle1);const rleMap2 = rleMap(rle2);const allRows = new Set([...rleMap1.keys(), ...rleMap2.keys()]);allRows.forEach(row => {const intervals1 = rleMap1.get(row) || [];const intervals2 = rleMap2.get(row) || [];const rowIntersected = intersectIntervals(intervals1, intervals2);if (rowIntersected.length > 0) {intersected.push({ row, intervals: rowIntersected });}});return intersected;}/*** 计算两个区间数组的交集* @param {Object[]} intervals1 - 第一个区间数组* @param {Object[]} intervals2 - 第二个区间数组* @returns {Object[]} - 交集区间数组*/function intersectIntervals(intervals1, intervals2) {const result = [];intervals1.forEach(({ startCol: start1, runLength: length1 }) => {intervals2.forEach(({ startCol: start2, runLength: length2 }) => {const start = Math.max(start1, start2);const end = Math.min(start1 + length1, start2 + length2);if (start < end) {result.push({ startCol: start, runLength: end - start });}});});return result;}/*** 计算两个 RLE 区域的并集* @param {Object[]} rle1 - 第一个 RLE 区域数组* @param {Object[]} rle2 - 第二个 RLE 区域数组* @returns {Object[]} - 并集 RLE 区域数组*/function unionRLE(rle1, rle2) {const union = [];const rleMap = (rle) => {const map = new Map();rle.forEach(({ row, intervals }) => {if (!map.has(row)) {map.set(row, []);}map.get(row).push(...intervals);});return map;};const rleMap1 = rleMap(rle1);const rleMap2 = rleMap(rle2);const allRows = new Set([...rleMap1.keys(), ...rleMap2.keys()]);allRows.forEach(row => {const intervals1 = rleMap1.get(row) || [];const intervals2 = rleMap2.get(row) || [];const rowUnion = unionIntervals(intervals1, intervals2);if (rowUnion.length > 0) {union.push({ row, intervals: rowUnion });}});return union;}/*** 计算两个区间数组的并集* @param {Object[]} intervals1 - 第一个区间数组* @param {Object[]} intervals2 - 第二个区间数组* @returns {Object[]} - 并集区间数组*/function unionIntervals(intervals1, intervals2) {const result = [];const allIntervals = [...intervals1, ...intervals2];allIntervals.sort((a, b) => a.startCol - b.startCol);let currentStart = -Infinity;let currentEnd = -Infinity;allIntervals.forEach(({ startCol, runLength }) => {const end = startCol + runLength;if (startCol > currentEnd) {if (currentEnd > currentStart) {result.push({ startCol: currentStart, runLength: currentEnd - currentStart });}currentStart = startCol;currentEnd = end;} else {currentEnd = Math.max(currentEnd, end);}});if (currentEnd > currentStart) {result.push({ startCol: currentStart, runLength: currentEnd - currentStart });}return result;}/*** 计算一个 RLE 区域相对于另一个区域的差集* @param {Object[]} rle1 - 第一个 RLE 区域数组* @param {Object[]} rle2 - 第二个 RLE 区域数组* @returns {Object[]} - 差集 RLE 区域数组*/function subtractRLE(rle1, rle2) {const difference = [];const rleMap = (rle) => {const map = new Map();rle.forEach(({ row, intervals }) => {if (!map.has(row)) {map.set(row, []);}map.get(row).push(...intervals);});return map;};const rleMap1 = rleMap(rle1);const rleMap2 = rleMap(rle2);const allRows = new Set([...rleMap1.keys(), ...rleMap2.keys()]);allRows.forEach(row => {const intervals1 = rleMap1.get(row) || [];const intervals2 = rleMap2.get(row) || [];const rowDifference = subtractIntervals(intervals1, intervals2);if (rowDifference.length > 0) {difference.push({ row, intervals: rowDifference });}});return difference;}/*** 计算两个区间数组的差集* @param {Object[]} intervals - 原始区间数组* @param {Object[]} subIntervals - 子区间数组* @returns {Object[]} - 差集区间数组*/function subtractIntervals(intervals, subIntervals) {const result = [];intervals.forEach(({ startCol, runLength }) => {let currentStart = startCol;let currentLength = runLength;subIntervals.forEach(({ startCol: subStart, runLength: subLength }) => {if (subStart >= currentStart + currentLength || subStart + subLength <= currentStart) {return;}const overlapStart = Math.max(currentStart, subStart);const overlapEnd = Math.min(currentStart + currentLength, subStart + subLength);if (overlapStart > currentStart) {result.push({ startCol: currentStart, runLength: overlapStart - currentStart });}if (overlapEnd < currentStart + currentLength) {result.push({ startCol: overlapEnd, runLength: (currentStart + currentLength) - overlapEnd });}let currentStartBack=currentStart;currentStart = Math.max(currentStart, overlapEnd);currentLength = (currentStartBack + currentLength) - currentStart;});if (currentLength > 0) {result.push({ startCol: currentStart, runLength: currentLength });}});return result;}/*** 绘制 RLE 运算结果* @param {CanvasRenderingContext2D} ctxIntersect - 交集 Canvas 渲染上下文* @param {CanvasRenderingContext2D} ctxUnion - 并集 Canvas 渲染上下文* @param {CanvasRenderingContext2D} ctxDifference - 差集 Canvas 渲染上下文* @param {number[]} rect1 - 第一个矩形 [x, y, width, height]* @param {number[]} rect2 - 第二个矩形 [x, y, width, height]*/function drawResults(ctxIntersect, ctxUnion, ctxDifference, rect1, rect2) {const rle1 = rectangleToRLE(rect1);const rle2 = rectangleToRLE(rect2);const intersectedRLE = intersectRLE(rle1, rle2);const unionRLE1 = unionRLE(rle1, rle2);const differenceRLE = subtractRLE(rle1, rle2);// 清空 CanvasctxIntersect.clearRect(0, 0, ctxIntersect.canvas.width, ctxIntersect.canvas.height);ctxUnion.clearRect(0, 0, ctxUnion.canvas.width, ctxUnion.canvas.height);ctxDifference.clearRect(0, 0, ctxDifference.canvas.width, ctxDifference.canvas.height);// 绘制交集结果drawRLE(ctxIntersect, intersectedRLE, 'rgba(255, 255, 0, 0.5)'); // Yellow for intersection// 绘制并集结果drawRLE(ctxUnion, unionRLE1, 'rgba(0, 255, 0, 0.5)'); // Green for union// 绘制差集结果drawRLE(ctxDifference, differenceRLE, 'rgba(255, 0, 0, 0.5)'); // Red for difference}const canvasIntersect = document.getElementById('canvasIntersect');const canvasUnion = document.getElementById('canvasUnion');const canvasDifference = document.getElementById('canvasDifference');const ctxIntersect = canvasIntersect.getContext('2d');const ctxUnion = canvasUnion.getContext('2d');const ctxDifference = canvasDifference.getContext('2d');const rect1 = [0, 0, 200, 200]; // x, y, width, heightconst rect2 = [50, 50, 150, 150]; // x, y, width, heightdrawResults(ctxIntersect, ctxUnion, ctxDifference, rect1, rect2);