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

[kentdobias]

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

[JCash]

Thanks for the repro case!
I'm looking into it!

[kentdobias]

The latest version in the dev branch fixes both issues for the specific test cases I supplied and appears to have made the problems arise less frequency (especially for smaller systems) but I'm still seeing the same errors. Here (assert_failure.bin.zip) is an array of 9216 points that trips the assertion, and here (
incorrect_success.bin.zip) is an array of 9216 points that returns a non-planar tesselation. Both arrays are bound by ((-128, -16), (256, 32)), with each contained 128 × 16 tile a translated copy of its neighbors. As before, once unzipped the data can be directly read into an array of (double precision) jcv_points.

[lundmark]

Hi,

I'm also seeing this happen. It's really rare but it definitely happens. I'm attaching a testcase of 4595 points required inside a 2048 * 2048 rectangle (0..2048, 0..2048), which triggers this assert.

jcv_crash_info.txt

[JCash]

@kentdobias Thanks again for the report. I wasn't able to reproduce the assert on macOS. What platform are you on? Any special compile flags?

In the case of invalid tesselation, I can reproduce that though, so I'll continue investigate that.

[JCash]

@lundmark Thanks for the test data, but I wasn't able to reproduce a crash with it (macOS)
Here's the cleaned up test file I tested with:
testdata_issue38_2.txt

[kentdobias]

@kentdobias Thanks again for the report. I wasn't able to reproduce the assert on macOS. What platform are you on? Any special compile flags?

In the case of invalid tesselation, I can reproduce that though, so I'll continue investigate that.

Huh, the test file now works for me, too! Both my compilers were updated in the meantime—maybe something was fixed?

[lundmark]

We have also updated compilers, so maybe it's not an issue for us anymore either. I'll try to reproduce it as soon as I have time! Thanks!

[JCash]

Ok, closing for now, but feel free to reopen if the issue comes back!

[14RS]

Unfortunately I also get the same assertion error:

jcv_boxshape_fillgaps: Assertion `allocator->numsites == 1' failed.

This takes place for both version 0.7 and 0.9. The bounding box is {min = {x = -10, y = -10}, max = {x = 7009, y = 3509}}
and the 185001 points in the attached .csv file are in x,y. In case you're wondering about the compiler, I'm using GCC with the following version details:

gcc (GCC) 13.2.1 20230728 (Red Hat 13.2.1-1)

I'm looking forward to continuing this discussion.

points(185001).csv