[ANN] Voronyj Diagram

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

[ANN] Voronyj Diagram

Natalia Tymchuk
Hello.

I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.

Best regards,
Natalia
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

Tudor Girba-2
Wow!

I will certainly look at this in more details.

Doru


On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk <[hidden email]> wrote:
Hello.

I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.

Best regards,
Natalia



--

"Every thing has its own flow"
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

SergeStinckwich
In reply to this post by Natalia Tymchuk
Great work, great website, Natalia !
Might be interested to mix Voronoi diagrams with multi-agent and
epidemiology modeling in the future.
Thank you.

BTW, this kind of diagram are called Voronoi diagrams in english:
https://en.wikipedia.org/wiki/Voronoi_diagram

On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk
<[hidden email]> wrote:
> Hello.
>
> I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
> I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.
>
> Best regards,
> Natalia



--
Serge Stinckwich
UCBN & UMI UMMISCO 209 (IRD/UPMC)
Every DSL ends up being Smalltalk
http://www.doesnotunderstand.org/

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

Natalia Tymchuk
Hi.
Thank you. I know about Voronoi, but Georgiy Voronyj was Ukrainian and actually he called Voronyj.
Voronyj means the raven color in Ukrainian. Russians translate casual nouns in proper names. In this way they get Voronoi.  
It is like if you translate Villeneuve-d'Ascq to English as Novoselok-d'Ascq because villeneuve literally translates to novoselok in Russian, or it like calling George Bush as Yuriy Kust.
Sorry, I know that everyone use Voronoi, but I belive that I should use real name.

Best regards,
Natalia


On Jul 25, 2014, at 3:16 PM, Serge Stinckwich <[hidden email]> wrote:

> Great work, great website, Natalia !
> Might be interested to mix Voronoi diagrams with multi-agent and
> epidemiology modeling in the future.
> Thank you.
>
> BTW, this kind of diagram are called Voronoi diagrams in english:
> https://en.wikipedia.org/wiki/Voronoi_diagram
>
> On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk
> <[hidden email]> wrote:
>> Hello.
>>
>> I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>> I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.
>>
>> Best regards,
>> Natalia
>
>
>
> --
> Serge Stinckwich
> UCBN & UMI UMMISCO 209 (IRD/UPMC)
> Every DSL ends up being Smalltalk
> http://www.doesnotunderstand.org/
>


Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

SergeStinckwich
Sorry no problem.
I didn't want to annoy you.

Regards,

On Fri, Jul 25, 2014 at 4:49 PM, Natalia Tymchuk
<[hidden email]> wrote:

> Hi.
> Thank you. I know about Voronoi, but Georgiy Voronyj was Ukrainian and actually he called Voronyj.
> Voronyj means the raven color in Ukrainian. Russians translate casual nouns in proper names. In this way they get Voronoi.
> It is like if you translate Villeneuve-d'Ascq to English as Novoselok-d'Ascq because villeneuve literally translates to novoselok in Russian, or it like calling George Bush as Yuriy Kust.
> Sorry, I know that everyone use Voronoi, but I belive that I should use real name.
>
> Best regards,
> Natalia
>
>
> On Jul 25, 2014, at 3:16 PM, Serge Stinckwich <[hidden email]> wrote:
>
>> Great work, great website, Natalia !
>> Might be interested to mix Voronoi diagrams with multi-agent and
>> epidemiology modeling in the future.
>> Thank you.
>>
>> BTW, this kind of diagram are called Voronoi diagrams in english:
>> https://en.wikipedia.org/wiki/Voronoi_diagram
>>
>> On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk
>> <[hidden email]> wrote:
>>> Hello.
>>>
>>> I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>>> I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.
>>>
>>> Best regards,
>>> Natalia
>>
>>
>>
>> --
>> Serge Stinckwich
>> UCBN & UMI UMMISCO 209 (IRD/UPMC)
>> Every DSL ends up being Smalltalk
>> http://www.doesnotunderstand.org/
>>
>



