Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

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

by toma (Vicar)
on Jul 03, 2008 at 04:49 UTC ( #695294=note: print w/ replies, xml ) Need Help??


in reply to 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
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

      "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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://695294]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2014-04-21 08:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (492 votes), past polls