Question

I have a set of points and I need to convert the set to (non-overlapping) triangles (or a big polygon if equivalent)...

The application: I have a list of locations (latitude,longitude) from a country, and I need to find if a given point is inside the counrty or not...

X         X                   *---------*                       *---------*
                              |      / |                      |           
                              |    /   |                      |             
     X         x      =>      |    *    |    *      = or =>     |              *
                              |   /    |   /                   |             /
                              | /      | /                     |           /
X         X                   *---------*                       *---------*

Is there an easy way or do I need a PhD to code it?

Or with a huge polygon? I found http://en.wikipedia.org/wiki/Point_in_polygon

Thx, JD

Answer 1

It would actually be easier to calculate the final polygon than constructing the polygon from triangles.

What you re looking for is the convex hull of a set of points. Many different algorithms exist to do this.

In my algorithms class, we studied the gift-wrapping algorithm (a.k.a.: The Jarvis March). It s fairly simple, but faster solutions exist.

If you want to construct the full polygon mesh, you would have to run a triangulation algorithm such as the Delaunay triangulation.

Answer 2

Your question text and question title point us in rather different directions. Do you want to figure out:

a triangulation from a set of points (Google for Delauny triangulation); or
the polygon which encloses your set of points (convex hull) or
whether a given lat,long pair is inside a country or not (point in polygon -- but this means that you have to have a polygonal representation of your country, and I guarantee that for some countries it won t be a nice convex polygon).

No, you shouldn t need a PhD to code this, they re all fairly well-documented problems in computational geometry. You ll be able to find open source software for all of the above. Your biggest problem is likely to be finding a polygonal representation of every country you are interested in.

Answer 3

Use Delaunay triangulation or other .

Answer 4

There s a library named qhull (http://www.qhull.org/) for doing this kind of job. It s solid enough to use in Blender, OGRE3D, and other apps that get serious use, and has APIs for more then just C/C++. It can even be used on the command line with simple text files of data for manual experimentation.

No need for a PhD, just a license to install 8D

There are others, but mostly of use to researchers or for special applications.

友情链接