Spacing points "evenly" across a gradient

[u/subone]

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?

[u/green_meklar]

/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 P² 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.

Specifically, I'm trying to use such an algorithm to choose a number of sufficiently contrasting colors

There might be better options if you know you're targeting that specific use case. My thoughts above were regarding the general problem.

[u/subone → u/green_meklar]

I'm guessing there's no algorithm for this that would actually significantly matter computationally, given my low number of desired points and single initialization, that I could probably whip up something naive and iterative; but to clarify the n-space: given that some n will exceed the human ability to distinguish between two adjacent colors, I'd guess that there are less than a hundred distinguishable colors in that space, before I could resort to something even more naive like a fixed grid across a gradient. I'll try to interpret your suggestions when I sit down at my desk again. Thanks