### Author Topic: Collinearity in convex hull algorithm  (Read 4385 times)

0 Members and 1 Guest are viewing this topic.

#### kaefer

• Guest
##### Collinearity in convex hull algorithm
« on: April 14, 2011, 09:14:49 PM »
First, many thanks for gile's concise F# implementation of the Graham scan algorithm. I had to make do with Carsten König's variant before, which is a little more verbose.

Put to use by throwing it together with Kean's 2D point gathering, I had to notice slight damage to my sport car's left front wheel (see picture).

My suspicion falls on the clockwise function, replacing it with Bryco's isLeftMath method brings better results. What gives? Looks like the case that 3 points lie in a row needs to be handled explicitly.
« Last Edit: April 14, 2011, 09:25:32 PM by kaefer »

#### Kerry

• Mesozoic relic
• Seagull
• Posts: 11654
• class keyThumper<T>:ILazy<T>
##### Re: Collinearity in convex hull algorithm
« Reply #1 on: April 14, 2011, 09:24:51 PM »

looks like the roof above the rear window is also a little 'dented'
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

#### kaefer

• Guest
##### Re: Collinearity in convex hull algorithm
« Reply #2 on: April 15, 2011, 02:54:45 AM »
looks like the roof above the rear window is also a little 'dented'

That's right, too.

How embarassing, inadequate testing led to completely wrong diagnosis. I should've checked the less complex procedure first: Generate the points, save them as DBPoints into the Database, and all's well with gile's Convex Hull.

#### gile

• Water Moccasin
• Posts: 2493
• Marseille, France
##### Re: Collinearity in convex hull algorithm
« Reply #3 on: April 15, 2011, 06:07:35 AM »
Hi,

Thanks for reporting.

After reading this post I looked deeper in the code I posted and noticed some problem with colinear points at 0° from the pivot point (eg. with a rectugular arry of points), so I modify the sorting lambda function in the code here.
It seems to work fine now: all colinear points are removed.
Speaking English as a French Frog

#### gile

• Water Moccasin
• Posts: 2493
• Marseille, France
##### Re: Collinearity in convex hull algorithm
« Reply #4 on: April 16, 2011, 11:13:51 AM »
Hi,

I think I finally solve the problem with colinear points by using a tolerance in the cosines comparison while sorting the point list.
New code here.
« Last Edit: April 16, 2011, 11:24:39 AM by gile »
Speaking English as a French Frog