A C implementation for creating 2D voronoi diagrams

Overview
Branch OSX/Linux Windows
master Build Status Build status
dev Build Status Build status

jc_voronoi

A fast C/C++ header only implementation for creating 2D Voronoi diagrams from a point set

Uses Fortune's sweep algorithm.

vanilla custom clipping

Brief

I was realizing that the previous 2D voronoi generator I was using, was taking up too much time in my app, and worse, sometimes it also produced errors.

So I started looking for other implementations.

Given the alternatives out there, they usually lack one aspect or the other. So this project set out to achieve a combination of the good things the other libs provide.

  • Easy to use
  • Robustness
  • Speed
  • Small memory footprint
  • Single/Double floating point implementation
  • Readable code
  • Small code (single source file)
  • No external dependencies
  • Cells have a list of edges (for easier/faster relaxation)
  • Edges should be clipped
  • A clear license

But mostly, I did it for fun :)

Disclaimer

This software is supplied "AS IS" without any warranties and support

License

LICENSE (The MIT license)

Feature comparisons

Feature vs Impl voronoi++ boost fastjet jcv
Language C++ C++ C C
Edge clip * * *
Generate Edges * * * *
Generate Cells * * *
Cell Edges Not Flipped * *
Cell Edges CCW * *
Easy Relaxation *
Custom Allocator *

Usage

The api contains these functions

void jcv_diagram_generate( int num_points, const jcv_point* points, const jcv_rect* rect, const jcv_clipper* clipper, jcv_diagram* diagram );
void jcv_diagram_generate_useralloc( int num_points, const jcv_point* points, const jcv_rect* rect, const jcv_clipper* clipper, void* userallocctx, FJCVAllocFn allocfn, FJCVFreeFn freefn, jcv_diagram* diagram );
void jcv_diagram_free( jcv_diagram* diagram );

const jcv_site* jcv_diagram_get_sites( const jcv_diagram* diagram );
const jcv_edge* jcv_diagram_get_edges( const jcv_diagram* diagram );
const jcv_edge* jcv_diagram_get_next_edge( const jcv_edge* edge );

The input points are pruned if

* There are duplicates points
* The input points are outside of the bounding box
* The input points are rejected by the clipper's test function

The input bounding box is optional

The input clipper is optional, a default box clipper is used by default

Example

Example implementation (see main.c for actual code)

#define JC_VORONOI_IMPLEMENTATION
#include "jc_voronoi.h"

void draw_edges(const jcv_diagram* diagram);
void draw_cells(const jcv_diagram* diagram);

void generate_and_draw(int numpoints, const jcv_point* points, int imagewidth, int imageheight)
{
    jcv_diagram diagram;
    memset(&diagram, 0, sizeof(jcv_diagram));
    jcv_diagram_generate(count, points, 0, 0, &diagram );

    draw_edges(diagram);
    draw_cells(diagram);

    jcv_diagram_free( &diagram );
}

void draw_edges(const jcv_diagram* diagram)
{
    // If all you need are the edges
    const jcv_edge* edge = jcv_diagram_get_edges( diagram );
    while( edge )
    {
        draw_line(edge->pos[0], edge->pos[1]);
        edge = jcv_diagram_get_next_edge(edge);
    }
}

void draw_cells(const jcv_diagram* diagram)
{
    // If you want to draw triangles, or relax the diagram,
    // you can iterate over the sites and get all edges easily
    const jcv_site* sites = jcv_diagram_get_sites( diagram );
    for( int i = 0; i < diagram->numsites; ++i )
    {
        const jcv_site* site = &sites[i];

        const jcv_graphedge* e = site->edges;
        while( e )
        {
            draw_triangle( site->p, e->pos[0], e->pos[1]);
            e = e->next;
        }
    }
}

Relaxing the points

Here is an example of how to do the relaxations of the cells.

void relax_points(const jcv_diagram* diagram, jcv_point* points)
{
    const jcv_site* sites = jcv_diagram_get_sites(diagram);
    for( int i = 0; i < diagram->numsites; ++i )
    {
        const jcv_site* site = &sites[i];
        jcv_point sum = site->p;
        int count = 1;

        const jcv_graphedge* edge = site->edges;

        while( edge )
        {
            sum.x += edge->pos[0].x;
            sum.y += edge->pos[0].y;
            ++count;
            edge = edge->next;
        }

        points[site->index].x = sum.x / count;
        points[site->index].y = sum.y / count;
    }
}

Double floating point precision

If you wish to use doubles, you can override these defines:

#define JC_VORONOI_IMPLEMENTATION
#define JCV_REAL_TYPE double
#define JCV_ATAN2 atan2
#define JCV_SQRT sqrt
#define JCV_FLT_MAX DBL_MAX
#define JCV_PI 3.141592653589793115997963468544185161590576171875
//define JCV_EDGE_INTERSECT_THRESHOLD 1.0e-10F
#include "jc_voronoi.h"

