Feature request : get all adjacent vertices for a given vertex

[lebesnec]

I'd like to access all the adjacent vertices of a given vertex. Something like the "getNeighborIds()" method of cells would be great. May be there is already a way to do this that I missed ?

Thanks for this great library !

[gorhill]

When you say "adjacent vertices", do you mean the vertices linked through the same edges?

[lebesnec]

yes, all the vertices linked through the edges that end/start from this vertex. Like : http://en.wikipedia.org/wiki/Adjacency_list

[gorhill]

That would be possible with a somewhat complicated algortihm, using the fact that from a cell's halfedge one can get the other cell sharing the halfedge, and from there finding which other halfedge shares the vertex, etc. until all cells sharing the vertex have been processed.

Theoritically I could put code in the core algorithm in order for each vertex to keep a list of back references to all edges which refer to the vertex, but thinking of the impact on performance I would rather not do that.

[eranimo]

@gorhill you could make it a function on the Edge class. If you want to loop over all edges it's required to have this sort of functionality. I'm doing something similar to what you suggested but it's not working because I can't look up the edges by vertex reliably -- some times they're not found

[wassfila]

@eranimo , this request is pretty old, but as ticket is still open, I document it for documentation's sake. I wrapped this library in a higher level one using a cell class, where I created links to previous and next edges, this greatly facilitates circular drawing algorithms such as SVG paths creation I import the cells in a new class

    from_rhill_cell(c){
        this.seed = c.site
        this.edges = []
        for(let i=0;i<c.halfedges.length;i++){
            const he = c.halfedges[i]
            let [v1,v2] = ccw_vertices(he)
            let edge = {v1:v1,v2:v2}
            edge.l = he_length(he)
            edge.c = center(edge.v1,edge.v2)
            edge.a = c.halfedges[i].angle
            this.edges.push(edge)
        }
    }

then I create links to neighbors, on edge level though, not on vertex level, but if you need a neighboring vertex you simply then need to loop through edges, take prev next edge and using v1 only

    add_prev_next(edges){
        for(let i=0;i<edges.length;i++){
            let edge = edges[i]
            edge.prev = (i==0)?edges.slice(-1)[0]:edges[i-1]
            edge.next = (i==edges.length-1)?edges[0]:edges[i+1]
        }
    }

more here in case of interest of the details in the full integration