[voronoi] pps() is treating site3 as an infinite line

[eadf]

This voronoi example:

0
3
-5138 -5149 -5038 -5142
-5042 -5069 -5165 -5162
-5011 -5195 -5404 -5134

Will get this result from 1.76.0:

The problem is that pps() is treating segments as a lines of infinite length.

Here is an illustration of the problem: site1 and site2 are the black and blue dots. site3 is the green line. site3.point0 is the dark green dot. pps() will find the red circle event, and that would have been correct if site3 were just a little bit longer. pps() assumes that site3 tangents the CE it is looking for, but that's not always the case. The correct circle event, the one passing through site1, site2 and site3 is the cyan colored circle.

My proposed solution to this problem is to take the CE pps() finds and project the (site3.point0 -> CE) vector upon the (site3.point0->site3.point1) vector. If the length of the projection is larger (or negative) than the site3 vector, the real CE is re-calculated using ppp().

The 'cost' of this fix is an additional calculation of a dot product for every call to pps() + the rare occasion when ppp() actually needs to be called.

To be able to call ppp() with either site3.point0or site3.point1 I had to change the method signature of ppp() to accept points instead of sites.

Here are more examples of the problem. (this PR fixes 'em all)

0
3
-5205 -5210 -5095 -5152
-5166 -5197 -5099 -5209
-5029 -5002 -5500 -5319

0
3
759 -242 631 128
189 -303 843 693
-911 -920 921 853

0
3
580 -833 552 -566
-671 955 604 -936
535 -110 412 -549

0
3
963 -74 -944 707
694 281 853 211
326 220 803 441

0
3
415 -54 955 703
976 38 -916 -467
909 424 962 401

0
3
365 113 741 366
768 -67 601 187
-814 662 817 -285

[asydorchuk]

Hi, I will start looking into this and probably will get back with some questions. Thanks for the PR!

[eadf]

The same problem exists for pss() but it's much more involved, lots of edge cases that I have not figured out yet. #67

[eadf]

I've changed the PR so that pps() does not delegate to ppp() anymore. That solution had a potential of reporting false circle events because ppp() simply does not have the required information to prevent a CE from intersecting the segment. (only tangent points are allowed, or intersection at end points) With this fix, the CE is reported as "not found" if it does not reach any valid point of the segment. (Just like circle_existence_predicate_.pps() does)

In addition to the test-cases listed above, this solution also fixes:

0
3
519 -635 342 -158
-440 707 661 -976
269 -113 507 -171

(this is one of the test cases I thought should be fixed by a future pss() fix #67)

By comparing identical circle events by their age, the pss() cases and more cases could be fixed as well:

0
3
673 903 -985 -362
-238 248 -179 453
-136 323 -90 419

0
3
597 -23 533 65
716 302 455 245
-716 412 999 356

0
3
570 8 245 194
838 785 8 157
-965 -572 934 858

0
3
310 407 365 177
754 177 -893 79
300 558 109 347

0
3
503 -633 600 -981
664 -702 688 -800
-658 584 880 -850

0
3
180 217 436 -48
561 725 -777 -922
-120 -155 443 558

0
3
-649 -607 956 199
153 3 13 -252
89 -186 293 -40

But it turns out that cases like this, that works w/o the identical-CE-age-ordering, will break:

0
3
523 224 465 223
-852 -312 853 292
277 267 369 449

0
3
-467 -299 603 -254
970 -188 -774 -316
238 -271 377 -590

0
3
836 737 -603 -397
207 253 585 581
61 177 286 550

At least we got a lead on what's causing the problems: the ordering of coordinate-identical circle events.

[ghost]

Thanks @eadf ! What happens if we return false for a circle event that we should have been able to calculate? That can lead to missing voronoi vertices right?

[eadf]

What happens if we return false for a circle event that we should have been able to calculate? That can lead to missing voronoi vertices right?

Yes. I tried the same fix for pss() and it frequently fails on previously good solutions. Probably because of that issue.

The best thing would be if sss(), pss() and pps() always returned valid solutions (or nothing)