JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Geometry Concepts bug within the tutorial - Geometry Concepts: Line Intersection and its Applications
 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
 Forums Tutorial Discussions Geometry Concepts bug within the tutorial - Geometry Concepts: Line Intersection and its Applications Previous Thread  |  Next Thread