Skip to content

Half-plane intersection #1332

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

Open
mzuenni opened this issue Sep 11, 2024 · 2 comments
Open

Half-plane intersection #1332

mzuenni opened this issue Sep 11, 2024 · 2 comments
Labels

Comments

@mzuenni
Copy link

mzuenni commented Sep 11, 2024

The code in the article seems to yield the wrong result for some tiny inputs, for example:

3       
5 5 -8 -8
-1 -9 10 -8
10 5 4 8

The intersection should be bounded:

-9.8 9.8
-6 -32
6.666666667 -6.666666667

The problem is likely the large bounding box.

@Harsh-Mathur-1503
Copy link
Contributor

Probably, the problem is that the bounding box becomes (inf) or how small floating point errors will partially add up when calculating the intersection. To iterate improvements of this algorithm, inf could then be redefined to treat smaller inputs with finesse and then to calibrate the value of epsilon (eps) to be less strict about minor floating-point deviation. Some ways you could improve the precision are:

  1. Refine the Bounding Box:
    Instead of inf fixed large bounding box, you may consider that the bounding box is computed on ranges of input points and it is an adjustment dynamically on data.

  2. Tolerance for Precision (eps) :
    For epsilon, it has been set at 1e-9. In some instances this value might be too small, especially when there is the need to address floating-point imprecision. You may try increasing this a bit, handle precision without losing some precision.

  3. Small Inputs and Edge Cases
    Deal with the inputs that have negative coordinates or very small values explicitly, make sure you check for edge cases when your coordinate is close to zero.

@Harsh-Mathur-1503
Copy link
Contributor

@adamant-pwn kindly see the pr #1367

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

No branches or pull requests

3 participants