# modeling/src/geometries/geom2/toOutlines.js

``````const vec2 = require('../../maths/vec2')

const toSides = require('./toSides')

/*
* Create a list of edges which SHARE vertices.
* This allows the edges to be traversed in order.
*/
const toSharedVertices = (sides) => {
const unique = new Map() // {key: vertex}
const getUniqueVertex = (vertex) => {
const key = vertex.toString()
if (unique.has(key)) {
return unique.get(key)
} else {
unique.set(key, vertex)
return vertex
}
}

return sides.map((side) => side.map(getUniqueVertex))
}

/*
* Convert a list of sides into a map from vertex to edges.
*/
const toVertexMap = (sides) => {
const vertexMap = new Map()
// first map to edges with shared vertices
const edges = toSharedVertices(sides)
edges.forEach((edge) => {
if (vertexMap.has(edge[0])) {
vertexMap.get(edge[0]).push(edge)
} else {
vertexMap.set(edge[0], [edge])
}
})
return vertexMap
}

/**
* Create the outline(s) of the given geometry.
* @param {geom2} geometry - geometry to create outlines from
* @returns {Array} an array of outlines, where each outline is an array of ordered points
* @alias module:modeling/geometries/geom2.toOutlines
*
* @example
* let geometry = subtract(rectangle({size: [5, 5]}), rectangle({size: [3, 3]}))
* let outlines = toOutlines(geometry) // returns two outlines
*/
const toOutlines = (geometry) => {
const vertexMap = toVertexMap(toSides(geometry)) // {vertex: [edges]}
const outlines = []
while (true) {
let startSide
for (const [vertex, edges] of vertexMap) {
startSide = edges.shift()
if (!startSide) {
vertexMap.delete(vertex)
continue
}
break
}
if (startSide === undefined) break // all starting sides have been visited

const connectedVertexPoints = []
const startVertex = startSide[0]
while (true) {
connectedVertexPoints.push(startSide[0])
const nextVertex = startSide[1]
if (nextVertex === startVertex) break // the outline has been closed
const nextPossibleSides = vertexMap.get(nextVertex)
if (!nextPossibleSides) {
throw new Error(`geometry is not closed at vertex \${nextVertex}`)
}
const nextSide = popNextSide(startSide, nextPossibleSides)
if (nextPossibleSides.length === 0) {
vertexMap.delete(nextVertex)
}
startSide = nextSide
} // inner loop

// due to the logic of fromPoints()
// move the first point to the last
if (connectedVertexPoints.length > 0) {
connectedVertexPoints.push(connectedVertexPoints.shift())
}
outlines.push(connectedVertexPoints)
} // outer loop
vertexMap.clear()
return outlines
}

// find the first counter-clockwise edge from startSide and pop from nextSides
const popNextSide = (startSide, nextSides) => {
if (nextSides.length === 1) {
return nextSides.pop()
}
const v0 = vec2.create()
const startAngle = vec2.angleDegrees(vec2.subtract(v0, startSide[1], startSide[0]))
let bestAngle
let bestIndex
nextSides.forEach((nextSide, index) => {
const nextAngle = vec2.angleDegrees(vec2.subtract(v0, nextSide[1], nextSide[0]))
let angle = nextAngle - startAngle
if (angle < -180) angle += 360
if (angle >= 180) angle -= 360
if (bestIndex === undefined || angle > bestAngle) {
bestIndex = index
bestAngle = angle
}
})
const nextSide = nextSides[bestIndex]
nextSides.splice(bestIndex, 1) // remove side from list
return nextSide
}

module.exports = toOutlines
``````