Extract vertices in edge-connection order from BufferGeometry for "is inside polygon" check

Questions
4

Hi,

You can do this using a half edge structure.

class HalfEdge {
  constructor(){
    this.twin = null
    this.a = null
    this.b = null
  }
}
const edges = []

triangles.forEach(triangle=>{
   triangle.forEach((vertex,vertexIndex)=>{
     const edge = new HalfEdge()
     edge.a = vertex
     edge.b = triangle[(vertexIndex + 1) % 3 ]
     edges.push(edge)
})

//now every triangle has 3 edges, we need to find which one doesnt have a twin

const edgeMap = {}

//initialize the map
vertices.forEach((v, vertexIndex) =>{
  edgeMap[vertexIndex] = {}
})

//link the edges
edges.forEach( edge=>{
  edgeMap[edge.a][edge.b] = edge
  if(edgeMap[edge.b] && edgeMap[edge.b][edge.a] ) edge.twin = edgeMap[edge.b][edge.a]
})

//isolate the boundary edges

const boundaryEdges = edges.filter( edge=> edge.twin === null )

Now it gets a little bit tricky,since you need to connect these edges. If you write the next/prev connectivity, you can traverse these and extract the edge loops. Otherwise maybe something like this:

while(boundaryEdges.length){
  const edge = boundaryEdges.pop()

  const next = boundaryEdges.splice(boundaryEdges.findIndex(e=> e.a === edge.b ), 1)
  
  edge.next = next
}

Following edge.next should give you a single loop, not connected at the end (wrapping).

2 Likes