Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

I suggest using Triangle (offsite link) to mesh your data, then load the resultant undirected graph into the Graph module, then do whatever work needs to be done. Triangle will handle whatever challenges your data has, unless it doesn't, in which case you can clean up the data on the way in to Triangle. If you can't clean it up, you will have a research project on your hands.

This is an example where floating point numbers can be a problem. For example, consider three lines that intersect at a single point. Due to floating point errors, this tends to generate a tiny triangle instead of a single point intersection. Issues such as this are covered in the Triangle documentation.

It should work perfectly the first time! - toma

Comment on Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

Replies are listed 'Best First'.
Re^2: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks by samtregar (Abbot) on Jul 03, 2008 at 17:26 UTC
Interesting - I hadn't run into Triangle before. I'll dig into the docs. But I do have one question if you have the time - what does it mean to "mesh" my data? If I pass Triangle a set of polygons that should all be considered a single shape, what would I get back? Luckily for me my data is on an integer grid so I think I'll be spared the problems floats can cause. -sam	[reply]
Re^3: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks by toma (Vicar) on Jul 08, 2008 at 18:42 UTC
"Meshing" is the process of splitting up your geometry into fundamental shapes such as triangles or squares or rectangles. You can pass triangle a set of polygons and get back a bunch of triangles that correspond to a single shape. For example, you can make a very good polygon merge program by starting with Triangle. It handles holes, non-convex shapes, and other problems without difficulty. You'll have to look at Triangle to see what all it does. It is a large topic. I use it to find messed up geometries in large collections of polygons. For example, my code detects self-intersecting polygons (that is, 'bow ties'). There are about a half-dozen such checks that I do on each polygon. The polygons can have hundreds of points or more. My code typically runs one polygon at a time over a collection of about 60,000 polygons. My perl code creates Triangle input files, calls Triangle from backticks, and then processes the Triangle output file. The Graph module is handy for loading the Triangle output data. It should work perfectly the first time! - toma	[reply]