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

[stolk]

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.

[stolk]

I caught this in my debugger.

It got triggered with both values (numitems and maxnumitems) being 6.

This is what I feed the jcv_diagram_generate:

(lldb) print points[0]
(jcv_point) $0 = (x = -0.148119405, y = 0.307878017)
(lldb) print points[1]
(jcv_point) $1 = (x = -0.0949054062, y = -0.37929377)
(lldb) print points[2]
(jcv_point) $2 = (x = 0.170877606, y = 0.477409601)
(lldb) print points[3]
(jcv_point) $3 = (x = -0.0634334087, y = 0.0787638053)
(lldb) print points[4]
(jcv_point) $4 = (x = -0.244908407, y = 0.402904421)
(lldb) print points[5]
(jcv_point) $5 = (x = -0.0830767974, y = 0.442425013)
(lldb) print *rect
(jcv_rect) $7 = {
  min = (x = -20, y = -20)
  max = (x = 20, y = 20)
}
(lldb) print num_points
(int) $8 = 6
(lldb) 

I'll try to make a minimal test case for this, to see if I can reproduce it reliably.

I examined the point set in wolfram alpha to see if it looks like a suspicious edge case, but it looks harmless to me:

https://www.wolframalpha.com/input/?i=plot++(-0.148119405,+0.307878017),+(-0.0949054062,+-0.37929377),+(0.170877606,+0.477409601),+(-0.0634334087,+0.0787638053),+(-0.244908407,+0.402904421),+(-0.0830767974,+0.442425013)

[stolk]

This is minimal code to reproduce the bug.

#include <math.h>
#include <stdio.h>
#include <assert.h>

#define JC_VORONOI_IMPLEMENTATION
#include "jc_voronoi.h"

#define WRITESVG

static jcv_point points[6] =
{
#if 1
    // these will trigger assert in queue.
    {-0.148119405, 0.307878017}, {-0.0949054062, -0.37929377}, {0.170877606, 0.477409601}, {-0.0634334087, 0.0787638053}, {-0.244908407, 0.402904421}, {-0.0830767974, 0.442425013}
#else
    // these are fine.
    0.749023,-0.836305,  -0.500977,-0.169639,  0.499023,0.497028,  -0.000977,-0.614083,  0.999023,0.052583,  -0.999512,0.719250,
#endif
};

static void output_poly( FILE* f, int numcoord, jcv_point* coords )
{
    fprintf( f, "<path d=\"M %f %f ", coords[0].x, coords[0].y );

    for ( int i=1; i<numcoord; ++i )
    {
        fprintf( f, "L %f %f ", coords[i].x, coords[i].y );
    }
    fprintf( f, "z\" stroke=\"black\" fill=\"#a0a0a0\" stroke-width=\"0.04\" />\n" );
}

const char* hdr = 
"<?xml version=\"1.0\" standalone=\"no\"?>\n"
"<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n"
"<svg width=\"400pt\" height=\"400pt\" viewBox=\"-2 -2 4 4\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n";

const char* ftr =
"</svg>\n";

int main( int argc, char* argv[] )
{
    int numpoints=6;

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

    rect.min.x = -20;
    rect.min.y = -20;
    rect.max.x =  20;
    rect.max.y =  20;
    jcv_diagram_generate( numpoints, points, &rect, &diagram );

#if defined(WRITESVG)
    // Write out the result to SVG.
    FILE* f = fopen( "out.svg", "w" );
    assert( f );
    fputs( hdr, f );
#endif

    const jcv_site* sites = jcv_diagram_get_sites( &diagram );
    assert( sites );

    for( int i = 0; i < diagram.numsites; ++i )
    {
        const jcv_site* site = sites+i;
        const jcv_graphedge* e = site->edges;

        jcv_point poly[16];
        int polylen = 0;
        while( e )
        {
            jcv_point v0 = e->pos[0];
            poly[ polylen++ ] = v0;
            e = e->next;
        }

#if defined(WRITESVG)
        // Write out the result to an SVG file.
        output_poly( f, polylen, poly );
#endif
    }

#if defined(WRITESVG)
    fputs( ftr, f );
    fclose( f );
#endif

    jcv_diagram_free( &diagram );

    return 0;
}

[stolk]

From a comment in the code:

    int max_num_events = num_points; // in rare cases, it is almost as large as the number of points

It looks like this assumption is not valid: in rare cases it can exceed the number of points.

For my purpose, it seems that taking out all the dynamic allocations wouldn't be a bad idea, and just use a MAXEDGES and MAXEVENTS typedef maybe, so that the algorithm will never have to allocate.

Let me know if you are interested in a version without dynamic allocations, and I can make a pull rq. Although I can understand if you prefer to keep the allocation in there.

[JCash]

Hi @stolk ! Thanks for the find, and great repro case!

Yes, I'll have to to research a bit to see if there's a deterministic upper limit for this. Either that, or reallocate the array, or, as you mention, pass in user defined limits.

Hopefully, I should be able to spend some time with this during the weekend.

[JCash]

Hi again @stolk ! I've now increased the max number of events to 2N, which I believe should always stay above the required number of events (the beach line can have max number of 2N-5 segments). I've also added your test case to the unit tests.

As for removing the dynamic allocations altogether, I think that's a bit tricky, since the exact number of events isn't known before hand. However, if you wish to preallocate the memory, you can do so and provide your own allocator. E.g. hand out memory from a contiguous block of preallocated memory.

These changes are now merged into master, and I've made a new release v0.4.0. Thanks for the help!