Tesselation occasionally incorrect, seemingly involves having identical y coordinates

[kentdobias]

I have another malformed test case. This one returns successfully a system that is obviously not correctly tessellated. The correct tesselation (modulo a convex hull) via Mathematica: The tesselation returned by this library: I noticed this problem while processing the neighbors of points whose edges cannot have been clipped, only to find NULL neighbors. One such point, with the correct neighbors highlighted, is here: The same point, with the neighbors indicated by the library highlighted along with the segment of bounding box the clipped edge is dual to, is here: I say that this may be related to identical y coordinates because many of the points in the dataset have identical either x or y coordinates, and the malformed example involves incorrectly identified neighbors with identical y coordinates.

The data file is here: 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(288 * sizeof(jcv_point));

  FILE *in = fopen("mem.bin","rb");
  fread(points, sizeof(jcv_point), 288, in);
  fclose(in);

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

  jcv_rect rect = {{-8.0, -8.0}, {16.0, 16.0}};

  jcv_diagram_generate(288, points, &rect, &diagram);

  const jcv_site* sites = jcv_diagram_get_sites(&diagram);

  for (int i = 0; i < diagram.numsites; i++) {
    if (sites[i].index == 238) {
      printf("site 238 at {%f, %f}:\n", sites[i].p.x, sites[i].p.y);
      const jcv_graphedge* e = sites[i].edges;

      while (e != NULL) {
        if (e->neighbor != NULL) {
          printf("%d is a neighbor\n", e->neighbor->index);
        } else {
          printf("edge clipped by bounding box\n");
        }
        e = e->next;
      }

      break;
    }
  }

  /* correct output should be:
   *
   * site 238 at {6.798607, 5.040127}:
   * 76 is a neighbor
   * 86 is a neighbor
   * 139 is a neighbor
   * 148 is a neighbor
   * 166 is a neighbor
   * 221 is a neighbor
   * 265 is a neighbor
   *
   * (or a permutation of these)
   */

  return 0;
}

Example use:

> unzip mem.bin.zip
Archive:  mem.bin.zip
  inflating: mem.bin 
> clang -lm test.c
> ./a.out
site 238 at {6.798607, 5.040127}:
266 is a neighbor
edge clipped by bounding box
265 is a neighbor
184 is a neighbor
253 is a neighbor
185 is a neighbor

[JCash]

After testing this with the fix for issue #38, it now produces the correct result. Closing as duplicate.