Convex hulls

Lex Spoon lex at cc.gatech.edu
Sun Sep 6 07:21:42 UTC 1998


Here's some quick code for the upper part of the convex hull.  It's
easy to modify for computing the lower hull in parallel and then
pasting the two together, but I'm resisting the urge to put all that
in because it just obscures the algorithm.

The basic scheme used here is: add the points from left to right, and
fix up the hull as you go.  The "fixing up" consists solely of
removing points just to the left of the point you are adding.

Overall, this kind of algorithm seems very well suited to
experimentation in Squeak:


   1) It takes good advantage of Collections.  Check out the casual
   four-line sort operation near the beginning, and consider how many
   lines it would take to use C's qsort().

   2) Mathetically, it only requires Points and numbers, which Squeak
   already has built in.  If you need really fancy math stuff, you
   should probably go with something like Mathematica.

   3) Morphic is a fine way to build little diagrams of what you are
   doing.  You can even go back and manipulate the diagrams by hand
   when you're done.

   4) Due to untyped variables, the code doesn't have to commit to
   what type, for instance, the "numbers" are.  This both makes it
   easier to write the code (floats or ints?  who cares?), and it
   helps avoid making too many early constraints (oops, changed my
   mind, now I want fractions).


Incidentally, this algorithm is O(n log n); there is at least one
O(n) algorithm, but the only one I've seen is a bit more complex than
this one here.

-Lex


======================================================================
'From Squeak 2.1 of June 30, 1998 on 6 September 1998 at 6:33:45 am'!

!Collection methodsFor: 'geometry' stamp: 'ls 9/6/1998 06:33'!
upperHull
	"compute the upper convex hull of a set of points"
	| hull sortedPoints |

	hull := OrderedCollection new.

	"sort the points from left to right"
	sortedPoints := self asSortedCollection: [ :point0 :point1 |
		point0 x = point1 x
			ifTrue: [ point0 y < point1 y ]
			ifFalse: [ point0 x < point1 x ] ].


	"add the points one by one"
	sortedPoints do: [ :point |
		"remove all points that would cause a concave angle"
		[hull size >= 2 and: [
			(hull at: hull size)
				isOnOrBelowLineThrough: (hull at: hull size - 1)
				and: point ] ]
		whileTrue: [ hull removeLast ].
		hull add: point ].

	^hull! !


!Point methodsFor: 'geometry' stamp: 'ls 9/6/1998 06:33'!
isOnOrBelowLineThrough: p0  and: p1
	"whether this point is on or below the line through p0 and p1"
	"equivalently, do the vectors (p0-->self) and (self-->p1) make a left turn?"
	| v1 v2 crossZ |

	v1 _ self - p0.
	v2 _ p1 - self.
	crossZ _ (v1 x * v2 y) - (v1 y * v2 x).

	^crossZ >= 0! !

====================  demo code ===========================================


"generate some test points"
points _ (1 to: 100) collect: [ :i | (100 atRandom) @ (100 atRandom) ].

"generate the upper hull"
hull _ points upperHull. 



"stuff all the drawing into a RectangleMorph, for easy cleanup"

board _ RectangleMorph new.
board extent: 100 at 100.    "adjust to fit, but leave it in the top left 
                           corner of the screen"
board openInWorld.


"draw the points"

points do: [ :point |
	m _ EllipseMorph new.
	m bounds: (point - (2 at 2) extent: 4 at 4).
	board addMorph: m ].


"draw the outline of the hull"
board addMorph: ((PolygonMorph vertices: hull  color: Color transparent  
	borderWidth: 1  borderColor: Color blue) makeOpen)

=============================================================================



ocit.inc writes:
 > The convex hull of a set of points is the smallest convex set that contains
 > the points.
 > 
 > What I meant by "convex hull algorithm" was  the algorithm that determined
 > the convex polygon given the above definition.
 > 
 > There is a lot of material and source code out there mainly in C . There are
 > also some Java applets. Somebody in this discussion group had distributed
 > code for Voronoi diagrams and I thought that perhaps the same person might
 > have something in Squeak for convex hulls.
 > 
 > Charles
 > OCIT
 > -----Original Message-----
 > From: Alessandro Manunza <manunza at elettro1.unica.it>
 > To: squeak at cs.uiuc.edu <squeak at cs.uiuc.edu>
 > Date: Friday, September 04, 1998 3:29 AM
 > Subject: R: Convex hulls
 > 
 > 
 > Hi,
 > excuse me, what is a "convex hull algorithm "?
 > 
 > Thanks
 > 
 > Alessandro
 > 
 > ----------
 > > Da: ocit.inc <ocit.inc at MCI2000.com>
 > > A: squeak at cs.uiuc.edu
 > > Oggetto: Convex hulls
 > > Data: venerdì 4 settembre 1998 6.56
 > >
 > > I am on the verge of attempting to implement an ST version of a convex
 > hull
 > > algorithm however I'm kind of busy at the moment and would prefer to
 > borrow
 > > one.
 > >
 > > Can anybody help?
 > >
 > > Thanks.
 > >
 > > Charles
 > >
 > >
 > 
 > 





More information about the Squeak-dev mailing list