Skip to content
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

implement degeneracies algorithm #5

Open
mischkew opened this issue Nov 16, 2015 · 3 comments
Open

implement degeneracies algorithm #5

mischkew opened this issue Nov 16, 2015 · 3 comments
Assignees

Comments

@mischkew
Copy link

see here http://arxiv.org/pdf/1211.3376v1.pdf
and here http://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf

@mischkew
Copy link
Author

degeneracies detection fails when floating point errors occur
we need thresholded comparisons

mischkew added a commit that referenced this issue Nov 20, 2015
* fixed indentation
* use thresholded comparions to avoid floating point errors #5
mischkew added a commit that referenced this issue Nov 23, 2015
mischkew added a commit that referenced this issue Nov 23, 2015
@mischkew
Copy link
Author

@dimitri-schmidt following progress tonight:

results are fine, but sometimes:

  • ccw instead of cw or the other way round
  • an arbitrary permutation of the correct solution

possible ways to solve:

  1. always test for the permutation which is the result
  2. build a permutation checker

@w8r
Copy link

w8r commented Jan 22, 2016

@mischkew, @dimitri-schmidt

Hey guys, great work! any plans to merge that back? What paper did you use? I hope it was not Overfelt.
After playing around with Greiner-Hormann for a long time I concluded that it will never be good enough for a general case. I have a great paper on my hands on another algorithm that I want to implement, which is more robust I guess and is also ready for multipolygons and holes, which is a great downside of this one - I tried to build something without cascading the operations and it didn't really work.

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

No branches or pull requests

3 participants