This PR introduces a HalfedgeList object (a doubly-linked list) to replace arrays in Voronoi cells. It seems a lot of time is spent on garbage collection when the createEdge method is called, since it needs to push new objects to the halfedges array of the corresponding cells.
At least in Chrome and Safari, this change gives a significant speed up when running the benchmark and Lloyd's relaxation demos with 10000 vertices.
Please note that this change would break code that needs to iterate through the existing halfedges array of the cell object though.
Iterating through halfedges would need to be done in this manner:
var halfedge = cell.halfedges.first;
while(halfedge) {
// Do something with the halfedge here
// ...
halfedge = halfedge.next;
}
Also, the HalfedgeList object is declared within the prototype of the Cell object. I'm not sure whether this is the right way to go or not. I tried declaring this within the prototype of the Voronoi object, like the Cell and Halfedge objects, but couldn't find a way to call the HalfedgeList constructor from within the Cell object's methods.
This PR introduces a HalfedgeList object (a doubly-linked list) to replace arrays in Voronoi cells. It seems a lot of time is spent on garbage collection when the createEdge method is called, since it needs to push new objects to the halfedges array of the corresponding cells.
At least in Chrome and Safari, this change gives a significant speed up when running the benchmark and Lloyd's relaxation demos with 10000 vertices.
Please note that this change would break code that needs to iterate through the existing halfedges array of the cell object though.
Iterating through halfedges would need to be done in this manner:
Also, the HalfedgeList object is declared within the prototype of the Cell object. I'm not sure whether this is the right way to go or not. I tried declaring this within the prototype of the Voronoi object, like the Cell and Halfedge objects, but couldn't find a way to call the HalfedgeList constructor from within the Cell object's methods.