Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Bug 409048

Summary:	[GEF4] Point.getConvexHull returns different results on JDK 6 and 7
Product:	[Tools] GEF	Reporter:	Fabian Steeg <steeg>
Component:	GEF Geometry	Assignee:	Matthias Wienand <matthias.wienand>
Status:	RESOLVED FIXED	QA Contact:
Severity:	normal
Priority:	P3	CC:	matthias.wienand
Version:	unspecified
Target Milestone:	---
Hardware:	PC
OS:	Mac OS X
Whiteboard:

Description Fabian Steeg

2013-05-24 19:28:05 EDT

I'm getting a test failure in the GEF4 master build with JDK 7 (u21 on Mac):

Failed tests: test_getConvexHull(PointTests)

I've split up the test_getConvexHull method to investigate (I didn't push this to eclipse.org since it's not in the Zest bundles, but of course I'd be happy to contribute it):

https://github.com/fsteeg/gef4/commit/f3ccca1

With this, it looks like getConvexHull returns one additional point on JDK 7:

test_getConvexHull3(PointTests): expected:<3> but was:<4>

Comment 1 Matthias Wienand

2013-06-06 05:31:36 EDT

The sorting algorithm used by Arrays.sort() changed from JDK 6 to 7 (and uses less compares). I do not know yet why that change affects the Point.getConvexHull() method. Obviously, the code should work with any sorting algorithm.

The code uses the Vector.getAngleCCW() method to sort the points. Later on, when the convex hull is build up, Straight.getSignedDistanceCCW() is used to test if three consecutive points form a "left turn" or a "right turn".

I think those two methods disagree in some degenerate cases (like the failing test case). If that is the case, a simple fix would be to make use of one of those methods to implement the other.

Another note: The comparator used to sort the points currently never returns 0. As the Arrays.sort() method is specified to use a stable sorting algorithm, maybe the comparator should return 0 if the arrangement of two points does not matter, so that, if the sort algorithm changes, the outcome would still be exactly the same.

Comment 2 Matthias Wienand

2013-06-14 05:22:01 EDT

I cherry-picked your commit now. Thank you for the help!

I fixed the inconsistency by exclusively using the Straight#getSignedDistanceCCW() method instead of the Vector#getAngleCCW() method.