Voronoi Diagram using Fortune's Algorithm

[mrcurry 506]

Voronoi diagram using Fortune's algorithm

Here's a set of functions developed for my current project to generate Voronoi diagrams in SQF without the need for addons.

 

What does it do?

The code generates the edges of the Voronoi diagram from a given set of sites (positions). If you do not yet know what a Voronoi diagram is or what it's uses are check out https://en.wikipedia.org/wiki/Voronoi_diagram.

 

Example: Using the Altis towns as sites

Spoiler

How do I use it?

Installation:

1. Download the example mission to get the code.
2. Copy the voronoi folder to your mission.
3. In your missions CfgFunctions class include "voronoi\cfgfunctions.ext" like so:

class CfgFunctions
{
	#include "voronoi\cfgfunctions.ext"
};

Execution:

The only included function you will need to call is VOR_fnc_getEdges:

private _edges = [_sites, _width, _height] call VOR_fnc_getEdges;

VOR_fnc_getEdges takes an array of sites (position2Ds), and width and height in meters for the area to scan. All sites must be inside the rectangle [0,0] and [width, height].

The function returns an array of edges that constitute the Voronoi diagram. Each edge is an array composed of:

[
    EDGE_START, 		- Start position
    EDGE_END, 			- End position
    EDGE_LEFT, 			- Site on the left
    EDGE_RIGHT,			- Site on the right
    EDGE_NEIGHBOUR,		- Internal usage
    EDGE_LINE_F,		- f in the function for the edge's line: y = fx + g
    EDGE_LINE_G,		- g in the function for the edge's line: y = fx + g
    EDGE_DIRECTION		- 2-dimensional direction vector of the ray going from start to end, not normalized.
]

 

Where do I get it?

Link (voronoi_example.Altis.zip)

 

Examples

Spoiler

Example call that includes the entire map

private _edges = [_sites, worldSize, worldSize] call VOR_fnc_getEdges;

An example of applying a voronoi diagram to generate areas of control

 

 

Known issues

• In some cases some edges may not find an intersection and only intersect with the bounding box. I haven't managed to isolate the issue yet but it seems to be a precision error in the intersection check. Suggestions are welcome.
• It's slow. For 50 sites a call in-mission takes about ~0.5 seconds which is very slow compared to good c++ code. Not entirely sure yet if it's because of my implementation or just SQF having a hard time with the complexity. In my in-mission testing 50 sites took about 0.5 seconds in an unscheduled environment and in scheduled took 1-2.5 seconds. During mission init the code is significantly faster, clocking in 150 sites in about 0.5 seconds. I can put this down partly to the way I handle data but not sure how much quicker I could make it. If anyone has the energy to dissect the code I'd love hear your input.

 

Feedback

Constructive feedback is always welcome.

I've probably missed cases where the code will break. If you're reporting a bug please if possible also submit the following:

• The complete set of sites passed. 
• Height and width passed.

[semiconductor 309]

This looks very intriguing but I can't really relate examples from Wiki to Arma.

Could you please elaborate a bit more on possible use cases?

[pierremgi 4898]

Probably useful with inPolygon .

[froggyluv 2136]

Yeah I read that Wiki and it broke my brain ..thanks

[mrcurry 506]

On 12/11/2018 at 3:21 PM, semiconductor said:

This looks very intriguing but I can't really relate examples from Wiki to Arma.

Could you please elaborate a bit more on possible use cases?

Yes, see further down.

 

3 hours ago, froggyluv said:

Yeah I read that Wiki and it broke my brain ..thanks

Sorry! The Wiki page is quite heavy, my bad, and Voronoi diagrams are pretty abstract as is. Took me a few weeks to wrap my head around them well enough to implement it.

Totally worth it though. :)

 

 Below are some example use cases but first a few things to keep in mind:

- All the points passed into VOR_fnc_getEdges are in the examples referred to as "sites".

- Any given voronoi edge will always be halfway between it's left site and right site. That means any point along that edge will always be the same distance from both of those sites.

- Any given voronoi vertex (where 3 edges start or end) is always the same distance from the 3 nearby sites and thereby at the center of the circle whose circumference coincides with those sites.

 

1. Largest empty circle queries

Imagine you're deploying AA positions and need to find a location to place the next one that minimises overlap with other AA positions. You can generate a voronoi diagram with the already existing AA positions as sites. By placing the new AA position at the vertex which is furthest from it's site(s) you will ensure maximum coverage using the minimum amount of AA positions.

 

2. Collision-avoidance

Credit for this idea goes to @Ed! and his post over here: https://forums.bohemia.net/forums/topic/190653-voronoi-diagram-fortunes-algorithm/

Using obstacles' positions as sites you can generate a voronoi diagram where objects placed at the edges of the diagram will have a low likelihood of colliding with those obstacles.

Useful when placing a large number of objects.

 

3. Pathfinding

From a voronoi diagram you can construct a graph that a scripted AI can use to find it's way along the sites. This is the main use I have for it with my current project where I can generate waypoints in such a way that AI units avoid areas controlled by the enemy.

 

4. Organic-looking structures

A voronoi diagram and it's cells may be a good way to represent areas of control or the result of linear growth. For example if the sites represents things like military bases and FOBs the cell belonging to that site can be thought of as the area that particular base would reasonably control. This in turn could create a believable division of an AO with little manual input.

 

Hope that helps a bit.

 

[Ed! 13]

This is super underrated.

[genesis92x 810]

This is amazing - I am curious to see how I could incorporate this into my works.