JCash/voronoi

voronoi map:multiple polygons intersects

lxzmxl opened this issue · 8 comments

lxzmxl commented

Hi, I'm using this code to generate voronoi with 1036 points in my project. but the result is
image
it't not a voronoi map and many polygons intersects.
I'm using this function:
jcv_diagram_generate(1036, points, &bounding_box, nullptr, &diagram)
bounding_box is
jcv_rect bounding_box = {{-45.8605, -653.969}, {746.861, 142.3}};
points is in the points.csv file.
points.csv

diagram is definited as this:
jcv_diagram diagram; memset(&diagram, 0, sizeof(jcv_diagram));
as a result, I'm using OGRGeometry library to render that diagram as above and I'm pretty sure it's not a problem of ogrGeometry library.
I also confirmed that all points are within the bounding_box and there is no abnormal point.

can you help me to handle this problem? thank you very much @JCash @dgavedissian @williamleong

JoHoop commented

This issue is related to #65 and #68.

lxzmxl commented

so how to solve it

lxzmxl commented

Any suggestion or approach is welcome

JCash commented

Hi @lxzmxl !

My guess is that it boils down to floating point precision, making calculation "explode".

Have you tried using #define JCV_REAL_TYPE double, to increase the floating point precision?

Apart from that, I have no real idea, and unfortunately I have very little time to spend on this project at the moment.
One suggested idea is to not store the points in floating point form, but keep the analytical form until the end, and then generate the final positions. That is a big rewrite I think, and I won't have any time for that anytime soon.

williamleong commented

Hi @lxzmxl , @JCash might be onto something.

I had some similar problems before switching to double precision. You may try tweaking the epsilon as well in addition, for example: #define JCV_REAL_TYPE_EPSILON 1.0e-10F.

@JCash interesting idea about not storing points in floating point, but I agree it will be a big effort.

lxzmxl commented

Hi, Thank you all very much!!
this bug can be fixed.
I changed below several things to fix this.

  1. JCV_REAL_TYPE from float to double
  2. JCV_ATAN2 from atan2f to atan2l
  3. JCV_SQRT from sqrtf to sqrtl
  4. JCV_PI from float to double
  5. change all the "==" equation, can not just use "==" to judge whether two float variables are equal. I use a Iszero function. which rewrote like this:
    bool Iszero(double x){ return std::abs(x)<1e-15}

for example:when compare whether two points are equal, I use Iszero(x1-x2) && Iszero(y1-y2）.
Then change every "==" to this Iszero function

now the voronoi map is right.
Thank you all very much again!

JoHoop commented

Could you open a PR?

lxzmxl commented

@JoHoop I will checkout a new branch to open a PR.

  • 👍1