--
Serge Stinckwich
UCBN & UMI UMMISCO 209 (IRD/UPMC)
Every DSL ends up being Smalltalk
http://www.doesnotunderstand.org/

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

PabloEstefo
In reply to this post by Natalia Tymchuk
Hi Natalia, 

Nice work, I really liked the southamerica map with the Voronyj diagram. 
And the website is also cool: nice organization and style.

Pablo

On 25 July 2014 16:49, Natalia Tymchuk <[hidden email]> wrote:
Hi.
Thank you. I know about Voronoi, but Georgiy Voronyj was Ukrainian and actually he called Voronyj.
Voronyj means the raven color in Ukrainian. Russians translate casual nouns in proper names. In this way they get Voronoi.
It is like if you translate Villeneuve-d'Ascq to English as Novoselok-d'Ascq because villeneuve literally translates to novoselok in Russian, or it like calling George Bush as Yuriy Kust.
Sorry, I know that everyone use Voronoi, but I belive that I should use real name.

Best regards,
Natalia


On Jul 25, 2014, at 3:16 PM, Serge Stinckwich <[hidden email]> wrote:

> Great work, great website, Natalia !
> Might be interested to mix Voronoi diagrams with multi-agent and
> epidemiology modeling in the future.
> Thank you.
>
> BTW, this kind of diagram are called Voronoi diagrams in english:
> https://en.wikipedia.org/wiki/Voronoi_diagram
>
> On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk
> <[hidden email]> wrote:
>> Hello.
>>
>> I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>> I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.
>>
>> Best regards,
>> Natalia
>
>
>
> --
> Serge Stinckwich
> UCBN & UMI UMMISCO 209 (IRD/UPMC)
> Every DSL ends up being Smalltalk
> http://www.doesnotunderstand.org/
>



Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

abergel
In reply to this post by Natalia Tymchuk
Impressive!!!!

Natalia, will you be at esug?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.



On Jul 25, 2014, at 8:10 AM, Natalia Tymchuk <[hidden email]> wrote:

Hello.

I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.

Best regards,
Natalia
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Voronyj Diagram

Natalia Tymchuk
In reply to this post by SergeStinckwich
 No problem. I just wanted to explain.

 
On Jul 25, 2014, at 5:00 PM, Serge Stinckwich <[hidden email]> wrote:

> Sorry no problem.
> I didn't want to annoy you.
>
> Regards,
>
> On Fri, Jul 25, 2014 at 4:49 PM, Natalia Tymchuk
> <[hidden email]> wrote:
>> Hi.
>> Thank you. I know about Voronoi, but Georgiy Voronyj was Ukrainian and actually he called Voronyj.
>> Voronyj means the raven color in Ukrainian. Russians translate casual nouns in proper names. In this way they get Voronoi.
>> It is like if you translate Villeneuve-d'Ascq to English as Novoselok-d'Ascq because villeneuve literally translates to novoselok in Russian, or it like calling George Bush as Yuriy Kust.
>> Sorry, I know that everyone use Voronoi, but I belive that I should use real name.
>>
>> Best regards,
>> Natalia
>>
>>
>> On Jul 25, 2014, at 3:16 PM, Serge Stinckwich <[hidden email]> wrote:
>>
>>> Great work, great website, Natalia !
>>> Might be interested to mix Voronoi diagrams with multi-agent and
>>> epidemiology modeling in the future.
>>> Thank you.
>>>
>>> BTW, this kind of diagram are called Voronoi diagrams in english:
>>> https://en.wikipedia.org/wiki/Voronoi_diagram
>>>
>>> On Fri, Jul 25, 2014 at 2:10 PM, Natalia Tymchuk
>>> <[hidden email]> wrote:
>>>> Hello.
>>>>
>>>> I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>>>> I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.
>>>>
>>>> Best regards,
>>>> Natalia
>>>
>>>
>>>
>>> --
>>> Serge Stinckwich
>>> UCBN & UMI UMMISCO 209 (IRD/UPMC)
>>> Every DSL ends up being Smalltalk
>>> http://www.doesnotunderstand.org/
>>>
>>
>
>
>
> --
> Serge Stinckwich
> UCBN & UMI UMMISCO 209 (IRD/UPMC)
> Every DSL ends up being Smalltalk
> http://www.doesnotunderstand.org/


Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Natalia Tymchuk
In reply to this post by abergel
Thank you.
Yes, I will.

