Bug in GrahamScan

[mtsamis]

(Continuing with the hull algorithm testing) I found one case where the GrahamScan produces a wrong hull. I open the issue to keep track of the bug.

var test = new Vector2[] {
				new Vector2(23, 1.0),
				new Vector2(57, 1.0),
				new Vector2(13, 1.0),
				new Vector2(27, 10.0)};

System.out.println(List.of(new GrahamScan().generate(test)));

which prints [(23.0, 1.0), (27.0, 10.0)]

[wnbittle]

Thanks for the reproduction case. I'm making decent progress on the others so I'll take a look at this one as well.

[mtsamis]

I'm developing an automated test for all the hull algorithms that tries to randomly cover a lot of cases. While doing so I found more bugs in DivideAndConquer, this time not an infinite loop, but some input that gives wrong hull. I'm not opening a new issue because there is a bit of spam around hull algorithms already; also it's possible that those will be fixed with your changes.

So when you finish with changes in the hull algorithms I can help test them with this randomized test; so far it found all of the existing bugs, so it covers a lot of cases. If you want the input that triggers the DivideAndConquer bug as well you can tell me.

[wnbittle]

I've been updating those same tests as well. Depending on the number of failure cases, feel free to report them here and I'll get them added. I've nearly worked through all the issues with GiftWrap, GrahamScan and DivideAndConquer but have some finishing touches. Every test case that's been reported to any of these issues, I've been testing on the other algorithms. I've found a few additional issues - probably some of the ones you are seeing as well. Up to this point I haven't found a test case that breaks MonotoneChain (at least one works...).

I do want to be cautious with #80, #76 and #73 in the sense that fixing them shouldn't imply that the resulting hulls would work with the core dyn4j engine without issue. A good example is your 4th failure case in #76 . I would not recommend that polygon be used in dyn4j.

I'll be updating the javadoc as well to reflect the expected output of each and any caveats that I've run into.

[mtsamis]

I actually have a general randomized tester, so I can generate them on demand. I'm checking if it could be included as a unit test as well, similar to the broadphase randomized test, which helped find some new bugs.

Here's one bug that is not reported on other issues, for DivideAndConquer
(you can check if it's fixed with you changes)

Counter example for DivideAndConquer
for point cloud: new Vector2[] {
new Vector2(-7.725662343635252, 3.239314248048395), 
new Vector2(-7.725662343635252, 9.244107520658332), 
new Vector2(-7.725662343635252, 5.6066430781506575), 
new Vector2(-5.985432177897989, 1.0634285355681339), 
new Vector2(2.7404621676247265, -4.946792659796997), 
};

Result is: new Vector2[] {
new Vector2(-7.725662343635252, 5.6066430781506575), 
new Vector2(-5.985432177897989, 1.0634285355681339), 
new Vector2(2.7404621676247265, -4.946792659796997), 
};

At least one missing point:
(-7.725662343635252, 9.244107520658332)

About the polygon with the extreme floating point values; yeah it makes little sense to use it in a simulation, but the algorithm should be general enough for outside use as well. Those where some initial lower-quality generated tests though. The new tester is using sane values.

[wnbittle]

Thanks for the additional test case. Added it as test to all hull generator tests - my fixes are working for this one as well.

About the polygon with the extreme floating point values; yeah it makes little sense to use it in a simulation, but the algorithm should be general enough for outside use as well.

Cool - I think we're on the same page then - I'll be adding some javadoc to that effect.

[wnbittle]

Fixed in commit 1134b73