Creating a surface of triangles from a set of 2D points...

Question

Hi,

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%5Fin%5Fpolygon

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

Use Delaunay triangulation or other .

Answer 3

Hi

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.

Regards

Mark

Answer 4

Thx everybody for the answers! JD

Answer 5

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.