Bugzilla – Full Text Bug Listing
| Summary: | Point.getConvexHull() throws IllegalArgumentException from sort | ||||||
|---|---|---|---|---|---|---|---|
| Product: | [Tools] GEF | Reporter: | Colin Sharples <ctg> | ||||
| Component: | GEF Geometry | Assignee: | gef-inbox <gef-inbox> | ||||
| Status: | RESOLVED FIXED | QA Contact: | |||||
| Severity: | normal | ||||||
| Priority: | P3 | CC: | matthias.wienand | ||||
| Version: | unspecified | ||||||
| Target Milestone: | 3.10.0 (Mars) M3 | ||||||
| Hardware: | PC | ||||||
| OS: | Windows 8 | ||||||
| Whiteboard: | |||||||
| Attachments: |
|
||||||
Thank you very much for the data! I created a test case from it and added it to the test suite. We faced a similar issue some time ago, when the comparator did not return 0 for any given points. I think the Straight#getSignedDistanceCCW() method does not produce results precise enough to identify two points with the same angle w.r.t. the first point in all cases. That's why I added an imprecision when testing if the signed distance is 0. This fixed the issue for the given set of points. The code is published on the master branch, therefore I resolve this bug ticket as fixed. However, it could well be the case that other sets of points still lead to the exception. If you encounter more failing cases, re-open the ticket, please. That seems to have done the trick. I'll add in a catch block to dump out any points if it happens again, so I can reopen. Thanks. |
Created attachment 248141 [details] Example set of points that cause exception I am using Point.getConvexHull to get the outline of a collection of shapes. For certain combinations of shapes, the getConvexHull() method will throw an IllegalArgumentException, coming from the Arrays.sort() call. I'm running this on JDK 1.7.0_55, and it looks like this is due to the stricter interpretation of the Comparable contract used by TimSort. There are cases where Straight.getSignedDistanceCCW() will return 0 for one direction, but a very small non-zero value for the reverse direction of the same pair of points, i.e. Straight.getSignedDistanceCCW(p0, p1, p2) == 0.0 but Straight.getSignedDistanceCCW(p0, p2, p1) != 0.0. This means that the Comparator is not transitive, so the sort barfs. I tried checking the reverse direction when the distance is zero, as follows: public int compare(Point p1, Point p2) { double d = Straight.getSignedDistanceCCW(p0, p1, p2); if (d == 0) { double dr = Straight.getSignedDistanceCCW(p0, p2, p1); return dr == 0 ? 0 : dr < 0 ? 1 : -1; } return d == 0 ? 0 : d < 0 ? -1 : 1; } This produced better results, but I still found some bad cases, so I am not sure exactly what is going on.