Degenerate case in convex hull code will never be hit

Discuss any Chipmunk bugs here.

Degenerate case in convex hull code will never be hit

Postby josephg » Fri Feb 01, 2013 11:59 pm

I'm porting the new convex hull code and I came across this:

Code: Select all
void
cpLoopIndexes(cpVect *verts, int count, int *start, int *end)
{
  // ...
  for(int i=1; i<count; i++){
    // ...
    if(...){
      min = v;
      (*start) = i;
    } else if(...){
      max = v;
      (*end) = i;
    }
  }
}


... then later, in cpConvexHull:

Code: Select all
   // Degenerate case, all poins are the same.
   int start, end;
   cpLoopIndexes(verts, count, &start, &end);
   if(start == end){


I'm pretty sure that start == end case will never hit, because start and end are never both set to one of the indexes (because end is set in an else if() ...)

I should probably submit a pull request but I'm being lazy, because I'm in the middle of porting.
josephg
 
Posts: 29
Joined: Sat Dec 24, 2011 4:54 am

Re: Degenerate case in convex hull code will never be hit

Postby slembcke » Sat Feb 02, 2013 5:03 am

Not quite. I think you misunderstood the comment "Degenerate case, all poins are the same". If you have a list of points that is the same vertex 5 times (or whatever), the algorithm breaks. In that case cpLoopIndex returns 0 for both the start and end and the recursion would break (crash or loop infinitely... I forget which). They have the same value because it never enters either the if or the else-if conditional.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Degenerate case in convex hull code will never be hit

Postby slembcke » Sat Feb 02, 2013 5:17 am

Also, I apologize for the... C-ness of that code. How it heavily uses pointers and swapping and such. I was a little obsessed with finding a way to perform the qhull algorithm in place without needing to allocate extra memory. Mostly just because it sounded like more fun. It did ultimately make it shorter, but also less obvious how it actually works.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Degenerate case in convex hull code will never be hit

Postby josephg » Sat Feb 02, 2013 3:50 pm

Hehe I understand, though that certainly made it a bit of challenge to port it to JS.

I get it now - because you initialize start=end=0 at the start, and you only update them if the new value is not equal. Cool :)

In other news:
http://dl.dropbox.com/u/2494815/demo/Query.html
http://dl.dropbox.com/u/2494815/demo/Convex.html
josephg
 
Posts: 29
Joined: Sat Dec 24, 2011 4:54 am


Return to Bugs

Who is online

Users browsing this forum: No registered users and 1 guest