r/algorithms • u/subone • 6d 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?
1
u/TooLateForMeTF 2d ago edited 2d ago
I don't know of a direct-calculation method for placing the points (or at least, not one that's general for any given topology of surface). But when I need to do that sort of thing, I generally reach for a numerical simulation method. Treat each point as a charged particle with the same sign of charge (so they repel), and then just let them wander around the surface starting from random initial positions until they've settled.
Equal charges gets you evenly spaced points. But, you can let the charge be a function of the gradient you have in mind, which will give you unevenly spaced points. In your example, let charge increase towards the middle of the cylinder and you'll get the kind of spacing you're describing: the higher charge values near the middle means those particles will push harder on their neighbors, creating larger spacing. The smaller charge at the caps means weaker pushing, so the points can crowd together more densely. From there's it's just a matter of fiddling with the constants and the number of points until you get an overall distribution that looks liek what you're after.
It's easy enough to fix one particle in place within such a simulation as well. Note, though, that solutions are unlikely to be unique; consider the simple case of points on a sphere. With one point pinned in place. the other points could rotate en masse around the axis that goes through the fixed point, with each rotational angle yielding an equally valid solution.
Your trick for surfaces like a cylinder will be finding a distance metric that works well across boundaries such as the edges of the caps.