Comments (8)
All right, will look into this...
from d3-delaunay.
Yes, I would like to do this, I just haven’t found the time.
from d3-delaunay.
@JobLeonard you only need the delaunator.hull
array, which is generated at the end of the constructor:
from d3-delaunay.
Please test PR #59.
from d3-delaunay.
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 insertNode
is:
// 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
/* ... */
}
from d3-delaunay.
I feel a bit like an idiot for not noticing that you even explain how to consruct a Voronoi in the explanation page:
https://mapbox.github.io/delaunator/
from d3-delaunay.
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[???] = ???;
}
from d3-delaunay.
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.
from d3-delaunay.
Related Issues (20)
- Generating higher-order Voronoi diagrams HOT 1
- Adding points incrementally without retriangulating HOT 3
- voronoi.cellPolygons skips null cells, and doesn’t report the cell’s index. HOT 3
- README misleading with "no-dependency library" line HOT 2
- Error with es6 worker + es6 modules HOT 18
- Would it be possible to make this work with a convex hull boundary for the Voronoi cells? HOT 2
- Delaunay points are a list of NaN HOT 1
- _edge() Comparison of numbers is unsafe HOT 5
- voronoi tiling goes a bit crazy when points are duplicated in the input HOT 1
- Broken voronoi HOT 3
- Update rollup and rollup-plugin-terser HOT 2
- Cosmetic Index out of bound check fix. HOT 1
- Minor change: Only compute bl and cl when needed. HOT 1
- renderPoints(5) crashes
- context.moveTo and context.lineTo implementation HOT 1
- Voronoi Polygon generator HOT 1
- convenience delaunay.edges() function?
- voronoi don't cover the rectangle? HOT 7
- Edges that both sides are clipped sometimes will not be identified as voronoi neighbor HOT 2
- Odd failure HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from d3-delaunay.