I have multiple overlapping squares in Paper.js, and I'd like to separate all the overlapping shapes into their own. You can do exactly this in Illustrator with the pathfinder divide. Before I attempt to just loop through all overlapping shapes and divide them with each other with what might have to be some nested loops I think, I'm wondering if there's a better way.
I want to turn all these squares: https://i.sstatic.net/6Uotg.png
into pieces like this https://i.sstatic.net/jiXV6.png (moved the pieces away from each other so you can see how they're separated)
I ended up going with my own solution which sounded more practical and simple than @arthur's answer. Not sure about which would be more performant though. To summarize, I map what blocks are overlapping with each other with a nested loop and Path.intersects(path), then do another nested loop to divide each block with its overlapping blocks with Path.divide(path) which will cut the original path with whatever path you're dividing it with.
Here's my actual code I'm using in my project with comments.
setupGrid() {
// Setup block row and column positions
for (let i = 0;i < this.total;i++) {
let x
let y
if (!odd(i)) {
x = firstColumnStartX + (this.size/2)
y = firstColumnStartY + ((i/2) * (this.size + this.gap)) + (this.size/2)
} else {
x = secondColumnStartX + (this.size/2)
y = secondColumnStartY + (Math.floor(i/2) * (this.size + this.gap)) + (this.size/2)
}
this.blocks.push(new paper.Path.Rectangle({
position: [x, y],
size: this.size,
strokeColor: '#ff000050'
}))
}
// Setup array to check what blocks are intersecting
const intersects = []
// Setup empty array with a nested array mapped to other blocks [5 x [5 x undefined]]
for (let i = 0;i < this.total;i++) {
intersects[i] = new Array(this.total).fill(undefined)
}
// Intersect checking
for (let i = 0;i < this.total;i++) {
const block = this.blocks[i]
for (let _i = 0;_i < this.total;_i++) {
const otherBlock = this.blocks[_i]
if (block !== otherBlock && intersects[i][_i] === undefined) {
intersects[_i][i] = intersects[i][_i] = block.intersects(otherBlock)
}
}
}
// First loop through all blocks
for (let i = 0;i < this.total;i++) {
let block = this.blocks[i]
// Then loop through other blocks only if they were intersected with the original block
for (let _i = 0;_i < this.total;_i++) {
const otherBlock = this.blocks[_i]
if (intersects[i][_i]) {
/* divide returns {
pieces: array of separated pieces that would be inside the original block's boundaries
leftoverBlock: what's leftover of the other block if the original block was subtracted from it
} */
const divide = this.divide(block, otherBlock)
block.remove()
otherBlock.remove()
// Override current block with the array of pieces
block = this.blocks[i] = divide.pieces
// Override other block with leftover
this.blocks[_i] = divide.leftoverBlock
// Don't let other block divide with original block since we already did it here
intersects[_i][i] = undefined
}
}
}
// Set random color for each piece to check if successful
for (let i = 0;i < this.blocks.length;i++) {
let block = this.blocks[i]
if (block instanceof Array) {
for (let _i = 0;_i < block.length;_i++) {
block[_i].fillColor = new paper.Color(Math.random(), Math.random(), Math.random(), 0.1)
}
} else {
block.fillColor = new paper.Color(Math.random(), Math.random(), Math.random(), 0.1)
}
}
}
// Divide blockA with blockB and expand
divideBlocks(blockA, blockB, pieces = []) {
const divideA = blockA.divide(blockB)
if (divideA instanceof paper.CompoundPath) {
for (let i = divideA.children.length;i--;) {
const child = divideA.children[i]
child.insertAbove(divideA)
pieces.push(child)
}
divideA.remove()
} else {
pieces.push(divideA)
}
return pieces
}
// Divide group (array of paths) with divider
divideGroup(children, divider, pieces = [], parent) {
for (let i = children.length;i--;) {
const child = children[i]
if (parent) {
child.insertAbove(parent)
}
if (child.intersects(divider)) {
this.divideBlocks(child, divider, pieces)
} else {
pieces.push(child)
}
}
}
// Subtract group (array of paths) from block
subtractGroupFromBlock(block, group) {
let oldBlock
let newBlock = block
for (let i = group.length;i--;) {
const child = group[i]
if (child.intersects(block)) {
newBlock = newBlock.subtract(child)
if (oldBlock) {
oldBlock.remove()
}
oldBlock = newBlock
}
}
return newBlock
}
// Check what kind of divide method to use
divide(blockA, blockB) {
const pieces = []
let leftoverBlock
if (blockA instanceof paper.Path) {
this.divideBlocks(blockA, blockB, pieces)
leftoverBlock = blockB.subtract(blockA)
} else if (blockA instanceof Array) {
this.divideGroup(blockA, blockB, pieces)
leftoverBlock = this.subtractGroupFromBlock(blockB, blockA)
}
return {
pieces,
leftoverBlock
}
}
My blocks set with random colors to differentiate each shape:
Overlapping blocks before: https://i.sstatic.net/TRDez.png
Overlapping blocks separated into pieces: https://i.sstatic.net/hrUmf.png
