search

Yatoom / foronoi

An implementation of Fortune's algorithm for Voronoi diagrams in Python.
MIT License
51 stars 11 forks source link

Bounding Circle implementation #6

Closed volkerjaenisch closed 3 years ago

volkerjaenisch commented 3 years ago

Dear Yatoom!

Thank you very much for this cool implementation of Fortune's algorithm.

My goal is to implement Voronoi diagrams for discs in Python. For the initialization of the disc algorithm I need a voronoi diagram clipped by a circle as a seed.

Your implementation of a bounding polygon for Voronoi diagrams aims in the same direction. So I decided to extend your code by a circular bounding box.

My code is cumbersome and no more than a most minimal experimental patch at the moment. This is just a prove of concept.

There are two critical points ATM. 1) Your code does has never thought of another type of bounding box. 2) Your great visualization code has some requirements closely related to some algorithm variables, so ATM a bounding_circle object cannot use them.

But these are minor obstacles that can easily be solved as my pull request shows. Looking forward to read from you.

Cheers, Volker

volkerjaenisch commented 3 years ago

I have to excuse myself. There are some big errors in my code. Stay tuned.

Yatoom commented 3 years ago

Hi Volker,

Thanks for your pull-request. Would be very cool to implement this into the algorithm!

There were a few issues with the plotting (empty figures, figures immediately closing and different number of arguments than expected). So I fixed these small issues, and you can find the updated files on this gist page: https://gist.github.com/Yatoom/823f58901935851bf78709a4a88285d8

Then I tried out your bounding circle, but it doesn't give the expected result yet: image Before clipping: image

volkerjaenisch commented 3 years ago

Dear Yatoom!

Thank you for looking into my pull request.

I will look into this ASAP. Approx tomorrow same time I have an answer or lots of questions :-)

Cheers,

Volker

On 09.02.21 23:20, Yatoom wrote:

Hi Volker,

Thanks for your pull-request. Would be very cool to implement this into the algorithm!

There were a few issues with the plotting (empty figures, figures immediately closing and different number of arguments than expected). So I fixed these small issues, and you can find the updated files on this gist page: https://gist.github.com/Yatoom/823f58901935851bf78709a4a88285d8 https://gist.github.com/Yatoom/823f58901935851bf78709a4a88285d8

Then I tried out your bounding circle, but it doesn't give the expected result yet: image https://user-images.githubusercontent.com/4205641/107435013-e08c7800-6b2b-11eb-84e7-0461e674c113.png Before clipping: image https://user-images.githubusercontent.com/4205641/107435096-fdc14680-6b2b-11eb-838f-3b747866aa85.png

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Yatoom/voronoi/pull/6#issuecomment-776283404, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATL6SG26N3DD2K273NT5QLS6GYMTANCNFSM4TX2O4PA.

--

inqbus Scientific Computing Dr. Volker Jaenisch Hungerbichlweg 3 +49 (8860) 9222 7 92 86977 Burggen https://inqbus.de

volkerjaenisch commented 3 years ago

Dear Yatoom!

Sorry for the delay. Can you please sketch what your expected result would look like.

I am surely no master in topology but to me it looks like what my algorithm should produce.

Cheers,

Volker

On 09.02.21 23:20, Yatoom wrote:

Hi Volker,

Thanks for your pull-request. Would be very cool to implement this into the algorithm!

There were a few issues with the plotting (empty figures, figures immediately closing and different number of arguments than expected). So I fixed these small issues, and you can find the updated files on this gist page: https://gist.github.com/Yatoom/823f58901935851bf78709a4a88285d8 https://gist.github.com/Yatoom/823f58901935851bf78709a4a88285d8

Then I tried out your bounding circle, but it doesn't give the expected result yet: image https://user-images.githubusercontent.com/4205641/107435013-e08c7800-6b2b-11eb-84e7-0461e674c113.png Before clipping: image https://user-images.githubusercontent.com/4205641/107435096-fdc14680-6b2b-11eb-838f-3b747866aa85.png

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Yatoom/voronoi/pull/6#issuecomment-776283404, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATL6SG26N3DD2K273NT5QLS6GYMTANCNFSM4TX2O4PA.

--

inqbus Scientific Computing Dr. Volker Jaenisch Hungerbichlweg 3 +49 (8860) 9222 7 92 86977 Burggen https://inqbus.de

Yatoom commented 3 years ago

Hi Volker,

I thought about it again, and it does indeed make sense. The correct dots are created and the edges connect to the correct dots. It just doesn't show nicely in the visualization that some of the edges should curve along the circle.

However, the area calculation doesn't work correctly with bounding circles yet. But I'm guessing that is quite a challenge to implement. I'm currently using the Shoelace algorithm to calculate the area of polygons, not sure how to change that for curved edges.

I suggest we merge this pull-request in and add a warning somewhere saying that area calculation doesn't work correctly. What do you think?

volkerjaenisch commented 3 years ago

Dear Yatoom!

You save my day. I was scared that my algorithm is not correct :-)- I agree fully with you to do the merge and leave a comment on the area calculation.

Cheers, Volker

On 14.02.21 01:20, Yatoom wrote:

Hi Volker,

I thought about it again, and it does indeed make sense. The correct dots are created and the edges connect to the correct dots. It just doesn't show nicely in the visualization that some of the edges should curve along the circle.

However, the area calculation doesn't work correctly with bounding circles yet. But I'm guessing that is quite a challenge to implement. I'm currently using the Shoelace algorithm to calculate the area of polygons, not sure how to change that for curved edges.

I suggest we merge this pull-request in and add a warning somewhere saying that area calculation doesn't work correctly. What do you think?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/Yatoom/voronoi/pull/6#issuecomment-778698130, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATL6SBKFMNGHOOBM37TDTLS64JONANCNFSM4TX2O4PA.

--

inqbus Scientific Computing Dr. Volker Jaenisch Hungerbichlweg 3 +49 (8860) 9222 7 92 86977 Burggen https://inqbus.de