Author: mrcurry Author Website: Requirements: No addons required Version: 1.00 Short description: The code generates the edges of the Voronoi diagram from a given set of sites (positions). Date: 2018-11-06 10:26 Comments: (0) Rating:

Voronoi Diagram using Fortune's Algorithm

by
mrcurry

Description:
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.

Installation / Usage:
For usage instructions and information of how to use the Voronoi Diagram using Fortune's Algorithmplease refer to the included documentation and/or example mission.

Copy the voronoi folder to your mission.
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.
]

Example call that includes the entire map
private _edges = [_sites, worldSize, worldSize] call VOR_fnc_getEdges;

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.

Notes:
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.

Changelog:
1.00

Forum topic:
- BI forums