Closed Telzhaak closed 3 years ago
After some testing, the broken corner cells were already present in the master-branch.
So this PR "could" be seen as ready to merge
.
I'll try to fix the corners over the weekend
Opened new issue #4 for the corner-problem, as it is not related with any of the changes made here
@Telzhaak - thanks for the PR and reporting the issues! I started taking a look at the code and looks good. Thanks for adding the benchmark results, I was curious on that - but looks like no measurable to minimal impact.
Short update: I added a UnitTest for the BoundingBox, but noticed that one of my changes results in a previously fine Unittest to fail:
---- cell_builder::test::extend_and_close_hull_test stdout ----
thread 'cell_builder::test::extend_and_close_hull_test' panicked at 'assertion failed: `(left == right)`
left: `[32.75, -15.5]`,
right: `[7.905417527999327, -3.0777087639996634]`:
Invalid vertex for position 1. Expected cell vertices [
[0.5, 0.625],
[32.75, -15.5],
[0.5, 33],
], found [
[0.5, 0.625],
[7.905417527999327, -3.0777087639996634],
[0.5, 9],
]. First cell', src\cell_builder.rs:513:13
I'm currently investigating the reason for that. It broke with the previous extend_vector normalized orthogonal
commit.
Most likely its the hardcoded, expected values, that are now outdated (depending on how you calculated them back when you implemented this test).
Sry, I'm currently busy moving, and I forgot to get back at this.
It is indeed due to the expected values being outdated.
Normalizing the orthogonal
, and changing the scale
factor to be the more easily computed as width+height
of course changes where the extended vertices end up
Due to these changes, it is also very very difficult to find "pretty" numbers for tests. I changed the tested triangle to be
(-0.5, 1.0)
(-1.5, -1.0)
( 0.5, -1.0)
circumcenter c = (-0.5, -0.25)
new scale = width + height = 4 + 4 = 8
angles with +x
-axis as reference
e1angle = 270° - atan(-1/-2) = 243.435°
e2angle = 0°
e3angle = 180° - atan(2/1) = 116.565°
Instead of extending the half-edge-intersection point, the circumcenter is extended:
exv1.x = c.x + scale * cos(e1angle - 90°) = -0.5 + 8. * cos(153.435°) = -7.655
exv1.y = c.y + scale * sin(e1angle - 90°) = -0.25 + 8. * sin(153.453°) = 3.328
exv2.x = c.x + scale * cos(e2angle - 90°) = -0.5 + 8. * cos(-90°) = -0.5
exv2.y = c.y + scale * sin(e2angle - 90°) = -0.25 + 8. * sin(-90°) = -8.25
exv3.x = c.x + scale * cos(e3angle - 90°) = -0.5 + 8. * cos(26.565°) = 6.655
exv3.y = c.y + scale * sin(e3angle - 90°) = -0.25 + 8. * sin(26.565°) = 3.328
(7.865633420552356, 2.8089875327071336)
(8.155417527999326, 3.5777087639996634)
(-0.5, -9)
<-
The proximity of each calculated point to its hand-estimated position is an indicator, that the expected test-values are correct. This is confirmed by the third point, whose mid-edge intersection point is trivial to find at (-0.5, -1.0)
. Extending this by scale
in -90°
-direction leads to exactly this value.Thus, this PR finished its scope and can be merged
Supposedly fixes #2
This commit changes the algorithm to not rely on mirrored coordinates, instead calculating
left
andbottom
from theBoundingBox
and checking for coordinates to be in rangebottom <= y <= top
andleft <= x <= right
. I chose not to rely onun-shift -> voronoi -> re-shift
, since this could cause confusion for users.The new output looks okay at first glance, but the![Voronoi_fix__corners_broken](https://user-images.githubusercontent.com/29286474/105499144-55a12600-5cc1-11eb-87f0-d4fd133507a7.png)
BoundingBox
Corners (e.g. top-left Voronoi-Diagram, upper right corner) are still a little broken. Haven't figured out why, yet.Benchmark Comparison "large_input_benchmark":