Search the Community
Showing results for tags 'fortunes'.
Found 1 result
-
Voronoi Diagram using Fortune's Algorithm
mrcurry posted a topic in ARMA 3 - MISSION EDITING & SCRIPTING
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 How do I use it? Installation: Download the example mission to get the code. 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. ] Where do I get it? Link (voronoi_example.Altis.zip) Examples 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.
