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

A possible weak spot in the implementation #153

Open
dbuenzli opened this issue Jul 29, 2022 · 1 comment
Open

A possible weak spot in the implementation #153

dbuenzli opened this issue Jul 29, 2022 · 1 comment

Comments

@dbuenzli
Copy link

I made my own implementation of the algorithm in another language (not yet published, but it will be at some point) and I read both your version and the reference implementation.

While reading them I thought that this collinearity test was likely not very robust; testing exactly for 0. in these cases rarely is.

I had a use case that was returning bogus results, e.g. here for union:

Screenshot 2022-07-29 at 17 54 30

I replaced the test by a more robust one derived from my line intersection test (basically see yours, when you reach that point, you have collinear segments; it seems you use a modified version of Eberly, I followed it to the letter). That solved my problem in this case:

Screenshot 2022-07-29 at 18 03 20

In case you are interested in testing this here is the list of points for the two contours (in floating point hex notation, to make sure you get exactly the same values):

let cell4 =
[[0x1.097c21704da94p+7, 0x1.949084e37324bp+7;
  0x1.0a2281672d93bp+7, 0x1.9343c4d244eb7p+7;
  0x1.0a2281672d93bp+7, 0x1.91f704c116b22p+7;
  0x1.0a2281672d93bp+7, 0x1.90aa44afe878ep+7;
  0x1.0b6f4154ed68bp+7, 0x1.9003e4a7515c4p+7;
  0x1.0cbc0142ad3dap+7, 0x1.9003e4a7515c4p+7;
  0x1.0d6261398d282p+7, 0x1.8f5d849eba3f9p+7;
  0x1.0eaf21274cfd1p+7, 0x1.8eb724962322fp+7;
  0x1.0eaf21274cfd1p+7, 0x1.8d6a6484f4e9bp+7;
  0x1.0f55811e2ce79p+7, 0x1.8c1da473c6b06p+7;
  0x1.1148a102cca7p+7, 0x1.87910437a4e7ep+7;
  0x1.11ef00f9ac917p+7, 0x1.8644442676aeap+7;
  0x1.13e220de4c50fp+7, 0x1.8451240cb158bp+7;
  0x1.148880d52c3b6p+7, 0x1.83aac4041a3c1p+7;
  0x1.152ee0cc0c25ep+7, 0x1.7fc483d08f903p+7;
  0x1.152ee0cc0c25ep+7, 0x1.7e77c3bf6156fp+7;
  0x1.15d540c2ec106p+7, 0x1.7d2b03ae331dap+7;
  0x1.167ba0b9cbfadp+7, 0x1.7c84a3a59c01p+7;
  0x1.17c860a78bcfdp+7, 0x1.7bde439d04e46p+7;
  0x1.191520954ba4cp+7, 0x1.79eb23833f8e7p+7;
  0x1.19bb808c2b8f4p+7, 0x1.789e637211553p+7;
  0x1.1a61e0830b79bp+7, 0x1.7751a360e31bep+7;
  0x1.1b084079eb643p+7, 0x1.7604e34fb4e2ap+7;
  0x1.1b084079eb643p+7, 0x1.736b632d58701p+7;
  0x1.1b084079eb643p+7, 0x1.721ea31c2a36cp+7;
  0x1.1baea070cb4ebp+7, 0x1.71784313931a2p+7;
  0x1.1cfb605e8b23ap+7, 0x1.70d1e30afbfd8p+7;
  0x1.1eee80432ae31p+7, 0x1.6d9202e0086e5p+7;
  0x1.1eee80432ae31p+7, 0x1.6c4542ceda35p+7;
  0x1.1da1c0556b0e2p+7, 0x1.6b9ee2c643186p+7;
  0x1.1baea070cb4ebp+7, 0x1.6ceba2d77151ap+7;
  0x1.1b084079eb643p+7, 0x1.6e3862e89f8afp+7;
  0x1.167ba0b9cbfadp+7, 0x1.70d1e30afbfd8p+7;
  0x1.152ee0cc0c25ep+7, 0x1.70d1e30afbfd8p+7;
  0x1.148880d52c3b6p+7, 0x1.721ea31c2a36cp+7;
  0x1.133bc0e76c667p+7, 0x1.72c50324c1537p+7;
  0x1.10a2410becbc8p+7, 0x1.72c50324c1537p+7;
  0x1.0f55811e2ce79p+7, 0x1.736b632d58701p+7;
  0x1.0cbc0142ad3dap+7, 0x1.7604e34fb4e2ap+7;
  0x1.0c15a14bcd532p+7, 0x1.7751a360e31bep+7;
  0x1.063c419dee14dp+7, 0x1.79eb23833f8e7p+7;
  0x1.04ef81b02e3fep+7, 0x1.79eb23833f8e7p+7;
  0x1.044921b94e556p+7, 0x1.7b37e3946dc7cp+7;
  0x1.02fc61cb8e807p+7, 0x1.7b37e3946dc7cp+7;
  0x1.01afa1ddceab7p+7, 0x1.7bde439d04e46p+7;
  0x1.fcdf8416de2e2p+6, 0x1.7dd163b6ca3a5p+7;
  0x1.fa46043b5e843p+6, 0x1.7e77c3bf6156fp+7;
  0x1.f8f9444d9eaf4p+6, 0x1.7fc483d08f903p+7;
  0x1.f7ac845fdeda4p+6, 0x1.806ae3d926acep+7;
  0x1.ee9344dfa0079p+6, 0x1.830463fb831f7p+7;
  0x1.ebf9c504205dap+6, 0x1.83aac4041a3c1p+7;
  0x1.e813853ae0decp+6, 0x1.86eaa42f0dcb4p+7;
  0x1.e57a055f6134dp+6, 0x1.87910437a4e7ep+7;
  0x1.e57a055f6134dp+6, 0x1.88ddc448d3213p+7;
  0x1.e04705a861e1p+6, 0x1.8d6a6484f4e9bp+7;
  0x1.e04705a861e1p+6, 0x1.8eb724962322fp+7;
  0x1.dc60c5df22622p+6, 0x1.90aa44afe878ep+7;
  0x1.db1405f1628d2p+6, 0x1.9150a4b87f958p+7;
  0x1.dc60c5df22622p+6, 0x1.929d64c9adcedp+7;
  0x1.e42d4571a15fep+6, 0x1.9343c4d244eb7p+7;
  0x1.e6c6c54d2109cp+6, 0x1.93ea24dadc081p+7;
  0x1.ebf9c504205dap+6, 0x1.93ea24dadc081p+7;
  0x1.ee9344dfa0079p+6, 0x1.93ea24dadc081p+7;
  0x1.efe004cd5fdc8p+6, 0x1.9343c4d244eb7p+7;
  0x1.f27984a8df867p+6, 0x1.929d64c9adcedp+7;
  0x1.f7ac845fdeda4p+6, 0x1.929d64c9adcedp+7;
  0x1.fa46043b5e843p+6, 0x1.929d64c9adcedp+7;
  0x1.fcdf8416de2e2p+6, 0x1.929d64c9adcedp+7;
  0x1.ff7903f25dd81p+6, 0x1.9343c4d244eb7p+7;
  0x1.025601d4ae95fp+7, 0x1.9343c4d244eb7p+7;
  0x1.03a2c1c26e6aep+7, 0x1.9343c4d244eb7p+7;
  0x1.04ef81b02e3fep+7, 0x1.93ea24dadc081p+7;
  0x1.082f61828dd44p+7, 0x1.949084e37324bp+7]]
