Upgrade to delaunator@3. #50
Comments
|
Yes, I would like to do this, I just haven’t found the time. |
|
Well, I'm currently looking into it myself, so maybe I can help! I can't promise I'll figure it out though. For now I'm experimenting with it via this notebook instead of cloning the repo. Here's what I figured out so far: As-is, it looks like v3 actually discards required information after construction, aside from the changes in logic, so cannot be used. However, if the updateable version I requested is implemented, this becomes possible again (on that note, I guess I should open an issue with a similar request here, or the ability to update won't be used in practice). That still leaves figuring out the move from the old to the new logic. Relevant bits of constructor code below Delaunator V2 constructor(coords) {
/* ... */
// initialize a circular doubly-linked list that will hold an advancing convex hull
let e = this.hull = insertNode(coords, i0);
this._hashEdge(e);
e.t = 0;
e = insertNode(coords, i1, e);
this._hashEdge(e);
e.t = 1;
e = insertNode(coords, i2, e);
this._hashEdge(e);
e.t = 2;
/* ... */
}Where // create a new node in a doubly linked list
function insertNode(coords, i, prev) {
const node = {
i,
x: coords[2 * i],
y: coords[2 * i + 1],
t: 0,
prev: null,
next: null,
removed: false
};
if (!prev) {
node.prev = node;
node.next = node;
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}Delaunator V3: constructor(coords) {
/* ... */
const hullPrev = this.hullPrev = new Uint32Array(n); // edge to prev edge
const hullNext = this.hullNext = new Uint32Array(n); // edge to next edge
const hullTri = this.hullTri = new Uint32Array(n); // edge to adjacent triangle
/* ... */
// set up the seed triangle as the starting hull
this.hullStart = i0;
let hullSize = 3;
hullNext[i0] = hullPrev[i2] = i1;
hullNext[i1] = hullPrev[i0] = i2;
hullNext[i2] = hullPrev[i1] = i0;
hullTri[i0] = 0;
hullTri[i1] = 1;
hullTri[i2] = 2;
hullHash[this._hashKey(i0x, i0y)] = i0;
hullHash[this._hashKey(i1x, i1y)] = i1;
hullHash[this._hashKey(i2x, i2y)] = i2;
/* ... */
this.hullPrev = this.hullNext = this.hullTri = null; // get rid of temporary arrays
/* ... */
} |
|
@JobLeonard you only need the |
|
I feel a bit like an idiot for not noticing that you even explain how to consruct a Voronoi in the explanation page: |
|
I’ve tried a few times to upgrade this library to Delaunator v3, and my brain just can’t keep track of the different meaning of the indexes to get it working. Like, the old code: // For points on the hull, index both the incoming and outgoing halfedges.
let node0, node1 = hull;
do {
node0 = node1, node1 = node1.next;
inedges[node1.i] = node0.t;
outedges[node0.i] = node1.t;
} while (node1 !== hull);I know I can iterate over the hull array, but I can’t figure out how to compute the equivalents to node.i and node.t in the new data structure. for (let i = 0, h0, h1 = hull[hull.length - 1]; i < hull.length; ++i) {
h0 = h1, h1 = hull[i];
inedges[???] = ???;
outedges[???] = ???;
} |
|
In particular, I think the new hull data structure doesn’t tell me the halfedge indexes of the convex hull—just the point indexes. So, I don’t think there’s an easy way to initialize inedges[i] with the halfedge index of the hull edge for a point i on the hull. |
|
All right, will look into this... |
fixes #50 note: I had to disable the tests for outeredges, because I'm not using the same outeredges (but they do point to the same nodes).
|
Please test PR #59. |
Fix Delaunay and Voronoi for degenerate cases For 0, 1, 2 points, and for collinear points: - returns the correct topology (neighbors, find) - returns the correct Voronoi cells (bounding box, half plane…) - resorts to deterministic jittering only in the case of multiple collinear points Fixes: - #19 - #20 - #50 - #65
More performance!
See also #49 ;)
The text was updated successfully, but these errors were encountered: