Applying formulas to lots of data

[Trothwell]

I have two sets of XY co-ordinate data, and when plotted on a chart together as a joined up scatter chart it appears as a rectangle inside a circle, but never dead centre. I need to now how to find the smallest distance from a point on the rectangle to the nearest point on the circle. To this I have worked out that I need to apply Pythagoras theorem to both sets of data to calculate the vector. This is based on the fact that I subtract the X value for the rectangle from the X value from the circle and likewise for the Y values, this then gives me the two short sides of a right angled triangle the basic formula is this:
SQRT(ABS(Cx-Rx+Cy-Ry)), where C is the circle and R is the rectangle, the ABS is there because negative values would be involved and the ABS function returns all data as positive. This works a treat but here is the problem:
There could be well over a hundred XY co-ordinates for the circle and fifty plus to define the rectangle, for my method to work I would have to perform the calculation many hundreds of times to get the data I need for example:
If my circle has 100 XY co-ordinates and my rectangle 50 XY co-ordinates then I would have to do the calc 5000 times to return all the possible values and then extract the smallest of those.
I have looked using an array but I haven’t a clue how to apply it in this case.

I hope this makes sense.

Any advice or guidence much appreciated.

Tim

[shg]

If the shapes are a true rectangle and a true circle, and the rectangle is inside the circle, then the nearest point of the rectangle to the circle is one (or more) of the four corners -- so you only need to test four points using a formula that includes just the corner position and the center and radius of the circle.

[Trothwell]

If the shapes are a true rectangle and a true circle, and the rectangle is inside the circle, then the nearest point of the rectangle to the circle is one (or more) of the four corners -- so you only need to test four points using a formula that includes just the corner position and the center and radius of the circle.

Many thanks for the reply, maybe I was being a littlle simplistic in my attempt to explain the problem. I had been using the rectangle in a circle scenario to test my formula as the results would (or should) apply to the real problem which is... attempting to work out the minimum clearance of a vehicle passing through a tunnel. The vehicle rectangle is actually is kinematic envelope i.e the worst case profile taking into account speed and angles and any sticky-out bits on the vehicle and can have anything upto 50 xy points. The tunnel is circular in form but obviously not a geometriclly perfect circle and can consist of anything up to 100+xy points. The results would then be used to determine if a particular vehicle can safely pass through the tunnel (i.e. the smallest vector is greater than the minimum tolerance) or there may be a potential problem (i.e the smallest vector is smaller than the minimum tolerance) in which case the requires closer examination.
Must admit its making my brain hurt a bit as I know this must be possible, but all this has done is highlight my lack of knowledge of what Excel can do.

Cheers

Tim

[shg]

There are books (lots of books; see, for example, http://www.amazon.com/gp/search?inde...rds=3540656200) on computational geometry, much of it finding application in fast collision detection in computer graphics. Typically, algorithms apply sequentially more complex tests, culling as aggressively as possible as soon as one fails. For example, test against precomputed bounding radii (cheap), then axis-aligned bounding boxes (more expensive), then for actual geometry intersections (very expensive).

If your considering this as a 2D problem (or a series of 2D problems), then a a simple brute-force method detects if any point of the vehicle hull falls outside the tunnel hull:

** Setup: for each line segment of the tunnel hull and vehicle hull, compute and store the center and bounding radius.

** For each line segment of the tunnel hull
** For each line segment of the vehicle hull
**** If the bounding circles overlap, then
****** Compute the parametric intersections of the vehicle segment with the tunnel segment, where 0 and 1 represent the endpoints of each line. If the parameters of both intersections are between 0 and 1, then the lines intersect.

You could do this with a pretty large table, or VBA. Either way, it's well within Excel's capabilities.

For a 3D solution, a CAD platform would be a better place to start.

[Trothwell]

My stock-in-trade is CAD and 3D modelling applications, and yes this is something you can do in CAD but when you are dealing with many hundreds of tunnel sections it become a real pain. In a nut shell I own a Laser Scanning company and I am attempting to come up with a solution that takes the point data generated (semi) automatically and gives me an indication of were there may be a potential problem and then worthy of closer examination.

I suspect that your idea about using computational geometry is correct, I have done a little reading on this over the weekend and on the face of it it looks like it could be done. However this is way over my head, I think it is time to seek out some help via our local university.

Cheers

Tim

[shg]

See also http://opende.sourceforge.net/wiki/i...sion_Detection). If you're going to approach a university, pick one that has a strong computer graphics capability (e.g., in the US, Carnegie Mellon).

Please don't quote whole posts.