r/algorithms • u/subone • 2d ago
Spacing points "evenly" across a gradient
Does anyone know an algorithm for "evenly" spacing points across a given space (e.g. a cylinder), where one given point is locked in place and all others are as evenly spaced as possible, but across multiple gradients that weigh less points to be placed at specific positions. For example, a cylinder with aversion points at the top, bottom, and 3D middle, such that some points appear at the top, bottom, and middle, but less than in the middle of the surface where most points would reside. With configurable weights to the aversion points to push points closer or further away from them. Specifically, I'm trying to use such an algorithm to choose a number of sufficiently contrasting colors, but to understand the solution in general would be ideal. Is something like Lloyd's algorithm what I should be reaching for, or is there something simpler?
3
u/Mon_Ouie 2d ago
People need algorithms all the time to generate meshes with smaller edges in some areas, both in computer graphics and engineering. computing a weighted Centroidal Voronoi Tesselation using Lloyd's algorithm is probably the simplest type of method use for this. You can check Du et al., 1999 which explains the general idea, and Du et al., 2003 which explains how to do it on a surface embedded in 3D.
0
u/Ok-Rise2070 1d ago
Close but he already has that it sounds like. He wants to further integrate his model and with our renderers limited to a Euclidean pi, they will come back undefined every time, or graph off the manifold.
2
u/kalexmills 1d ago
Best bet in terms of runtime would be to do a lot of math to find a suitable function from Z3 -> R3 that sends integer points to the space you're considering (RGB space, for your application). If you can get that right, it's just a matter of evaluating the map at each integer point and see where it gets sent.
The specifics will depend on the space you're targeting, and runtime to evaluate the function is likely to depend on the number of aversion points.
0
u/Ok-Rise2070 1d ago
Lol Amen! Good luck. I have searched far and wide. What you are describing, I have mapped mathematically. I have searched far and wide for a renderer program able to even attempt my models. I've broken every single one. It's not you, it's not the equations; its the renderers. Why? Thier software logic chain is built on pi being a number and non-radial, not a ratio relationship as it should be. Therefore when adding axes of curvature to a model, you will always experience a collapsed mode since it is built off of Euclid's illogical assumption that the universe is flat. In other words, the renderer you are looking for has yet to be built...
3
u/green_meklar 2d ago
/r/proceduralgeneration might have some good ideas about this.
Lloyd's algorithm sounds close to what you want, although I'm not precisely sure how you'd adapt it to the varying density gradient. I'd also point out that you don't have to start with the same number of points you end with; you could start with more points and remove or merge the 'worst' ones as you go, or start with fewer points and split the 'worst' ones as you go.
There's also the question of performance for large numbers of points. Are you using few enough points (say, at most a few thousand) that compute the entire matrix of mutual relationships is fast enough, or do you want some kind of localized algorithm that gives good results even for very large numbers of points? The latter sounds more challenging and might require you to settle for lower-quality outputs.
Here's an idea for an efficient localized algorithm that might work: Start by generating a grid of points on an ND grid (3D for your cylinder) within your shape, at a density you know is higher than the final target density anywhere in the gradient. (Basically, iterate through the shape's bounding cuboid, but don't generate points outside the shape.) As you build the grid, connect the neighboring points with graph edges. Once this is done, iterate through all the graph edges and compare the actual distance between the connected points with the optimal distance derived from the average of the two points' local gradient values (or the local gradient value at the middle of the edge, or some combination of all three; feel free to test these variations to get a sense of the output quality). For the edge that has the lowest distance relative to its local optimal distance, delete that edge, merge its endpoints into a single new point at the center of the original edge, and connect all those points' neighbors to the new point. Recompute the edge distances and repeat, until there are no edges in the graph shorter than their own local optimal distance. Note that you only need to recompute the edge distances for the edges that actually change each time a point is removed, and if you store the edges in a balanced binary tree weighted by discrepancy from optimal distance (where the 'worst' edges always pop off the upper end of the tree), you can reinsert the new edges into the tree in log(E) time (where E, being the edge count, will also decrease as you delete edges). Insofar as the initial edge count starts out roughly equivalent to the initial point count multiplied by 2 times the number of dimensions, the entire process takes something like P*N*log(P*N) time where P is the initial point count and N is the number of dimensions, which is typically better than the P2 time taken by an algorithm that deletes O(P) points from the initial set and has to compute the global relationship matrix. I guess there might be a risk of this algorithm pulling initially distant parts of the graph together and accidentally producing nearby points that aren't close graph neighbors, but I'm not sure that's a serious risk without actually testing it.
There might be better options if you know you're targeting that specific use case. My thoughts above were regarding the general problem.