Styjun

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.

Example in Illustrator

I want to turn all these squares:
https://i.imgur.com/PPRi9M9.png

into pieces like this
https://i.imgur.com/xTFS8jP.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.imgur.com/j9ZSUC5.png

Overlapping blocks separated into pieces:
https://i.imgur.com/mc83IH6.png

Since you want to create shapes which did not exist before (according to your example, you want the operation to create the inner rectangle), I think you will have to loop over all overlapping shapes, compute intersections with Path.getIntersections(path[, include]), and re-create new paths from existing ones.

Once you computed all intersections, you will have to loop through all vertices, always rotating in the same direction, and create the new paths.

Take one (random) vertex, find the connected vertex "with the smallest angle" (it should work with currentVertex.getDirectedAngle(connectedVertex)) ; set the current vertex as visited and continue until you find the first vertex again. Create a shape, and redo this algorithm until you visited all vertices.

You could also use Path.intersect(path[, options]) but I don't think it would help you.