Custom clipping

The library also comes with a second header, that contains code for custom clipping of edges against a convex polygon.

The polygon is defined by a set of

Again, see main.c for a practical example

    #define JC_VORONOI_CLIP_IMPLEMENTATION
    #include "jc_voronoi_clip.h"

    jcv_clipping_polygon polygon;
    // Triangle
    polygon.num_points = 3;
    polygon.points = (jcv_point*)malloc(sizeof(jcv_point)*(size_t)polygon.num_points);

    polygon.points[0].x = width/2;
    polygon.points[1].x = width - width/5;
    polygon.points[2].x = width/5;
    polygon.points[0].y = height/5;
    polygon.points[1].y = height - height/5;
    polygon.points[2].y = height - height/5;

    jcv_clipper polygonclipper;
    polygonclipper.test_fn = jcv_clip_polygon_test_point;
    polygonclipper.clip_fn = jcv_clip_polygon_clip_edge;
    polygonclipper.fill_fn = jcv_clip_polygon_fill_gaps;
    polygonclipper.ctx = &polygon;

    jcv_diagram diagram;
    memset(&diagram, 0, sizeof(jcv_diagram));
    jcv_diagram_generate(count, (const jcv_point*)points, 0, clipper, &diagram);

Some Numbers

Tests run on a Intel(R) Core(TM) i7-7567U CPU @ 3.50GHz MBP with 16 GB 2133 MHz LPDDR3 ram. Each test ran 20 times, and the minimum time is presented below

I removed the voronoi++ from the results, since it was consistently 10x-15x slower than the rest and consumed way more memory _
timings memory num_allocations

Same stats, as tables

General thoughts

Fastjet

The Fastjet version is built upon Steven Fortune's original C version, which Shane O'Sullivan improved upon. Given the robustness and speed improvements of the implementation done by Fastjet, that should be the base line to compare other implementations with.

Unfortunately, the code is not very readable, and the license is unclear (GPL?)

Also, if you want access to the actual cells, you have to recreate that yourself using the edges.

Boost

Using boost might be convenient for some, but the sheer amount of code is too great in many cases. I had to install 5 modules of boost to compile (config, core, mpl, preprocessor and polygon). If you install full boost, that's 650mb of source.

It is ~2x as slow as the fastest algorithms, and takes ~2.5x as much memory.

The boost implementation also puts the burden of clipping the final edges on the client.

The code consists of only templated headers, and it increases compile time a lot. For simply generating a 2D voronoi diagram using points as input, it is clearly overkill.

Voronoi++

The performance of it is very slow (~20x slower than fastjet) and And it uses ~2.5x-3x more memory than the fastest algorithms.

Using the same data sets as the other algorithms, it breaks under some conditions.

O'Sullivan

A C++ version of the original C version from Steven Fortune.

Although fast, it's not completely robust and will produce errors.

Gallery

I'd love to see what you're using this software for! If possible, please send me images and some brief explanation of your usage of this library!

