### [Algorithms] Nearest shapes to a point

2008-07-02 21:17:23 GMT

Hi there I'm delurking to ask a question for a friend of mine. He's trying to solve a problem which amounts to this: There's a series of complex shapes (essentially long curving pipes which may twist, split, rejoin etc). The space may have five or six of these (or more), each a separate network but wound around each other in complex ways. He has a point in the space and he needs to know which network is nearest to the point. He can calculate anything about the space and the networks ahead of time, but the calculation itself is a real-time problem. My feeling is that there are two main approaches that could work, but I'm obviously open to other suggestions. Option 1: The networks are being given to him just as a bunch of models, but there's no reason in principle why he couldn't analyse them and convert them to a series of splines. One option would be to store these splines as a series of lists at a progressively greater level of detail, including some metric defining how good the detail is (how closely the spline matches the curve, eg a maximum distance from the real curve to the spline segment). Then he could take the point and calculate the nearest splines at each level of detail (taking into account the margin of error), gradually homing in until only one segment is selected. I can visualise this algorithm pretty well, but I don't know how efficient it would be, or how easy it would be to calculate the splines - especially since his client wants to be able to add new networks at a later date without additional coding. Option 2: He could take the whole space and partition it in some way into regions such that each region belongs to a particular network, ie, for every(Continue reading)