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

Hi guys, I have a scene where the player can move and look around using pointerlock controls. I would like to constrain its movements on X e Z dimensions (there are no constraints on Y because it is fixed).
To do that I’m going to use a simple algorithm to check if a point is inside a polygon (I don’t need any complex collision detection). The algorithm is the following:

function isInsidePoly(nvert, vertX, vertY, testX, testY) {
            let res = false
            let i, j;

            for (i = 0, j = nvert - 1; i < nvert; j = i++) {
                if ( ((vertY[i] > testY) !== (vertY[j] > testY) ) &&
                    (testX < (vertX[j] - vertX[i]) * (testY - vertY[i]) / (vertY[j] - vertY[i]) + vertX[i]) )
                    res = !res;

            return res;


  • nvert: number of polygon vertices.
  • vertX, vertY: arrays containing the x- and y-coordinates of the polygon’s vertices.
  • testX, testY: X- and Y-coordinate of the test point.

From here: https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon/2922778#2922778

The algorithm works fine, however in order to work properly the polygon vertices must be provided in order of edges connection, not in a random order.
My problem is that I want to design the polygon topology on Blender and then import back in Threejs. Doing so, I’ve noticed that the vertices extracted from the imported BufferGeometry are not in the edge-connection order, thus the algorithm does not work.

My question: given a BufferGeometry of a polygon, how can I extract the vertices following the edge connection order (starting from any point)?

Looks like THREE.EdgesGeometry() can do a part of the job for you :slight_smile:
It returns an array of coordinates of vertices of external edges of a shape (in pairs):

Your part of job is to connect those pairs in correct order.
Something like that:

The answer on SO is not exactly what you need, but it’s very close and with some modification you can get a desired array of coordinates of the shape’s polygon.


Thank you very much, using EdgesGeometry was a good starting point! Unfortunately the edges connections does not follow any particular order and orientation when extracted from the geometry, so I needed to write a small function to reconstruct the correct order, but it is working fine now!

1 Like


You can do this using a half edge structure.

class HalfEdge {
    this.twin = null
    this.a = null
    this.b = null
const edges = []

     const edge = new HalfEdge()
     edge.a = vertex
     edge.b = triangle[(vertexIndex + 1) % 3 ]

//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:

  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).

1 Like

I am actually facing the same issue. Do you have that function to reconstruct the correct order lying around?