Degenerate case in convex hull code will never be hit

Discuss any Chipmunk bugs here.
Post Reply
josephg
Posts: 29
Joined: Sat Dec 24, 2011 4:54 am
Contact:

Degenerate case in convex hull code will never be hit

Post by josephg »

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.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

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

Post by slembcke »

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: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

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

Post by slembcke »

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/
josephg
Posts: 29
Joined: Sat Dec 24, 2011 4:54 am
Contact:

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

Post by josephg »

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
Post Reply

Who is online

Users browsing this forum: No registered users and 4 guests