Diagram for 10 points or less

[Mr-Question]

Hello Pierre,

Regarding the algorithm in general - great work, thank you!

However, I have observed some problems during its evaluation in case of 10 points or less. In such cases application either produces artifacts (see screenshots below) or finishes execution immediately.

As for performance of the algorithm, it looks quite fast. Do you plan to add some new functionality, e.g. creation of dual graph using computed diagram?

I would like to advice you to compare it against CGAL library. Unfortunately, I have not checked it yet by myself, so I have no results to share with you.

Best regards.

[pvigier]

Hi,

Thanks for reporting the issue!

I have investigated a bit. The error was in the box intersection algorithm. It was due to floating point issues.

I am not an expert of this kind of problem. But I think I have solved the problem with commit 37917bf.

I have also updated the demo so that by pressing 'N' you generate a new random diagram. It makes testing a lot of configurations easier.

Yes I am planning to add Delaunay triangulation and Lloyd's relaxation. But not in this repo, I will refactor this code and publish it in the repo called MyGAL.

If you find a configuration where there is a problem, please note the seed (it is printed in the terminal). Otherwise, I will close this issue.

Best

[Mr-Question]

Hi,

Thanks for quick feedback! Here are some seeds causing the problems (at least ones printed last in reports) on last master.

100 points: seed: 15429614094583038 - crashes application

10 points: seed: 15429609808190186 - no window at startup, finished; seed: 15429610750504357 - appeared after pressing 'N' several times, crashes application;

6 points: seed: 15429611266005140 - crashes application; seed: 15429611577805582 - crashes application;

4 points: seed: 15429612322170400 - crashes application;

3 points: seed: 15429613602452275 - crashes application;

Hope this could help.

Regards

[pvigier]

Hi,

I was not able to reproduce any of these bugs. Just to be sure, did you pull the last version of the code, after commit 37917bf?

Maybe, the implementation of random generators is platform dependent and I have not the same points generated for the same seed as you ... I will try to check that.

Did you try a lot of seeds to find these bugs? Because I have tried more than 100 seeds for 3 points and the same for 10 points and I have not seen any problem.

Thanks a lot!

[Mr-Question]

Hello,

Just to be sure, did you pull the last version of the code, after commit 37917bf?

Yes, I am pretty sure that this patch is applied.

Maybe, the implementation of random generators is platform dependent

I'm using Visual Studio 2015, Windows 7 64 bit.

Did you try a lot of seeds to find these bugs?

Sometimes it comes quickly, sometimes immediately after launch, sometimes it is necessary to press 'N' many times to reproduce the problem.

Here is some output including source points for 4 points:

seed: 15433295013303380 0.7453251780385373 0.8233995529337189 0.3330772245389635 0.3734526729796854 0.3845301150020435 0.6844454552677216 0.288260397485413 0.2359597135551834 construction: 0ms bounding: 0ms

seed: 15433298810084257 0.1128907678069253 0.05607054582322847 0.7285254049202027 0.343636819265745 0.1758040969809487 0.1677247829619917 0.0504342985341992 0.6393606931038527 construction: 0ms bounding: 0ms

Have just noticed that output does not contain "intersection" stage.

Best regards.

[pvigier]

Hi,

Thank you for your answer.

The output you pasted confirms that the generation of points is platform dependent: I do not get the same points for the same seeds on Linux with GCC 7.3.

There was a bug in the bounding algorithm. It was responsible for most of the segmentation faults. I solved it in 97051c1. I don't know how I missed it last time. :sweat_smile:

Commits 332317d and ff260f4 make the intersection algorithm more robust to numerical issues.

Finally, I realize that a quick fix to completely avoid numerical issues in the intersection algorithm is to take a box slightly bigger for the bounding algorithm. (It also explains why there was issues only for small number of points.) Commit 556978a does that.

I ran the algorithm on 100 000 random instances for 2, 3, 4, 10 and 100 points without any crash. Moreover, I manually checked 1000 random instances for 10 points.

I am waiting that you confirm there is no issue anymore.

Thanks again!

Best

[Mr-Question]

Hi Pierre,

It is much better now, it has become more stable, thanks. However, there are some cases that still fail the program. Here they are (4 points):

seed: 15433973993384023 0.7960002482160894 0.7543302578952367 0.881993172044393 0.9816747225793874 0.9062758722556491 0.8387401544212354 0.4277366877879041 0.1959710317779039 construction: 0ms bounding: 0ms

seed: 15433974369174554 0.0325371805931953 0.03672436838973209 0.430900279683139 0.8581399288344841 0.1252969633805538 0.1395016115012137 0.9013220947109972 0.5118709541727899 construction: 0ms bounding: 0ms

seed: 15433974574104842 0.5430952309642251 0.4304022591480233 0.3939031965193771 0.7521377166730069 0.112472755676659 0.9327239382774811 0.6398966263768217 0.280392492951992 construction: 0ms bounding: 0ms

seed: 15433975410266580 0.8520037541648393 0.8675134348038052 0.4174750293140066 0.330239131532745 0.06221158711232767 0.1232908900610208 0.2733498804294691 0.2844124584621153 construction: 0ms bounding: 0ms

seed: 15433975651736922 0.6831132162818763 0.1202856000724072 0.9153969459599003 0.06383016312342278 0.1124879965128423 0.2402524080950187 0.1472527807625737 0.4377218083812771 construction: 0ms bounding: 0ms

By the way, probably it should be registered as the different issue, I have problems to build project as is using Visual Studio 2015 without modifications. Seems they are actual only for Windows platform.

There are three points:

invalid numeric argument '/Wextra'

-Wextra is removed from CMAKE_CXX_FLAGS in CMakeLists.txt

Beachline.cpp(421): error C2679: binary '<<': no operator found which takes a right-hand operand of type 'std::string' (or there is no acceptable conversion)

solved by #include \<string> in the Beachline.cpp.

FortuneAlgorithm.obj : error LNK2019: unresolved external symbol "public: __cdecl Event::Event(double,class Vector2,struct Arc *)"

Implementation of the Event(double,class Vector2,struct Arc *) has been moved to header file.

Regards!

[pvigier]

Hi,

I tried to use the coordinates you pasted to reproduce the issues but I saw nothing. I think it is platform dependent.

I will close the issue and stop working on this implementation. But, I will start working on MyGAL which will be based on this code. I will work on the issues you mentioned and test it more on Windows.

Anyway, I thank you again. You help me improving the code a lot!

Best regards

[Mr-Question]

I appreciate your efforts very well, thank you!

See you in MyGAL!