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:[email protected]] 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 <[email protected]> > 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
