Hi, I''m programming a game with a geogrphical map. Each country is a shape (GeneralPath ''cos I''m using Java) with lines and curves & has 1 or more paths. Now I would like to know what are the neighbors of each country (by the ground and by the see ). Canada is neighbor of USA,Brazil(by see), Greenland(by see),... If someone has a little idea... Thanks

The job will be easier if you design your shapes using something like the classic "winged-edge" method. This is a way of representing geometry that explicitly stores the topology----neighbor information. For example, you define a curve that is the boundary between the USA and Canada. Then when defining the shape for USA, just use that curve in building the shape. Same for Canada, just use that curve in building the shape for Canada. Then the *curve* knows all the neighbors. Ask the curve who all the neighbors are!

This "winged-edge" method is used in what is called "non-manifold" geometry. Its also commonplace in subdivision surfaces (and progressive meshes) to maintain the topology of an arbitrary mesh that may be non-manifold.

If you build the shapes independently, its more difficult since you actually have to walk around these very complex shape hierarchically and look for coincident edges. I''ve implemented an algorithm to do just this for fully 3D curves (for a NASA project we did a few years ago) and it is very very tricky to do robustly.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

What you seem to be doing sounds extremely complex. It sounds far easier to define relationships via pointers.

For example:

class body
{
body[] myNeighbors;
}


body Canada;
Canada.myNeighbors[0] = USA;
Canada.myNeighbors[1] = Atlantic Ocean;
Canada.myNeighbors[2] = Pacific Ocean;

thus you can create a tree of nodes that point to each other.

You seem to be defining neighbors by actual geometry. Unless the application is specifically ment to determine relationships via abstract forms it would be easier, faster, and cleaner just to seperately define relationships.

However if hell bent on your approach I suggest having a list of ''lines'' that countries can point to as owning as a boarder. This definately would seperate the concept of countries having individual shapes but just making up of several boarders.

BTW: you misspelled sea

Winged-edge isn't all that complex. What I described earlier is very similar to Jindocai's approach, except that I would have:

class Curve
{
Body[] neighbors;
}

and

class Body
{
Curve[] edges;
}

Neighbors are stored at the edge level rather than the shape level.

Jindocai's approach is certainly more compact, and doesn't carry redundant information, and may be a better approach. As long as you do not need more geometric detail about where a neighbor is on the shape outline of a given country. Winged-edge is still an option in that case.

If you are wanting to know how to geometrically calculate the neighbors given shapes that are modeled independently without storing neighbor/topology information, then this is a fairly tedious problem. I would say you need to rework they way you are storing the map!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

[edited by - grhodes_at_work on April 1, 2002 5:58:49 PM]

[edited by - grhodes_at_work on April 1, 2002 5:59:29 PM]

Thanks guys