enduguXL commented 7 years ago

Hello Thanks for the lib!

screenclip

jcvBounds min x -6.418 y -5.500 max x 3.140 y 0.009 jcvPoints[0] x -5.544 y -3.492 jcvPoints[1] x -5.010 y -4.586 jcvPoints[2] x 3.030 y -3.045 jcvPoints[3] x -5.279 y -5.474 edge[0] pos[0] x -1.318 y -2.105 pos[1] x -1.428 y 0.009 edge[1] pos[0] x -0.667 y -5.500 pos[1] x -1.318 y -2.105 edge[2] pos[0] x -0.762 y -5.500 pos[1] x -0.762 y -5.500 edge[3] pos[0] x -6.418 y -4.618 pos[1] x -6.418 y -4.618 edge[4] pos[0] x -6.418 y -4.596 pos[1] x -1.318 y -2.105 edge[5] pos[0] x -6.418 y -4.643 pos[1] x -3.598 y -5.500

Gray lines are XY axis Green box is bounds Green lines are valid edges Green crosses are input points Two magenta crosses are problematic edge2 and edge3

I'm using double

define JC_VORONOI_IMPLEMENTATION

define JCV_REAL_TYPE double

define JCV_ATAN2 atan2

define JCV_SQRT sqrt

define JCV_FABS fabs

include <jc_voronoi/jc_voronoi.h>

david94133 commented 6 years ago

I found this too. Edges with zero length are detected on line 1060:

if( jcv_point_eq(&e->pos[0], &e->pos[1]) ) ...

The spurious edge could be removed at that point, but edges are stored in a singly-linked list, so removing it is expensive. In my own project I just discard zero-length edges as I process them.

There are no back-links (for example from half edges to edges) to check for, so just discarding is sufficient.

JCash commented 5 years ago

As @david94133 mentions, the edges are inside a singly linked list.

I don't want to add extra memory or operations for a doubly linked list, due to the fact that iterating over the edges isn't the main part of this library, and also since skipping the invalid edges is easily done when required.

Therefore I added an iterator function const jcv_edge* jcv_diagram_get_next_edge( const jcv_edge* edge ); to do this automatically. I've updated the examples, and added a test for this too.

Will close this issue once it's merged into master.