(no subject)

Subject: [squeak-dev] Building Voronoi diagragram

> Hello,

> Would anyone have a ready-to-use implementation of Fortune's sweep line
> algorithm for generating Voronoi diagrams?

> There is a useful Voronoi package on SqueakMap, but Fortune's method is
> much faster.

> Stef

If you google computational geometry workbench you will find references
to the Computational Geometry Workbench developed at
               Carleton University,   Ottawa Canada.
It was developed in Smalltalk V in the 1980s.  A port to Smalltalk 80
was started
but never finished.  It contained many computational geometry algorithm
implementations including for Voronoi diagrams but I don't know which
ones.  So if you can dig up the workbench you might find an implementation
of Fortune's method there.

If you dig up the workbench let me know.  I would like to grab some of the
code in the workbench too (I need to be able to triangulate a polygon).
It would also be cool to see the workbench ported to Squeak.
I would be willing to help with such a port but only as a minor contributer as
I already have enough on my plate.

Ralph Boland

> If you google computational geometry workbench you will find references
> to the Computational Geometry Workbench developed at
>                 Carleton University,   Ottawa Canada.

Thanks for the pointer. I'll have a look.

> It was developed in Smalltalk V in the 1980s.

Hmm. Fortune's paper is from 1987, so it may be too early.

Best,

Stef

Hi Ralph,

in Squeak 3.6 and 3.8 there is class Subdivision with the comment:

"I perform (constraint) delauney triangulations on a set of points. See
my class side for examples."

I know I once used it I guess in 3.6 but can't find that image anymore.

Cheers,


Herbert


Am 24.01.2019 um 19:19 schrieb Ralph Boland:
>
> code in the workbench too (I need to be able to triangulate a polygon).



> It would also be cool to see the workbench ported to Squeak.
> I would be willing to help with such a port but only as a minor contributer as
> I already have enough on my plate.
>
> Ralph Boland
>

Herbert,

Thanks for finding the background on this.

The classes Subdivision, SubdivisionHalfEdge, and SubdivisionQuadEdge are
present in Squeak 3.2, but not in Squeak 2.8. Some of the methods have no
author initials, so they date back to the early days of Squeak. All of the
methods with timestamps are from 'ar' so I think that Andreas Raab wrote
the package.

I see no direct references to these classes in the 2.8 image, and my guess
would be that they were probably removed at some later point because they
were not needed in the base image.

Given that the classes were written by Andreas, I think that it is safe
to say that they will be of high quality, and that they will work with
little or no change in the latest Squeak trunk images.

The classes are in category 'Graphics-Tools-Triangulation', so if you
file that out from Squeak 3.8 and load it back in to your current Squeak
image, it will work.

I just tried this in my trunk image, and the class side examples in
Subdivision work fine, with no modifications required at all.

I am attaching the fileout from Squeak 3.8.

Good stuff, thanks for finding it :-)

Dave

On Thu, Jan 24, 2019 at 09:58:42PM +0100, Herbert K??nig wrote: