Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^2: Better maps with Math::Geometry::Voronoi, (Working* code)

by samtregar (Abbot)
on Jul 03, 2008 at 17:09 UTC ( [id://695394]=note: print w/replies, xml ) Need Help??


in reply to Re: Better maps with Math::Geometry::Voronoi, (Working* code)
in thread Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

Awesome, thanks! I'll give this a try and let you know how it goes.

One question - does it deal with shapes that have holes in them? Unfortunately I think tye is right, that will happen. Perhaps it can explain some of the spurious edges? I'm skeptical of blaming them on the underlying Voronoi code - that's some very old, well tested code and it doesn't show any anomalies when you graph the results without joining. Happy to be proven wrong, of course, but I'd need proof based on the original data to believe it.

-sam

Replies are listed 'Best First'.
Re^3: Better maps with Math::Geometry::Voronoi, (Working* code)
by BrowserUk (Patriarch) on Jul 03, 2008 at 17:49 UTC
    does it deal with shapes that have holes in them?

    I think it should, though it may need some modification to isolate the two (or more) polygons. I'll need to construct a known testcase and see what happens.

    As for the source of the errors. The presence of 'holes' could explain the anomolies I'm seeing. But either way, the problem is exacerbated by the presence of duplicate points that are being returned in individual polys. I've tried printing the values from the simple 'squares' testcase I posted earlier, to the fullest precision Perl can give me, and this isn't a case of points that differ by infinitesimal amounts being mapped to the same pixel. The values as returned bu M::G::V are all exact integer values.

    I'm currently filtering each of the individual polys for adjacent duplicate vertices, but that won't handle the case of there being 'extra points' in the solution. If you run the code above with -PAT=hex2 and look at the grey (unfiltered) polys on the left-hand edge, you'll see that there are various edges showing up that do not obviously result from the normal dividors from the points.

    In particular, if you look at the poly in the lower left corner, the extreme left-hand edge appears to be parallel to the left edge of the coordinate space (white box). There is no way you should be able to generate a 'parallel normal' from points wholy contained within the white coordinate space--but there it is.

    I'm not accusing the underlying libraries of having errors, I just don't know any way to explain the presence of that edge (and others) based on what I know of the algorithms involved. Now I'm wondering what hoops would be involved in compiling the underlying library on Win32? (Did you post a pointer to teh source code anywhere?)

    I had to make a couple of minor edits to memory.c (in myalloc() to get it to compile with MSC. Apparently cl doesn't know how to calculate sizeof( void* )? I just switched the two occurances to char* until I got a chance to investigate that, work out the correct solution and produce a patch for you. But I do not see that it could have any affect on the math.

    I'll play and try and come up with a simple dataset that produces a 'hole' to see what happens. If you have any ideas on how to produce such a dataset, please let me know. I'm having trouble conceiving of how that can arise right now?


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^3: Is it possible to get a 'hole' in a Veronoi diagram?
by BrowserUk (Patriarch) on Jul 03, 2008 at 18:32 UTC
    One question - does it deal with shapes that have holes in them?

    You know, the more I think about this, the more I am convinced (on the basis of my own brand of logic rather than any real mathematic understanding), that it isn't possible to have a 'hole' in a Voronoi diagram?

    If someone knows better, please demonstrate?


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      I don't think you can get even a polygon that is not convex, because by construction, you start out with a convex polygon (the whole space) and all areas you're clipping away from that are using lines/half-spaces perpendicular to the line connecting the two points. If you assume a metric space with a symmetric metric respecting the triangle inequality, I have the feeling that you encounter a contradiction fairly quickly, but I haven't written down any formal proof either :)

        That all sound plausible to me. Greek, but plausible :)

        My 'proof' is somewhat erm, simpler. Working with Sam's phone box analogy from above, for there to be a hole in the middle of the phone boxes would imply an area of space between them that isn't "closest" to any of them. Which just doesn't make any sense.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
      BrowserUk:

      You can't get a polygon with a hole in it in a Voronoi diagram. He's starting with a voronoi diagram and then combining adjacent polygons of the same "color". You may then get a polygon with a "hole" in it. Example: A nine by nine array of points, where the center one is red, the eight adjacent points are all blue, and the rest of the points are red. If you take one of the blue points and merge all adjacent blue polygons until you run out, you'll get a small red polygon in the center (originally in the voronoi diagram), then a polygon surrounding that one that's blue, etc. I believe that's what was meant.

      ...roboticus

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2024-03-19 10:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found