Natalia

On Jul 25, 2014, at 5:36 PM, Alexandre Bergel <[hidden email]> wrote:

Impressive!!!!

Natalia, will you be at esug?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.



On Jul 25, 2014, at 8:10 AM, Natalia Tymchuk <[hidden email]> wrote:

Hello.

I implemented Voronyj diagrams for Roassal. You can read about it here: http://natalia.tymchuk.me/RTVoronyjDiagram/ .
I will be on vacation from Monday till Thursday, but it will be really cool if you can write me your opinion about this project and all your remarks.

Best regards,
Natalia
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Damien Pollet
Hi Natalia,

I've been playing with it today, and look at the pretty pixels it makes :D
The points are generated by the poisson disc sampling algorithm
described at http://bost.ocks.org/mike/algorithms/

However, see the result of the doit, in red… the time grows really
quick with the number of nodes, which makes it impractical with large
point sets (the 2 smaller sets are instant, the 3rd one quickly pops
the progress bar, and the 4th takes a couple minutes). Wikipedia says
the complexity should be around N log N, so that's strange ; I've seen
the code copies collections a lot, that might be it… but it's too late
for coding now :|

On 25 July 2014 19:12, Natalia Tymchuk <[hidden email]> wrote:

> Thank you.
> Yes, I will.
>
> Natalia
>
> On Jul 25, 2014, at 5:36 PM, Alexandre Bergel <[hidden email]>
> wrote:
>
> Impressive!!!!
>
> Natalia, will you be at esug?
>
> Alexandre
> --
> _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
> Alexandre Bergel  http://www.bergel.eu
> ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
>
>
>
> On Jul 25, 2014, at 8:10 AM, Natalia Tymchuk <[hidden email]>
> wrote:
>
> Hello.
>
> I implemented Voronyj diagrams for Roassal. You can read about it here:
> http://natalia.tymchuk.me/RTVoronyjDiagram/ .
> I will be on vacation from Monday till Thursday, but it will be really cool
> if you can write me your opinion about this project and all your remarks.
>
> Best regards,
> Natalia
> _______________________________________________
> Moose-dev mailing list
> [hidden email]
> https://www.iam.unibe.ch/mailman/listinfo/moose-dev
>
>
>


--
Damien Pollet
type less, do more [ | ] http://people.untyped.org/damien.pollet

Poisson + Voronyj.png (176K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Natalia Tymchuk
Hello.
Yes, it is quite slow.  I used Delaunay triangulation to build the diagram, I’m not sure that it has the smallest complexity, but it is the simples one for me.
>  I've seen
> the code copies collections a lot, that might be it…
It is the reason, however I wanted not only draw the diagram as a lot of segments, but to build the polygons and for that I need all that collections.
Maybe I will change the algorithm, that builds the diagrams.
Thanks for your attention and comments)

Best regards,
Natalia


On Aug 26, 2014, at 3:38 AM, Damien Pollet <[hidden email]> wrote:

