nodename/as3delaunay

Delaunay triangulation and Voronoi diagram for Flash (Flash Builder 4 project)

as3delaunay's Issues

Get neighbor sites in Voronoi diagram

Is there an easy way to get neighboring sites of a site of the Voronoi diagram, where "site A is a neighbor of site B" implies that site A and B share an edge in the Voronoi diagram?

As explained in this related issue, the current getNeighborSitesForSite method should be renamed to getDelaunayNeighborSitesForSite or so, to indicate that this is not a neighbor in the sense of the Voronoi, but only in the sense of the Delaunay graph, which includes additional edges to ensure convexity of the triangulation.

I am thinking that since the current getNeighborSitesForSite method yields a superset of the wanted Voronoi neighborhood, one could easily attain this goal, if there was a method to determine whether two sites share an edge in the Voronoi diagram. I have not found such a method, but maybe I was not looking hard enough?

How to fill the voronoi or delaunay polygons

Sorry to be filing an issue for this, since it's a question actually.
I just started using this lib and cannot seem to figure out how to create fills for the polygons, whether it be for the voronoi diagram or the delaunay triangulation. Do you think you could push me in the right direction?
I followed this tutorial and have been experimenting with visualizing the edges and circles etc. but I'd really like to understand how to fill the various parts.

Voronoi.regions doesn't work

When I call voronoi.regions in following code the error is thrown:

package {
import com.nodename.Delaunay.Voronoi;
import com.nodename.geom.LineSegment;

import flash.display.Sprite;
import flash.events.Event;
import flash.geom.Point;
import flash.geom.Rectangle;

public class HelloVoronoi extends Sprite {
    private var _points:Vector.<Point>;
    private var _plotBounds:Rectangle;
    private var _voronoi:Voronoi;
    private var _segments:Vector.<LineSegment>;

    public function HelloVoronoi() {
        if (stage) init();
        else addEventListener(Event.ADDED_TO_STAGE, init);
    }

    private function init(event:Event = null):void {
        _points = new Vector.<Point>();

        for (var i:uint = 0; i < 50; i++) {
            var point:Point = new Point(Math.random() * stage.stageWidth, Math.random() * stage.stageHeight);
            _points.push(point);
        }

        _plotBounds = new Rectangle(0, 0, stage.stageWidth, stage.stageHeight);
        _voronoi = new Voronoi(_points, null, _plotBounds);

        _segments = _voronoi.voronoiDiagram();

        for each (var segment:LineSegment in _segments) {
            graphics.lineStyle(1, 0x000000, 1);
            graphics.moveTo(segment.p0.x, segment.p0.y);
            graphics.lineTo(segment.p1.x, segment.p1.y);
        } 

        var regions:Vector.<Vector.<Point>> = _voronoi.regions();

    }
}

}

TypeError: Error #1006: value is not a function.
at com.nodename.geom::Polygon/winding()
at com.nodename.Delaunay::Site/region()
at SiteList/regions()
at com.nodename.Delaunay::Voronoi/regions()
at HelloVoronoi/init()
at HelloVoronoi()

Best way to construct connected clipped Voronoi graph? - voronoiDiagram LineSegments don't line up

I just finished porting as3delaunay to C# (https://github.com/jceipek/Unity-delaunay) and I'm trying to figure out how to best expose a graph of connected nodes for the Voronoi results. It seems that adjacent LineSegments produced by Voronoi.voronoiDiagram do not have perfectly overlapping vertices; even the individual coordinates of the vertices of the LineSegments are sometimes off by a small margin.

Could you perhaps offer some suggestions as to how to create such a graph?
At the moment, I'm using a dictionary in a manner similar to the way the kruskal function works but indexing on a 2-Tuple with custom hash and equality functions to make nearby vertices hash the same way, but that seems quite kludgy and doesn't always work perfectly:

public struct Tuple : System.IEquatable<Tuple>
{
    readonly float x;
    readonly float y;

    public Tuple (float first, float second)
    {
        this.x = first;
        this.y = second;
    }

    public float X { get { return x; } }
    public float Y { get { return y; } }

    public override int GetHashCode ()
    {
        return (Mathf.RoundToInt (x)).GetHashCode () ^ (Mathf.RoundToInt (y)).GetHashCode ();
    }

    public override bool Equals (object obj)
    {
        if (obj == null || GetType () != obj.GetType ()) {
            return false;
        }
        return Equals ((Tuple)obj);
    }

    public bool Equals (Tuple other)
    {
        return Mathf.Approximately (other.x, x) && Mathf.Approximately (other.y, y);
    }
}

// After setting up lineSegments = voronoiInstance.voronoiDiagram(points,colors,rect)
Dictionary<Tuple,Node> network = new Dictionary<Tuple,Node> ();
        for (int i = 0; i< lineSegments.Count; i++) {
            Tuple p0 = new Tuple (((Vector2)lineSegments [i].p0).x, ((Vector2)lineSegments [i].p0).y);
            if (!network.ContainsKey (p0)) {
                network [p0] = new Node ();
            }

            Tuple p1 = new Tuple (((Vector2)lineSegments [i].p1).x, ((Vector2)lineSegments [i].p1).y);
            if (!network.ContainsKey (p1)) {
                network [p1] = new Node ();
            }

            if (i == r0) {
                t_a = network [p0];
            } else if (i == r1) {
                t_b = network [p1];
            }

            ConnectNodes (network [p0], network [p1]);
        }

License of Ruby Port

Aloha,

I've just finished porting as3delaunay to ruby; I can't find any information online as to whether a language port counts as 'derivative work' or a 'substantial copy' of the original, which would affect how I list your copyright and my own in the license file. Would something along the following lines be acceptable?

Original Copyright (c) 2009 Alan Shaw
Ruby Translation Copyright (c) 2013 Adam Gardner

I intend to keep the MIT license, and put it up online as soon as I've made a few tweaks and tests.

(I noticed that there's a haXe port already online, but that one is missing licensing information entirely as far as I can tell, so it wasn't much help).

`getNeighborSitesForSite` bug - How to get a graph only spanning between voronoi neighbor sites?

When looking at the Delaunay graph, Voronoi sites on the region boundary are connected to other sites that are not immediate Voronoi neighbors, but also happen to touch on the same boundary line (probably to ensure convexity of the triangulation).

When playing around with the demo, you can easily see the problem. I highlighted one such edge on the right-hand side with a long white box.The edge connects two Voronoi sites are not immediate neighbors:

If this is intended, then the getNeighborSitesForSite method should be renamed to getDelaunayNeighborSitesForSite or so, to make sure that this is not a neighbor in the sense of the Voronoi diagram?

Also, do you have a quick fix for getting such a Voronoi graph that only connects Voronoi neighbor sites?

regions bug

When calculating regions in a specific vertices configuration (two overlapping edges + some other conditions I have yet to understand), the EdgeReorderer.reorderEdges method gets stuck in an infinite loop (rightPoint and leftPoint are both null, nDone never reaches n).
I couldn't fix the bug, as a temporary fix I'm checking for overlapping vertices and removing them.
This script should be able to reproduce the bug:

var points:Vector.<Point> = new Vector.<Point>();
points.push(new Point(512, 363));
points.push(new Point(512, 363));
points.push(new Point(511, 362));
points.push(new Point(520, 345));

var voronoi:Voronoi = new Voronoi(points, null, null, new Rectangle(0, 0, 800, 600));
var segments:Vector.<LineSegment> = voronoi.voronoiDiagram();
var regions:Vector.<Vector.<Point>> = voronoi.regions();

(Wonderful implementation, by the way..)