Here is a problem I am trying to solve:
I have an irregular shape. How would I go about evenly distributing 5 points on this shape so that the distance between each point is equal to each other?
+6
A:
Hi Saliem,
this is mathematically impossible. It will only work for a small subset of base shapes.
There are however some solutions you might try:
Analytic approach. Start with a point P0, create a sphere around P0 and intersect it with the base shape, giving you a set of curves C0. Then create another point P1 somewhere on C0. Again, create a sphere around P1 and intersect it with C0, giving you a set of points C1, your third point P2 will be one of the points in C1. And so on and so forth. This approach guarantees distance constraints, but it also heavily depends on initial conditions.
Iterative approach. Essentially form-finding. You create some points on the object and you also create springs between the ones that share a distance constraint. Then you solve the spring forces and move your points accordingly. This will most likely push them away from the base shape, so you need to pull them back onto the base shape. Repeat until your points are no longer moving or until the distance constraint has been satisfied within tolerance.
Sampling approach. Convert your base geometry into a voxel space, and start scooping out all the voxels that are too close to a newly inserted point. This makes sure you never get two points too close together, but it also suffers from tolerance (and probably performance) issues.
If you can supply more information regarding the nature of your geometry and your constraints, a more specific answer becomes possible.
David Rutten
2009-09-10 18:01:13
What base shapes are you talking about? There is no way to place five points in space (of at most three dimensions) and have all pairwise distances equal. This is easy to see from the analytic approach you mention. The first three points (ABC) will form an equilateral triangle; the next (D) will make it a regular tetrahedron. When you try to place the fifth (E), if you make it equidistant from ABC, it will either be at D or the reflection of D over the plane defined by ABC, and then DE will not be the correct distance.
Jefromi
2009-09-10 18:07:55
i'm not entirely sure what you mean by the nature of the geometry and the constraints...but the irregular shape is a locality / neighborhood. the nodes are latitude and longitude points
saliem
2009-09-10 18:14:46
@Jefromi; you cannot have ALL points be an equal distance from each other, but if you have 5 points and 10 distance constraints, a solution *might* be possible.
David Rutten
2009-09-10 18:20:02
So we're working on the surface of the earth? Are we measuring distances along the edge of the shape (not the usual metric!), or directly (on a sphere, also not the usual metric!)? Do we want every single pairwise distance equal, or are we just looking for AB = BC = CD = DE = EA?
Jefromi
2009-09-10 18:21:08
@saliem; by the nature of the shape I mean the definition of it. Is it a mathematical surface? Is it a freeform surfaces defined as a triangular mesh, or perhaps a Nurbs patch. Is your surface continuous, closed, smooth, G1? etc. etc.By the nature of the constraints I mean just the basic information. How many constraints do you have. Are they all the same distance, or different distances. Is there tolerance involved in your problem?
David Rutten
2009-09-10 18:22:12
Exactly David - by having specific geometries that are not necessarily standard 3-d geometries, you can get this behavior. It cannot happen in a standard Euclidean 3d.
aperkins
2009-09-10 22:03:47
Five points with equal distance from each other is easily possible in four dimensional space. The vertices of a regular 4-simplex have all the same distance from each other. So the claim "is mathematically impossible" is not true unless you specify "in three or less dimensions".
drhirsch
2009-09-10 22:23:55
+2
A:
David says this is impossible, but in fact there is an answer out of left field: just put all your points on top of each other! They'll all have the same distance to all the other points: zero.
In fact, that's the only algorithm that has a solution (i.e. all pairwise distances are the same) regardless of the input shape.
I know the question asks to put the points "evenly", but since that's not formally defined, I expect that was just an attempt to explain "all pairwise distances are the same", in which case my answer is "even".
redtuna
2009-09-21 13:43:18