Bug: graph is missing edges

[JoHoop]

First of all, thank you very much for your great work!

We're are using your implementation in a RoboCup soccer league and believe to have encountered a bug.

The points are the player's positions {-4050,0}, {-3300,500}, {0,1000}, {0,-1000}, {2250,0}. The bounding box to clip against is the field's corners {-4500,-3000}, {4500,3000}.

When iterating over the graph edges of the last point, the top right ({4500, 3000}) and bottom right ({4500,-3000}) corners of the field are missing entirely. Interestingly, changing the point {2250,0} to {2250,1} will fix the issue and the Voronoi diagram is constructed correctly.

Please find my screenshot attached.

Any help would be much appreciated. I'd be happy to submit a PR fixing the bug when found.

[JoHoop]

This is a minimal working example to paste into the src/examples/simple.c. Output edges do not contain the corners 4500 +-3000. Change points[4].y = 1.0f; to see the expected correct output. Any help would be much appreciated!!

#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
//#define JCV_CEIL ceil
//#define JCV_FLOOR floor
//#define JCV_FLT_MAX 1.7976931348623157E+308
#include "jc_voronoi.h"

#define NPOINT 5

int main(int argc, char** argv) {
  (void)argc;
  (void)argv;

  int i;
  jcv_rect bounding_box = { { -4500.0f, -3000.0f }, { 4500.0f, 3000.0f } };
  jcv_diagram diagram;
  jcv_point points[NPOINT];
  const jcv_site* sites;
  jcv_graphedge* graph_edge;

  memset(&diagram, 0, sizeof(jcv_diagram));

  points[0].x = -4050.0f;
  points[0].y = 0.0f;
  points[1].x = -3300.0f;
  points[1].y = 500.0f;
  points[2].x = 0.0f;
  points[2].y = 1000.0f;
  points[3].x = 0.0f;
  points[3].y = -1000.0f;
  points[4].x = 2250.0f;
  points[4].y = 0.0f;

  printf("# Seed sites\n");
  for (i=0; i<NPOINT; i++) {
    printf("%f %f\n", (double)points[i].x, (double)points[i].y);
  }

  jcv_diagram_generate(NPOINT, (const jcv_point *)points, &bounding_box, 0, &diagram);

  printf("# Edges\n");
  sites = jcv_diagram_get_sites(&diagram);
  for (i=0; i<diagram.numsites; i++) {

    graph_edge = sites[i].edges;
    while (graph_edge) {
      // This approach will potentially print shared edges twice
      printf("%f %f\n", (double)graph_edge->pos[0].x, (double)graph_edge->pos[0].y);
      printf("%f %f\n", (double)graph_edge->pos[1].x, (double)graph_edge->pos[1].y);
      graph_edge = graph_edge->next;
    }
  }

  jcv_diagram_free(&diagram);
}

[JoHoop]

73 fixed this issue.

Thank you very much, @JCash!

[JCash]

Aha, glad to hear it! Thanks for closing the ticket!