JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
bug within the tutorial - Geometry Concepts: Line Intersection and its Applications | Reply
I think there is a bug in the code:
convexHull(point[] X, boolean onEdge)

when i test it with the arguments:
convexHull(true,{1,1},{2,2},{3,3},{4,4},{4,2},{5,2},{5,1});

it end up with the wrong results
Re: bug within the tutorial - Geometry Concepts: Line Intersection and its Applications (response to post by hotou) | Reply
I think this is because the author has put in a bit of a fudge to deal with the starting vertex. To avoid processing vertices that are behind the current one in the path, he marks them as visited. However, to allow the path to close, he doesn't mark the starting vertex as visited. This leads to a problem when the starting vertex is a part of a string of colinear vertices, because the cross products in that case will be zero, so when processing the second vertex in the path, it sees the starting vertex as a valid target, with a cross product of zero with the actual next vertex and a distance that is no greater than the actual next vertex. It processes the starting vertex first (since it has index 0), so the vertex it should be visiting next then gets ignored.

If you change the line:
if(onEdge && d < dist){

to
if(onEdge && (d < dist || n == start)){

I think it should solve the problem
RSS