> Hi Natalia,
>
> I've been playing with it today, and look at the pretty pixels it makes :D
> The points are generated by the poisson disc sampling algorithm
> described at http://bost.ocks.org/mike/algorithms/
>
> However, see the result of the doit, in red… the time grows really
> quick with the number of nodes, which makes it impractical with large
> point sets (the 2 smaller sets are instant, the 3rd one quickly pops
> the progress bar, and the 4th takes a couple minutes). Wikipedia says
> the complexity should be around N log N, so that's strange ; I've seen
> the code copies collections a lot, that might be it… but it's too late
> for coding now :|
>
> On 25 July 2014 19:12, Natalia Tymchuk <[hidden email]> wrote:
>> Thank you.
>> Yes, I will.
>>
>> Natalia
>>
>> On Jul 25, 2014, at 5:36 PM, Alexandre Bergel <[hidden email]>
>> wrote:
>>
>> Impressive!!!!
>>
>> Natalia, will you be at esug?
>>
>> Alexandre
>> --
>> _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
>> Alexandre Bergel  http://www.bergel.eu
>> ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
>>
>>
>>
>> On Jul 25, 2014, at 8:10 AM, Natalia Tymchuk <[hidden email]>
>> wrote:
>>
>> Hello.
>>
>> I implemented Voronyj diagrams for Roassal. You can read about it here:
>> http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>> I will be on vacation from Monday till Thursday, but it will be really cool
>> if you can write me your opinion about this project and all your remarks.
>>
>> Best regards,
>> Natalia
>> _______________________________________________
>> Moose-dev mailing list
>> [hidden email]
>> https://www.iam.unibe.ch/mailman/listinfo/moose-dev
>>
>>
>>
>
>
>
> --
> Damien Pollet
> type less, do more [ | ] http://people.untyped.org/damien.pollet
> <Poisson + Voronyj.png>_______________________________________________
> Moose-dev mailing list
> [hidden email]
> https://www.iam.unibe.ch/mailman/listinfo/moose-dev


Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Damien Pollet
On 26 August 2014 09:29, Natalia Tymchuk <[hidden email]> wrote:
> It is the reason, however I wanted not only draw the diagram as a lot of segments, but to build the polygons and for that I need all that collections.

It's not a matter of having many collections, but of repeatedly making
copies in nested loops. For instance, in uniqueTriCombiDo: using
allButFirst: followed by withIndexDo: can be replaced by to:do:

However, I guess the biggest gain would be in avoiding to enumerate
potential triangles over the whole point set, since that's
combinatorial; for instance
http://en.wikipedia.org/wiki/Fortune%27s_algorithm

--
Damien Pollet
type less, do more [ | ] http://people.untyped.org/damien.pollet

Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Emilio Oca-3
Hi Natalia,

