BUG: Do not correct orientation of triangles returned by Qhull #4444
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
tacaswell
added a commit
that referenced
this pull request
May 21, 2015
…tion FIX: Do not correct orientation of triangles returned by Qhull
|
@ianthomas23 Thanks! |
|
@ianthomas23 this makes sense, thank you for the fix! |
|
Actually in 1.5.0 via 178d453. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single
311E
commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Fix for issue #4437.
Up until now whenever you create an mpl
Triangulationthe code checks that all triangles have vertices ordered in an anticlockwise manner; if they are ordered clockwise it flips them so they are anticlockwise. This is unnecessary for a triangulation returned by Qhull as the triangles are already correctly oriented. The OP's example shows that not only is it unnecessary, but in some cases it is erroneous to do so.Qhull can return nearly flat triangles if there are nearly colinear points. This is usual in computational geometry problems with finite machine precision. You can't really check the orientation of the vertices for a nearly flat triangle as it essentially comes down to calculating the area which can be +0.0 or indeed -0.0 for a flat triangle. If Qhull correctly gives us a correctly-oriented flat triangle but we measure the area to be -0.0, we flipped the triangle making the whole triangulation invalid.
This PR stops the orientation check for triangles returned by Qhull, and adds a test based on the OP's example. It will also need to go in master, but it cannot be cherry-picked as CXX has been removed in master so I will write a new PR for that.