New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Error case in WelzlEncloser.pivotingBall #20

jerdmanGH opened this Issue Jan 20, 2017 · 2 comments


None yet
2 participants
Copy link

jerdmanGH commented Jan 20, 2017

The following code generates an internal error:

	final WelzlEncloser<Euclidean3D, Vector3D> encloser =
            new WelzlEncloser<Euclidean3D, Vector3D>(1e-14, new SphereGenerator());
	List<Vector3D> points = new ArrayList<Vector3D>();
	points.add(new Vector3D(0.9999999731, 0.000200015, 0.0001174338));
	points.add(new Vector3D(0.9987716667, 0.0350821284, 0.0349914572));
	points.add(new Vector3D(0.9987856181, -0.0346743952, 0.0349996489));
	points.add(new Vector3D(0.9987938115, -0.0346825853, -0.0347568755));
	points.add(new Vector3D(0.9987798601, 0.0350739383, -0.0347650673));
            EnclosingBall<Euclidean3D, Vector3D> enclosing3D = encloser.enclose(points);

This comment has been minimized.

Copy link

maisonobe commented Jan 22, 2017

I confirm the issue.
The problem seem to be related to numerical issues. During the enclosing ball search iterations, the radius of the balls should be non-decreasing from one iteration to the next one. However, with the points sample above, one iteration leads to a ball of radius 0.04932531217754311 and at the following iteration the radius becomes 0.049325312177543094 which is 1.6e-17 smaller. The difference is 2 ulps only.
I am looking at this.

maisonobe added a commit that referenced this issue Jan 24, 2017

Fixed issues in Welzl smallest enclosing ball computation.
Thanks to jerdmanGH for reporting the issue.
Fixes GitHub #20.

This comment has been minimized.

Copy link

maisonobe commented Jan 24, 2017

The issue has been fixed in commit 842ccd2.

Thanks for the report!

@maisonobe maisonobe closed this Jan 24, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment