Aphex_Twin

The problem is this. You have a predefined space (say a square), in which there are a series of "obstacles" (concave or convex polygons).

Can you help me with a couple of ideas, links, suggestions on an algorithm that finds the shortest path between two arbitrary points in that space (granted, of course, if neither A, nor B are inside any of the obstacles)?


Secondly, if you have a random concave polygon, do you know of an algorithm that can split it into a minimum number of triangles and the combined perimeter of the new shapes is minimal?

Ooble

For the first, look up Dijkstra's Shortest Path Algorithm.

__________________
Me :: You :: Them

Aphex_Twin

Here is what I have in mind.

I have an "enclosure" made up of passable and impassable terrain. In the picture below the impassable terrain is black.

So everything is made up of polygons. My purpose is to construct an algorithm that could divide the terrain into triangles as it is shown in the picture. Well, the larger or more obtuse triangles could themselves be subdivided into smaller triangles if it is necessary.

Now if we take the centers of weight of the triangles (the blue dots) and join them with the centers of weight of the neighbouring triangles (triangles that share at least a vertice) we can arrange the terrain as an un-oriented graph. The nice thing about this setting is that you can always find a path from point A to B if both A and B are in passable terrain (and here is where Dijkstra comes in).

I would appreciate any hints and ideas

Attached Images

map.GIF (7.1 KB, 50 views)

Ooble

What do you need help with? You seem to have got it!

__________________
Me :: You :: Them