## Re: [Algorithms] Finding a free spot for circles in a triangle mesh.

 Re: [Algorithms] Finding a free spot for circles in a triangle mesh. From: Paul Du Bois - 2004-11-29 04:27:20 ```I have a similar problem, but in 3D, and it is a pain in the butt. I do a sphere vs sea-of-triangles intersection test and find the nearest feature, then travel (penetration distance + slop) outwards along the face normal (not the feature normal; that ended up not working so well). Repeat up to N times until the sphere is not intersecting any more, increasing slop as you go. Perform a sweep test from the final position to the original position. This works OK in practice, but I don't generally have to handle difficult cases; for those, it is likely to fail after N iterations. For your problem, it might help to think about it as something like Given a set of closed polygons S, a point P, and a radius r, determine whether P is in the volume minkowski_sum(S, circle of radius r). If it is, return the closest feature. This is a pretty easy collision problem. The minkowski sum can be precomputed for a few sample radii. You could simply the sum by only expanding edges and not verts; bevel the acute corners and make a bsp; etc etc. ```

 [Algorithms] Finding a free spot for circles in a triangle mesh. From: Nick Waanders - 2004-11-25 21:27:01 ```Hi guys, I have the following problem: We have a 2D triangle mesh with each triangle marked as passable or impassable. We also have a 2D point P inside the triangle mesh. Now what we want to find is the closest 2D position to the point P that fits a circle of given radius R. The circle and it's interior cannot intersect with any impassable triangles (so it has to be entirely on a passable position). P can start on any triangle (passable or impassable) Additional info: - Needs to be fast (as in hundreds of times per second) - Can precalculate as much as we want, but we are memory limited. - Approximate position is ok, so it doesn't need to be the _absolute_ closest point. We have been thinking of a random search, or an increasing radius search, but it would be so much nicer if there was an analytical solution to this. Thanks for any help Cheers, Nick Waanders ```
 Re: [Algorithms] Finding a free spot for circles in a triangle mesh. From: Paul Du Bois - 2004-11-29 04:27:20 ```I have a similar problem, but in 3D, and it is a pain in the butt. I do a sphere vs sea-of-triangles intersection test and find the nearest feature, then travel (penetration distance + slop) outwards along the face normal (not the feature normal; that ended up not working so well). Repeat up to N times until the sphere is not intersecting any more, increasing slop as you go. Perform a sweep test from the final position to the original position. This works OK in practice, but I don't generally have to handle difficult cases; for those, it is likely to fail after N iterations. For your problem, it might help to think about it as something like Given a set of closed polygons S, a point P, and a radius r, determine whether P is in the volume minkowski_sum(S, circle of radius r). If it is, return the closest feature. This is a pretty easy collision problem. The minkowski sum can be precomputed for a few sample radii. You could simply the sum by only expanding edges and not verts; bevel the acute corners and make a bsp; etc etc. ```