Issues
  • Site vertices

    Site vertices

    If I want to create a mesh from the sites can I use edges and assume they are connected, i.e. iterate through edges and add each starting point to a list of vertices ?

    opened by kewp 14
  • Site-point collisions

    Site-point collisions

    Not sure where to put these comments / requests for info ...

    (Thanks for creating this library, btw ! Has saved me a lot of time and brain power)

    Is there an easy way to determine which site within the rectangle belongs to an x,y co-ordinate ? All I can think to do is loop through each one and do a polygonal collision check using each edge but I figured Voronoi is sort-of designed to know which points belong inside (that's basically the definition of a Voronoi diagram).

    opened by kewp 9
  • Assertion internal->numsites == 1 occasionally triggers on valid input.

    Assertion internal->numsites == 1 occasionally triggers on valid input.

    There is a bug in this library that occasionally causes the assertion at line 1134 (internal->numsites == 1) to fail. I do not know what the issue is, but I have attached a test program and data file that faithfully reproduce the error. Apologies for the size of the data file—this is an extremely infrequent error, and I've only been able to trigger it with sets this large.

    Test file: mem.bin.zip

    Test code:

    #include <stdio.h>
    
    #define JC_VORONOI_IMPLEMENTATION
    #define JCV_REAL_TYPE double
    #define JCV_ATAN2 atan2
    #define JCV_FLT_MAX 1.7976931348623157E+308
    #include "jc_voronoi.h"
    
    int main() {
      jcv_point *points = (jcv_point *)malloc(9216 * sizeof(jcv_point));
    
      FILE *in = fopen("mem.bin", "rb");
      fread(points, sizeof(jcv_point), 9216, in);
      fclose(in);
    
      /* should start with
         (x = 40.232121213226684, y = 13.714460519854523)
         (x = 168.23212121322669, y = 13.714460519854523)
         (x = -87.767878786773309, y = 13.714460519854523)
         (x = 40.232121213226684, y = 29.714460519854523)
         (x = 40.232121213226684, y = -2.2855394801454771)
         (x = 168.23212121322669, y = 29.714460519854523)
         (x = -87.767878786773309, y = 29.714460519854523)
         (x = 168.23212121322669, y = -2.2855394801454771)
         (x = -87.767878786773309, y = -2.2855394801454771)
         (x = 123.81366674520085, y = 1.1403291016984274)
         */
      for (unsigned int i = 0; i < 10; i++) {
        printf("(x = %.14f, y = %.14f)\n", points[i].x, points[i].y);
      }
    
      jcv_diagram diagram;
      memset(&diagram, 0, sizeof(jcv_diagram));
    
      jcv_rect rect = {{-128.0, -16.0}, {256.0, 32.0}};
    
      jcv_diagram_generate(9216, points, &rect, &diagram);
    
      return 0;
    }
    

    Example use:

    > unzip mem.bin.zip
    Archive:  mem.bin.zip
      inflating: mem.bin 
    > clang -lm test.c
    > ./a.out
    (x = 40.23212121322668, y = 13.71446051985452)
    (x = 168.23212121322669, y = 13.71446051985452)
    (x = -87.76787878677331, y = 13.71446051985452)
    (x = 40.23212121322668, y = 29.71446051985452)
    (x = 40.23212121322668, y = -2.28553948014548)
    (x = 168.23212121322669, y = 29.71446051985452)
    (x = -87.76787878677331, y = 29.71446051985452)
    (x = 168.23212121322669, y = -2.28553948014548)
    (x = -87.76787878677331, y = -2.28553948014548)
    (x = 123.81366674520085, y = 1.14032910169843)
    a.out: ./jc_voronoi.h:1134: void jcv_fillgaps(jcv_diagram *): Assertion `internal->numsites == 1' failed.
    [1]    21138 abort (core dumped)  ./a.out
    
    opened by kentdobias 8
  • List of unique vertices

    List of unique vertices

    One more issue :/

    Because I want to create a mesh, I need a list of unique vertices. These are stored as x,y points. Any idea how to do this ?

    My naive algorithm would go as follows:

    • Loop through all sites and their edges and add them all together (i.e. 5 sites each with, say, 5 edges gives a maximum of 25 vertices)
    • Now we have a maximum. Allocate an integer for each (to be used as boolean). Set all to 1.
    • Loop through again, this time with an inner loop starting from the outer loop +1
    • In the inner loop, check if the outer loop position as the same as inner. If so, set the value of the integer to 0 (not unique).

    Now we have a list of unique vertices ...

    Not very elegant. Any better ideas ?

    Also - can I just use an equals check on the positions (x1==x2) even though they are floats ?

    opened by kewp 5
  • Fix creation of edges at boundary

    Fix creation of edges at boundary

    Thanks for the library, it is great!

    opened by david94133 5
  • Assertion `pq->numitems < pq->maxnumitems' failed.

    Assertion `pq->numitems < pq->maxnumitems' failed.

    It is very rare, and saw it only once, but I was able to hit this assert:

    jc_voronoi.h:887: int jcv_pq_push(jcv_priorityqueue *, void *): Assertion `pq->numitems < pq->maxnumitems' failed.

    Unfortunately, I didn't get a core dump to investigate further.

    I feed it between 2 and 16 points, with no duplicates.

    From now on, I'll run my game in a debugger, so I can catch it and report back.

    opened by stolk 5
  • half edge neighbor is incorrect

    half edge neighbor is incorrect

    when i iterate through a site's halfedges and look at their neighbors, they do not correspond to actual neighbors. and even if i look at the half edge's corresponding edge, its two sites are not neighboring in the diagram. untitled

    opened by godpenguin7 3
  • Incorrect number of edges in specific case

    Incorrect number of edges in specific case

    When using jc_voronoi for a natural neighbor interpolation problem, I was testing jc_voronoi to make sure it was getting linked correctly by giving it a square of points at {0,0}, {val, 0}, {0, val}, {-val, 0}, and {0, -val}.

    There appears to be a bug when val = 2 in this case. I went through and was checking the number of edges that each site said it had, and the {0,0} site is always supposed to say 4. When val = 2, it says it has two. This doesn't seem to happen when I rotate or shift the square. This code runs through these cases and some other vals other than 2

    #define JC_VORONOI_IMPLEMENTATION
    #include "jc_voronoi.h"
    #include <cmath>
    #include <stdlib.h>
    #include <iostream>
    
    void printSquare( float val, int mode )
    {
      std::cout << "\nStart Of Test\n";
      int pointCount = 5;
      jcv_point list[pointCount];
      // list[0] = {  0,   0 };
    
      if( mode == 1)
      {
        //45 degree rotation on unit circle
        list[0].x = 0;
        list[0].y = 0;
        float valUpdated = val/(std::sqrt(2));
        // list[1] = { valUpdated, valUpdated };
        list[1].x = valUpdated;
        list[1].y = valUpdated;
        // list[2] = { -valUpdated, valUpdated };
        list[2].x = -valUpdated;
        list[2].y = valUpdated;
        // list[3] = { valUpdated, -valUpdated };
        list[3].x = valUpdated;
        list[3].y = -valUpdated;
        // list[4] = { -valUpdated, -valUpdated };
        list[4].x = -valUpdated;
        list[4].y = -valUpdated;
      }else if ( mode == 2)
      {
        //offset from origin
        float xOffset = std::rand() % 100 + 1;
        float yOffset = std::rand() % 100 + 1;
    
        list[0].x = 0 + xOffset;
        list[0].y = 0 + yOffset;
    
        // list[1] = { val + xOffset , 0 + yOffset };
        list[1].x = val + xOffset;
        list[1].y = 0 + yOffset;
        // list[2] = { 0 + xOffset, val + yOffset  };
        list[2].x = 0 + xOffset;
        list[2].y = val + yOffset;
        // list[3] = { -val + xOffset, 0 + yOffset  };
        list[3].x = -val + xOffset;
        list[3].y = 0 + yOffset;
        // list[4] = { 0 + xOffset, -val + yOffset };
        list[4].x = 0 + xOffset;
        list[4].y = -val + yOffset;
      }else
      {
        list[0].x = 0;
        list[0].y = 0;
        // list[1] = { val, 0 };
        list[1].x = val;
        list[1].y = 0;
        // list[2] = { 0, val };
        list[2].x = 0;
        list[2].y = val;
        // list[3] = { -val, 0 };
        list[3].x = -val;
        list[3].y = 0;
        // list[4] = { 0, -val };
        list[4].x = 0;
        list[4].y = -val;
      }
      jcv_diagram diagram;
      memset(&diagram, 0, sizeof(jcv_diagram));
      jcv_diagram_generate(pointCount, list, nullptr, &diagram);
    
      const jcv_site *sites = jcv_diagram_get_sites(&diagram);
      for( int i = 0; i < diagram.numsites; ++i )
      {
          const jcv_site* site = &sites[i];
          std::cout << "\nAt site index " << site->index << " with position (" << site->p.x << ", " << site->p.y << ")\n";
          const jcv_graphedge* e = site->edges;
          int edgeCount = 0;
    			while( e )
    			{
    			// 	std::cout << "\nSite pos  = " << site->p.x << ", " << site->p.y << "\n";
          //   std::cout << "Edge 1 pos = " << e->pos[0].x << ", " << e->pos[0].y << "\n";
          //   std::cout << "Edge 2 pos = " << e->pos[1].x << ", " << e->pos[1].y << "\n";
            edgeCount++;
    				e = e->next;
    			}
          // std::cout << "\nSite pos  = " << site->p.x << ", " << site->p.y << "\n";
          std::cout << "Number of edges is " << edgeCount << "\n";
          if(site->p.x == 0 && site->p.y == 0)
          {
            if(edgeCount != 4)
            {
              std::cout << "At (0,0) the cell does not have 4 edges!!!!!!!!!!!\n";
            }else{
              std::cout << "As expected, the cell at (0,0) has 4 edges\n";
            }
          }
      }
      std::cout << "Done printing sites and edge counts for this test\n\n\n";
      jcv_diagram_free( &diagram );
    
    }
    
    int main( int argc, const char *argv[])
    {
    
      float eps = std::numeric_limits<float>::epsilon();
      std::cout << "\nDemonstration of bug at 2\n\n";
    
      printSquare( 1, 0 );
      printSquare( 3, 0 );
      std::cout << "\nThis is the buggy one\n";
      printSquare( 2, 0 ); //issue is here
      std::cout << "\nEnd of the buggy one\n";
      printSquare( 2, 1 );
      printSquare( 2, 2 );
      printSquare( 2+2*eps, 0 );
      printSquare( 2-2*eps, 0 );
    
      std::cout << "\n\n\nEnd of Tests\n";
    
      return 0;
    
    }
    

    The result from this is

    Demonstration of bug at 2
    
    
    Start Of Test
    
    At site index 4 with position (0, -1)
    Number of edges is 4
    
    At site index 3 with position (-1, 0)
    Number of edges is 4
    
    At site index 0 with position (0, 0)
    Number of edges is 4
    As expected, the cell at (0,0) has 4 edges
    
    At site index 1 with position (1, 0)
    Number of edges is 4
    
    At site index 2 with position (0, 1)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    Start Of Test
    
    At site index 4 with position (0, -3)
    Number of edges is 4
    
    At site index 3 with position (-3, 0)
    Number of edges is 4
    
    At site index 0 with position (0, 0)
    Number of edges is 4
    As expected, the cell at (0,0) has 4 edges
    
    At site index 1 with position (3, 0)
    Number of edges is 4
    
    At site index 2 with position (0, 3)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    This is the buggy one
    
    Start Of Test
    
    At site index 4 with position (0, -2)
    Number of edges is 3
    
    At site index 3 with position (-2, 0)
    Number of edges is 2
    
    At site index 0 with position (0, 0)
    Number of edges is 2
    At (0,0) the cell does not have 4 edges!!!!!!!!!!!
    
    At site index 1 with position (2, 0)
    Number of edges is 4
    
    At site index 2 with position (0, 2)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    End of the buggy one
    
    Start Of Test
    
    At site index 4 with position (-1.41421, -1.41421)
    Number of edges is 5
    
    At site index 3 with position (1.41421, -1.41421)
    Number of edges is 5
    
    At site index 0 with position (0, 0)
    Number of edges is 4
    As expected, the cell at (0,0) has 4 edges
    
    At site index 2 with position (-1.41421, 1.41421)
    Number of edges is 5
    
    At site index 1 with position (1.41421, 1.41421)
    Number of edges is 5
    Done printing sites and edge counts for this test
    
    
    
    Start Of Test
    
    At site index 4 with position (8, 48)
    Number of edges is 4
    
    At site index 3 with position (6, 50)
    Number of edges is 4
    
    At site index 0 with position (8, 50)
    Number of edges is 4
    
    At site index 1 with position (10, 50)
    Number of edges is 4
    
    At site index 2 with position (8, 52)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    Start Of Test
    
    At site index 4 with position (0, -2)
    Number of edges is 4
    
    At site index 3 with position (-2, 0)
    Number of edges is 4
    
    At site index 0 with position (0, 0)
    Number of edges is 4
    As expected, the cell at (0,0) has 4 edges
    
    At site index 1 with position (2, 0)
    Number of edges is 4
    
    At site index 2 with position (0, 2)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    Start Of Test
    
    At site index 4 with position (0, -2)
    Number of edges is 4
    
    At site index 3 with position (-2, 0)
    Number of edges is 4
    
    At site index 0 with position (0, 0)
    Number of edges is 4
    As expected, the cell at (0,0) has 4 edges
    
    At site index 1 with position (2, 0)
    Number of edges is 4
    
    At site index 2 with position (0, 2)
    Number of edges is 4
    Done printing sites and edge counts for this test
    
    
    
    
    
    End of Tests
    

    I am not sure why this is happening, especially since it works when val = 2 + 2 *numeric_limits::epsilon.

    I am hoping someone more familiar with the code can find it the reason

    bug 
    opened by archimedes4000 3
  • Assertion on polygon bounds

    Assertion on polygon bounds

    Hey, congrats on the great library.

    I am trying to generate a voronoi diagram inside one of the cells of another voronoi diagram. I am converting the bounding polygon to a jcv_polygon and then making a clipper and setting it as a ctx.

    The generation asserts at line 218 of jc_voronoi_clip.h at this assertion assert(min_edge >= 0);

    Can you please help me understand what is happening? Thanks

    opened by Balgy 3
  • Provide simple example of usage

    Provide simple example of usage

    Thanks for the great library!

    It would be helpful to provide a simple example program of usage. The main.c is a little verbose and has a lot of cruft dealing with coloring and saving to an image file.

    Here is an example program:

    // to compile:
    //
    // gcc jc_voronoi_example.c -I../src -o jc_voronoi_example  -lm
    //
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define JC_VORONOI_IMPLEMENTATION
    // If you wish to use doubles
    //#define JCV_REAL_TYPE double
    //#define JCV_FABS fabs
    //#define JCV_ATAN2 atan2
    #include "jc_voronoi.h"
    
    #define NPOINT 10
    
    int main(int argc, char **argv) {
      int i;
      jcv_rect bounding_box = { { 0.0, 0.0 }, { 1.0, 1.0 } };
      jcv_diagram diagram;
      jcv_point points[NPOINT];
      const jcv_site *sites;
      jcv_graphedge *graph_edge;
    
      memset(&diagram, 0, sizeof(jcv_diagram));
    
      srand(0);
      for (i=0; i<NPOINT; i++) {
        points[i].x = (float)rand()/(1.0 + RAND_MAX);
        points[i].y = (float)rand()/(1.0 + RAND_MAX);
      }
    
      // seed sites
      //
      for (i=0; i<NPOINT; i++) {
        printf("%f %f\n\n", points[i].x, points[i].y);
      }
    
      jcv_diagram_generate(NPOINT, (const jcv_point *)points, &bounding_box, &diagram);
    
      sites = jcv_diagram_get_sites(&diagram);
      for (i=0; i<diagram.numsites; i++) {
    
        graph_edge = sites[i].edges;
        while (graph_edge) {
          printf("%f %f\n", graph_edge->pos[0].x, graph_edge->pos[0].y);
          printf("%f %f\n", graph_edge->pos[1].x, graph_edge->pos[1].y);
          printf("\n");
    
          graph_edge = graph_edge->next;
        }
    
      }
    
      jcv_diagram_free(&diagram);
    }
    

    The generated seed sites:

    0.840188 0.394383
    0.783099 0.798440
    0.911647 0.197551
    0.335223 0.768230
    0.277775 0.553970
    0.477397 0.628871
    0.364784 0.513401
    0.952230 0.916195
    0.635712 0.717297
    0.141603 0.606969
    

    Visualizing the seed sites and edges with gnuplot:

    jcv_voronoi_example

    This assumes you're in an example subdirectory, say, to compile and run. The number of points is hard coded and it creates the points randomly in a 1x1 box, but the above example gets across clearly how to set up, use and get useful information out of the library. Presumably this 'double covers' the half edges but for illustration purposes I don't think that's a problem.

    I'd be happy to submit a pull request if that's helpful.

    enhancement 
    opened by abetusk 3
  • Suggestion for easier user experience

    Suggestion for easier user experience

    Hey @JCash this is super helpful. I am new to github/C/C++/Voronoi, but I can still make my own Voronoi image!

    This is just a light suggestion from a C beginner standpoint -- feel free to close if that doesn't make sense to you! When I fork and clone to my repo and run "cd src && gcc main.c -o main " it will complain the

    [email protected] src % gcc main.c -o main
    Undefined symbols for architecture x86_64:
      "_wrap_stbi_write_png", referenced from:
          _main in main-3c1ce3.o
    ld: symbol(s) not found for architecture x86_64
    clang: error: linker command failed with exit code 1 (use -v to see invocation)
    

    the quick fix is to add this to the header of main.c

    #include "stb_wrapper.c"
    

    in the test.c file I will also need to include

    #include "../src/jc_voronoi.h"
    

    to get it run.

    feel free to lmk what do you think? I can help submit a PR if you like.

    Thanks again for the help!

    opened by liuyinglao 0
  • Access to the site by its index

    Access to the site by its index

    Now, to get access to a separate site by its index, you need to either make a separate array sorted by site indexes, or use a chart search. Maybe there are other ways that I can't see?

    opened by Mikez2015 0
  • Undefined Behavior - misaligned address

    Undefined Behavior - misaligned address

    Hi thank you for a great library, super easy to use. I have noticed runtime errors reported by Xcode.

    jc_voronoi.h:784:2: runtime error: store to misaligned address 0x6290000079f4 for type 'void *', which requires 8 byte alignment

    opened by ibanic 0
  • Usage of Voronoi library

    Usage of Voronoi library

    Hello, my name is Lena and I am trying to work with algorithm Event-chain and I need Voroni diagram to do it to find nearest neighbors (or 5 nearest neighbors). But I can not use your library because I work in Visual Studio 2019 and it asks for new and new files/libraries which I can not find here. Maybe you could help me to realize your library I really need it! In which program you realized your library? And maybe you know how else I can realize algorithm of find nearest neighbor. Regards.

    opened by Lena1111111111 0
  • Question about the 3D voronoi diagram

    Question about the 3D voronoi diagram

    I have a question

    I have information about the coordinates of a 3D point cloud and K-nearest neighbors. From there, what code should I refer to to create a 3D Voronoi diagram

    opened by mizuki-saito 0
  • SDL2 render?

    SDL2 render?

    Hello! Thanks for awesome work!

    Do you have an example code below, but for the SDL2?

    #define JC_VORONOI_IMPLEMENTATION
    #include "jc_voronoi.h"
    
    void draw_edges(const jcv_diagram* diagram);
    void draw_cells(const jcv_diagram* diagram);
    
    void generate_and_draw(int numpoints, const jcv_point* points, int imagewidth, int imageheight)
    {
        jcv_diagram diagram;
        memset(&diagram, 0, sizeof(jcv_diagram));
        jcv_diagram_generate(count, points, 0, 0, &diagram );
    
        draw_edges(diagram);
        draw_cells(diagram);
    
        jcv_diagram_free( &diagram );
    }
    
    void draw_edges(const jcv_diagram* diagram)
    {
        // If all you need are the edges
        const jcv_edge* edge = jcv_diagram_get_edges( diagram );
        while( edge )
        {
            draw_line(edge->pos[0], edge->pos[1]);
            edge = jcv_diagram_get_next_edge(edge);
        }
    }
    
    void draw_cells(const jcv_diagram* diagram)
    {
        // If you want to draw triangles, or relax the diagram,
        // you can iterate over the sites and get all edges easily
        const jcv_site* sites = jcv_diagram_get_sites( diagram );
        for( int i = 0; i < diagram->numsites; ++i )
        {
            const jcv_site* site = &sites[i];
    
            const jcv_graphedge* e = site->edges;
            while( e )
            {
                draw_triangle( site->p, e->pos[0], e->pos[1]);
                e = e->next;
            }
        }
    }
    
    opened by IvaOsi 0
  • How to support clip by nonconvex boundary?

    How to support clip by nonconvex boundary?

    Hi, is there any simple method to enable the library to support clip by nonconvex boundary? I tested when use concave polygon as clip polygon, the result is blank.

    opened by manuel76413 0
  • Assertion error on jcv_diagram_generate

    Assertion error on jcv_diagram_generate

    Hi. first of all, thank you so much for your great OSS. This library is very useful and easy to use. Thanks!!

    I might find an issue of this OSS. When I input a certain data into jcv_diagram_generate function, an assertion was reported:

    Assertion failed: (internal->numsites == 1), function jcv_fillgaps, file src/jc_voronoi.h, line 1143.

    This repo is a fork of your voronoi repo and I added a test code for reproducing the issue. https://github.com/AtsushiSakai/voronoi If you have time, please take a look the file test/assert_text.c file. https://github.com/AtsushiSakai/voronoi/blob/master/test/assert_test.c test/invalid_data.h includes input x-y point data for the issue.

    #38 might be a same issue.

    opened by AtsushiSakai 0
  • Time Complexity Question

    Time Complexity Question

    In my knowledge, the time complexity of Fortune's Sweepline algorithm is O(n log n). This algorithm uses a balanced binary search tree(BBST) to insert/delete parabola and to do a binary search in O(log n).

    I found that this code uses a linked list, instead of BBST. The linked list makes this code O(n^2), and it means this code will take lots of time to calculate Voronoi Diagram in specific inputs.

    Generator of test input is here.

    #!/usr/bin/ruby
    n = 1000000
    n.times do |i|
    	puts "%d %d" % [(i+1), -(i+1)]
    	puts "%d %d" % [-(i+1), -(i+1)]
    end
    

    You can check that your program is almost stopped at this part or this part.

    Actually, an implementation used linked list will work well in the average case.

    opened by zigui-ps 6
  • Running generator yields faulty edges

    Running generator yields faulty edges

    The input yields edges that goes through the entire diagram, running from 0 y to 2048 (max y). Several of these edges only have 2 corners and those corners only get one edge.

    https://gist.github.com/lundmark/548d4b9184ff1a64d40fc9040cdb6475

    The rect is: jcv_rect rect = { { 0, 0 }, { 2048, 2048 } };

    It's compiled with vs2019, with the following flags: -Od", "-Oi", "-fp:fast", "-Gm-", "-GR-", "-EHa-", "-FC", "-GF", "-WL", "-WX", "-Wall", "-MP"

    opened by lundmark 5
Releases(v0.7.0)
  • v0.7.0(Nov 2, 2019)

    • Added support for clipping against convex polygons
    • Added JCV_EDGE_INTERSECT_THRESHOLD for edge intersections
    • Fixed issue where the bounds calculation wasn’t considering all points
    Source code(tar.gz)
    Source code(zip)
  • v0.6.0(Oct 21, 2018)

  • v0.5.0(Oct 14, 2018)

    • Fixed issue where the graph edge had the wrong edge assigned (issue #28)
    • Fixed issue where a point was falsely passing the jcv_is_valid() test (issue #22)
    • Fixed jcv_diagram_get_edges() so it now returns all edges (issue #28)
    • Added jcv_diagram_get_next_edge() to skip zero length edges (issue #10)
    • Added defines JCV_CEIL/JCV_FLOOR/JCV_FLT_MAX for easier configuration
    Source code(tar.gz)
    Source code(zip)
  • v0.3.0(Apr 20, 2017)

  • v0.2.0(Apr 20, 2017)

Owner
Mathias Westerdahl
Engine developer at @defold, a free game engine. Try it out at http://www.defold.com // CTO @refold, https://www.refold.io/
Mathias Westerdahl
Creating Artificial Life with Reinforcement Learning

Although Evolutionary Algorithms have shown to result in interesting behavior, they focus on learning across generations whereas behavior could also be learned during ones lifetime.

Maarten Grootendorst 39 Nov 18, 2021
A light-weight image labelling tool for Python designed for creating segmentation data sets.

An image labelling tool for creating segmentation data sets, for Django and Flask.

null 73 Nov 22, 2021
This python-based package offers a way of creating a parametric OpenMC plasma source from plasma parameters.

openmc-plasma-source This python-based package offers a way of creating a parametric OpenMC plasma source from plasma parameters. The OpenMC sources a

Fusion Energy 6 Nov 10, 2021
A set of examples around hub for creating and processing datasets

Examples for Hub - Dataset Format for AI A repository showcasing examples of using Hub Uploading Dataset Places365 Colab Tutorials Notebook Link Getti

Activeloop 6 Oct 10, 2021
A Deep Learning based project for creating line art portraits.

ArtLine The main aim of the project is to create amazing line art portraits. Sounds Intresting,let's get to the pictures!! Model-(Smooth) Model-(Quali

Vijish Madhavan 3k Nov 24, 2021
Honours project, on creating a depth estimation map from two stereo images of featureless regions

image-processing This module generates depth maps for shape-blocked-out images Install If working with anaconda, then from the root directory: conda e

null 1 Nov 4, 2021
A forwarding MPI implementation that can use any other MPI implementation via an MPI ABI

MPItrampoline MPI wrapper library: MPI trampoline library: MPI integration tests: MPI is the de-facto standard for inter-node communication on HPC sys

Erik Schnetter 13 Nov 30, 2021
Numenta Platform for Intelligent Computing is an implementation of Hierarchical Temporal Memory (HTM), a theory of intelligence based strictly on the neuroscience of the neocortex.

NuPIC Numenta Platform for Intelligent Computing The Numenta Platform for Intelligent Computing (NuPIC) is a machine intelligence platform that implem

Numenta 6.3k Nov 24, 2021
PyTorch implementation of neural style transfer algorithm

neural-style-pt This is a PyTorch implementation of the paper A Neural Algorithm of Artistic Style by Leon A. Gatys, Alexander S. Ecker, and Matthias

null 618 Dec 1, 2021
PyTorch implementation of DeepDream algorithm

neural-dream This is a PyTorch implementation of DeepDream. The code is based on neural-style-pt. Here we DeepDream a photograph of the Golden Gate Br

null 99 Nov 21, 2021
The project is an official implementation of our CVPR2019 paper "Deep High-Resolution Representation Learning for Human Pose Estimation"

Deep High-Resolution Representation Learning for Human Pose Estimation (CVPR 2019) News [2020/07/05] A very nice blog from Towards Data Science introd

Leo Xiao 3.5k Nov 24, 2021
Image-to-Image Translation with Conditional Adversarial Networks (Pix2pix) implementation in keras

pix2pix-keras Pix2pix implementation in keras. Original paper: Image-to-Image Translation with Conditional Adversarial Networks (pix2pix) Paper Author

William Falcon 132 Nov 8, 2021
Python implementation of cover trees, near-drop-in replacement for scipy.spatial.kdtree

This is a Python implementation of cover trees, a data structure for finding nearest neighbors in a general metric space (e.g., a 3D box with periodic

Patrick Varilly 26 Sep 13, 2021
Home repository for the Regularized Greedy Forest (RGF) library. It includes original implementation from the paper and multithreaded one written in C++, along with various language-specific wrappers.

Regularized Greedy Forest Regularized Greedy Forest (RGF) is a tree ensemble machine learning method described in this paper. RGF can deliver better r

RGF-team 352 Nov 19, 2021
Implementation of Restricted Boltzmann Machine (RBM) and its variants in Tensorflow

xRBM Library Implementation of Restricted Boltzmann Machine (RBM) and its variants in Tensorflow Installation Using pip: pip install xrbm Examples Tut

Omid Alemi 52 Nov 14, 2021
A fast Evolution Strategy implementation in Python

Evostra: Evolution Strategy for Python Evolution Strategy (ES) is an optimization technique based on ideas of adaptation and evolution. You can learn

Mika 240 Nov 27, 2021
🌳 A Python-inspired implementation of the Optimum-Path Forest classifier.

OPFython: A Python-Inspired Optimum-Path Forest Classifier Welcome to OPFython. Note that this implementation relies purely on the standard LibOPF. Th

Gustavo Rosa 21 Nov 8, 2021
Implementation of Geometric Vector Perceptron, a simple circuit for 3d rotation equivariance for learning over large biomolecules, in Pytorch. Idea proposed and accepted at ICLR 2021

Geometric Vector Perceptron Implementation of Geometric Vector Perceptron, a simple circuit with 3d rotation equivariance for learning over large biom

Phil Wang 35 Oct 10, 2021
Official implementation of AAAI-21 paper "Label Confusion Learning to Enhance Text Classification Models"

Description: This is the official implementation of our AAAI-21 accepted paper Label Confusion Learning to Enhance Text Classification Models. The str

null 74 Nov 19, 2021