Voronoi diagram from Delaunay Triangles
BlitzMax Forums/BlitzMax Programming/Voronoi diagram from Delaunay Triangles
| ||
| Hi all, I need a spot of help, if someone can. I'm working on deriving the Voronoi diagram of a set of points. I already have the Delaunay triangulation of those points, and therefore can easily calculate the perpendicular bisectors I need. The problem is, I'm having trouble figuring out how to assign the start and end points to each final Voronoi edge. I'm not sure how to determine if a given intersection constitutes a better endpoint than the ones I already have. My classic outlier case at the moment is figuring the Voronoi diagram for the following points (using standard blitz screen X,Y): a - 0,5 b - 5,2 c - 10,5 d - 10,0 In that case, triangle ABC has a Voronoi line that terminates well south of the triangle itself. |
| ||
| oh man, you are cleverer than I am. I spent a couple of days trying to get fortune's algorithm to work and gave up in despair. I'm not sure what you're asking, though. Here's what I think the voronoi diagram should look like:  (Clearly the two lines going up should intersect somewhere above the image and another line will emerge from their intersection, heading vertically upwards) So there are four lines heading off into infinity. Normal procedure is just to clip them off with a bounding box and finish your cells that way. Is that what you were asking? |
| ||
| Hey Warpy! Heh - I'm not that clever, man. I'm just barely scraping by with this stuff. It is going to be interesting getting the final bugs out. I figured out how to deal with the issue I had. So, I already had my Delaunay triangles figured out, and was trying to draw the Voronoi diagram. I had each bisector as (essentially) an infinite line, and then needed to add endpoints to each one. The problem I had was that I couldn't figure out how to decide which point was which for a given Voronoi segment. For example, I was figuring out the Voronoi points of ABC and BCD, then trying to add those points to each bisector to make a Voronoi segment. Last night, with some help, I realized that I was approaching it wrong. Now, I'm figuring out each Delaunay triangle and its associated Voronoi point. Then, I look at each bisector in the whole set of bisectors... if the triangle for that bisector has another triangle adjacent to (sharing a triangle edge), then the Voronoi point of that adjacent triangle is a terminus for that edge's bisector. If the triangle has no adjacent triangle, then the line stretches to infinity. I am so glad to be done with this. ;P |
   |