I think Damien is right, you should consider Fortune algorithm (http://en.wikipedia.org/wiki/Fortune%27s_algorithm)
As seen in this image
http://upload.wikimedia.org/wikipedia/commons/0/0c/Fortunes-algorithm-slowed.gif
when the sweep line advances, it generates different events that allows you build auxiliary structures like the polygons you need.
Usually you are able to end the Voronyj construction and all the related structures in n log n, with n the number of sites.

Best

Emilio


> -----Mensaje original-----
> De: Pharo-dev [mailto:[hidden email]] En nombre de
> Damien Pollet
> Enviado el: Martes, 26 de Agosto de 2014 07:03
> Para: Pharo Development List
> CC: Moose-related development
> Asunto: Re: [Pharo-dev] [Moose-dev] [ANN] Voronyj Diagram
>
> On 26 August 2014 09:29, Natalia Tymchuk <[hidden email]>
> wrote:
> > It is the reason, however I wanted not only draw the diagram as a lot
> of segments, but to build the polygons and for that I need all that
> collections.
>
> It's not a matter of having many collections, but of repeatedly making
> copies in nested loops. For instance, in uniqueTriCombiDo: using
> allButFirst: followed by withIndexDo: can be replaced by to:do:
>
> However, I guess the biggest gain would be in avoiding to enumerate
> potential triangles over the whole point set, since that's
> combinatorial; for instance
> http://en.wikipedia.org/wiki/Fortune%27s_algorithm
>
> --
> Damien Pollet
> type less, do more [ | ] http://people.untyped.org/damien.pollet


Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

abergel
In reply to this post by Damien Pollet
Hi Damien,

Can you share what is necessary to reproduce the pictures you’ve sent ? (e.g., PoissonDiscDistribution class)

Alexandre

On Aug 25, 2014, at 9:38 PM, Damien Pollet <[hidden email]> wrote:

> Hi Natalia,
>
> I've been playing with it today, and look at the pretty pixels it makes :D
> The points are generated by the poisson disc sampling algorithm
> described at http://bost.ocks.org/mike/algorithms/
>
> However, see the result of the doit, in red… the time grows really
> quick with the number of nodes, which makes it impractical with large
> point sets (the 2 smaller sets are instant, the 3rd one quickly pops
> the progress bar, and the 4th takes a couple minutes). Wikipedia says
> the complexity should be around N log N, so that's strange ; I've seen
> the code copies collections a lot, that might be it… but it's too late
> for coding now :|
>
> On 25 July 2014 19:12, Natalia Tymchuk <[hidden email]> wrote:
>> Thank you.
>> Yes, I will.
>>
>> Natalia
>>
>> On Jul 25, 2014, at 5:36 PM, Alexandre Bergel <[hidden email]>
>> wrote:
>>
>> Impressive!!!!
>>
>> Natalia, will you be at esug?
>>
>> Alexandre
>> --
>> _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
>> Alexandre Bergel  http://www.bergel.eu
>> ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
>>
>>
>>
>> On Jul 25, 2014, at 8:10 AM, Natalia Tymchuk <[hidden email]>
>> wrote:
>>
>> Hello.
>>
>> I implemented Voronyj diagrams for Roassal. You can read about it here:
>> http://natalia.tymchuk.me/RTVoronyjDiagram/ .
>> I will be on vacation from Monday till Thursday, but it will be really cool
>> if you can write me your opinion about this project and all your remarks.
>>
>> Best regards,
>> Natalia
>> _______________________________________________
>> Moose-dev mailing list
>> [hidden email]
>> https://www.iam.unibe.ch/mailman/listinfo/moose-dev
>>
>>
>>
>
>
>
> --
> Damien Pollet
> type less, do more [ | ] http://people.untyped.org/damien.pollet
> <Poisson + Voronyj.png>

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.




Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

Damien Pollet
On 26 August 2014 15:23, Alexandre Bergel <[hidden email]> wrote:
> Can you share what is necessary to reproduce the pictures you’ve sent ? (e.g., PoissonDiscDistribution class)

sure:

Gofer new
smalltalkhubUser: 'cdlm' project: 'Flatland';
package: 'PoissonDiscSampler';
load

--
Damien Pollet
type less, do more [ | ] http://people.untyped.org/damien.pollet

Reply | Threaded
Open this post in threaded view
|

Re: [Moose-dev] [ANN] Voronyj Diagram

abergel
Thanks Damien!

I am currently travelling. I will have a closer look at your fix next week.
Thanks for your work!

Cheers,
Alexandre


On Aug 26, 2014, at 9:38 AM, Damien Pollet <[hidden email]> wrote:

> …speaking of code changes, here's a small fix
>
> On 26 August 2014 15:41, Damien Pollet <[hidden email]> wrote:
>> On 26 August 2014 15:23, Alexandre Bergel <[hidden email]> wrote:
>>> Can you share what is necessary to reproduce the pictures you’ve sent ? (e.g., PoissonDiscDistribution class)
>>
>> sure:
>>
>> Gofer new
>> smalltalkhubUser: 'cdlm' project: 'Flatland';
>> package: 'PoissonDiscSampler';
>> load
>>
>> --
>> Damien Pollet
>> type less, do more [ | ] http://people.untyped.org/damien.pollet
>
>
>
> --
> Damien Pollet
> type less, do more [ | ] http://people.untyped.org/damien.pollet
> <Roassal2-DamienPollet.449.mcz>

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.