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

0 Members and 1 Guest are viewing this topic.

kaefer

  • Swamp Rat
  • Posts: 572
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'
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

kaefer

  • Swamp Rat
  • Posts: 572
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: 2275
  • 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: 2275
  • 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