let cell5 =
[[0x1.02fc61cb8e807p+7, 0x1.9c5d054a887c6p+7;
  0x1.0595e1a70e2a5p+7, 0x1.99c385282c09dp+7;
  0x1.06e2a194cdff5p+7, 0x1.991d251f94ed3p+7;
  0x1.0789018bade9cp+7, 0x1.9683a4fd387aap+7;
  0x1.082f61828dd44p+7, 0x1.9536e4ec0a416p+7;
  0x1.082f61828dd44p+7, 0x1.93ea24dadc081p+7;
  0x1.0789018bade9cp+7, 0x1.9343c4d244eb7p+7;
  0x1.06e2a194cdff5p+7, 0x1.91f704c116b22p+7;
  0x1.0595e1a70e2a5p+7, 0x1.9150a4b87f958p+7;
  0x1.044921b94e556p+7, 0x1.90aa44afe878ep+7;
  0x1.01afa1ddceab7p+7, 0x1.90aa44afe878ep+7;
  0x1.0062e1f00ed68p+7, 0x1.90aa44afe878ep+7;
  0x1.ff7903f25dd81p+6, 0x1.9150a4b87f958p+7;
  0x1.f7ac845fdeda4p+6, 0x1.91f704c116b22p+7;
  0x1.f51304845f306p+6, 0x1.91f704c116b22p+7;
  0x1.efe004cd5fdc8p+6, 0x1.9343c4d244eb7p+7;
  0x1.ee9344dfa0079p+6, 0x1.93ea24dadc081p+7;
  0x1.ed4684f1e0329p+6, 0x1.9536e4ec0a416p+7;
  0x1.ed4684f1e0329p+6, 0x1.9683a4fd387aap+7;
  0x1.ee9344dfa0079p+6, 0x1.97d0650e66b3fp+7;
  0x1.efe004cd5fdc8p+6, 0x1.991d251f94ed3p+7;
  0x1.f3c644969f5b6p+6, 0x1.9a69e530c3268p+7;
  0x1.f51304845f306p+6, 0x1.9bb6a541f15fcp+7;
  0x1.f7ac845fdeda4p+6, 0x1.9bb6a541f15fcp+7;
  0x1.fa46043b5e843p+6, 0x1.9c5d054a887c6p+7;
  0x1.025601d4ae95fp+7, 0x1.9c5d054a887c6p+7]]
@w8r
Copy link
Owner

w8r commented Jul 29, 2022

Thanks a lot! I looked at it recently and I don't remember why I modified it. I should bring it back

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

No branches or pull requests

2 participants