Oct 14 '22 17:10 dorn-gerhard

A benchmark results for the new implementation using intersectparameters (CrossingSegments) is better than the solution inspired by Balbes, R. and Siegel, J. 1990. (https://www.sciencedirect.com/science/article/abs/pii/0167839691900198)

grafik

In addition intersectcollinear was wrong as mentioned in #299 This is repaired now and a new test is added.

Oct 14 '22 17:10 dorn-gerhard

That is amazing @dorn-gerhard 👏🏽 I will wait for the tests to pass before starting the review.

Oct 14 '22 18:10 juliohm

@dorn-gerhard various tests are failing. This is a central key algorithm that we need to be extra careful to change. Can you please double check what is happening?

Oct 15 '22 12:10 juliohm

@dorn-gerhard various tests are failing. This is a central key algorithm that we need to be extra careful to change. Can you please double check what is happening?

Sure, I checked the problem, was a little mistake.

A question arose regarding tests of Polytopes: is the order of vertices important?

e.g. currently Segment((1,0), (0,0)) == Segment((0,0), (1,0)) returns false

Reason why i am asking: The outcome of two overlapping segments could depend on the order or arguments so that s1 ∩ s2 == s2 ∩ s1 returns false

Oct 15 '22 13:10 dorn-gerhard

Yes, the segments are oriented in our design, A -- B is different than B -- A

Oct 15 '22 13:10 juliohm

Apparently the changes you proposed are causing the processes to hang @dorn-gerhard. I really appreciate it if you can be extra careful with all these intersection details as they can break a great deal of code downstream (like triangulation algorithms).

Oct 15 '22 17:10 juliohm

I see the problem and investigated the issue deeper.

A test in polytopes.jl fails, namely a issimiple(p::PolyArea) test which calls issimple(p.outer::Chain) in chains.jl which uses intersection of Segments and basically checks whether all Segment Intersections are CornerTouchingSegments or NoIntersections.

The problem is of numerical nature and lies in the intersectparameters function when calculating the parameter for the intersections of two segments. It only occurs in two testfiles (smooth$.jl) and there only in five of 120 intersections.

here is one example

P2 = Point{2, Float32}
s1 = Segment(P2(0.256951700559717, 0.382175329425997), P2(0.307299924914942, 0.272417978947013))
s2 = Segment(P2(0.307299924914942,0.272417978947013), P2(0.348147533748717, 0.184216111169297))
λ₁, λ₂ = Meshes.intersectparameters(s1(0), s1(1), s2(0), s2(1))

yields julia> λ₁ = 1.000007f0, λ₂ =-3.548892f-6 instead something close to one(T), zero(T). isapprox(λ₁, one(T), atol=atol(T)) fails here.

So what is the reason for this numerical inaccuracy?

I checked the function intersectparameters where we used the qr decomposition to decide the rank AND calculate the parameters.

Now the following happens:

a, b = s1(0), s1(1)
c, d = s2(0), s2(1)

A = [(b - a) (c - d)]
y = c - a

QQ = qr(A)

@info A \ y
@info QQ.R \ QQ.Q' * y

so the current implementation using the QR decomposition produces inaccurate results.

I therefore tried to solve the problem by replacing the second QR decomposition by A \ y. Benchmarks are promising, function now yields:

julia> @benchmark Meshes.intersectparameters(s1(0), s1(1), s2(0), s2(1))
BenchmarkTools.Trial: 10000 samples with 194 evaluations.
 Range (min … max):  495.876 ns … 66.443 μs  ┊ GC (min … max): 0.00% … 99.10%
 Time  (median):     516.495 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   611.109 ns ±  1.720 μs  ┊ GC (mean ± σ):  7.42% ±  2.62%

  █▆▄▆▄▄▂▂▄▃▂▁▂      ▂▁          ▁                             ▁
  ████████████████▇▇▇█████▇▇▇██▇███▇▇▆▆▆█▇▆▇▇▆▆▆▆▅▆▅▅▄▅▅▅▄▅▄▅▄ █
  496 ns        Histogram: log(frequency) by time      1.09 μs <

 Memory estimate: 432 bytes, allocs estimate: 13.

the new function (avoiding the second QR decomposition) yields:

julia> @benchmark intersectparameters3(s1(0), s1(1), s2(0), s2(1))
BenchmarkTools.Trial: 10000 samples with 195 evaluations.
 Range (min … max):  475.385 ns … 66.247 μs  ┊ GC (min … max): 0.00% … 99.15%
 Time  (median):     491.795 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   582.439 ns ±  1.692 μs  ┊ GC (mean ± σ):  7.65% ±  2.62%

  █▇▄▆▄▄▃▃▃▂▃▂▂▂ ▁   ▂▂                                        ▁
  █████████████████▇▇█████▇▇█▇▇▆▇▇▆▇▆▆▅▆▇▇▅▆▆▅▆▅▆▄▅▅▅▅▃▄▄▅▅▄▄▅ █
  475 ns        Histogram: log(frequency) by time      1.07 μs <

 Memory estimate: 432 bytes, allocs estimate: 13.

I also ran all tests locally, now it should work

Testing polytopes.jl...
Test Summary:       | Pass  Total
Meshes.jl (Float32) |  371    371

Oct 16 '22 18:10 dorn-gerhard

Codecov Report

Merging #309 (1ae3e8b) into master (4f358a3) will increase coverage by 0.09%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #309      +/-   ##
==========================================
+ Coverage   92.74%   92.84%   +0.09%     
==========================================
  Files         105      106       +1     
  Lines        3006     3018      +12     
==========================================
+ Hits         2788     2802      +14     
+ Misses        218      216       -2

Impacted Files	Coverage Δ
src/intersections/rays.jl	`88.88% <ø> (+3.17%)`	:arrow_up:
src/intersections/raysegment.jl	`100.00% <ø> (ø)`
src/intersections/lines.jl	`100.00% <100.00%> (ø)`
src/intersections/segments.jl	`100.00% <100.00%> (+1.31%)`	:arrow_up:
src/toporelations/adjacency.jl	`95.91% <0.00%> (-4.09%)`	:arrow_down:
src/sampling.jl	`100.00% <0.00%> (ø)`
src/diffops.jl
src/sampling/block.jl	`83.33% <0.00%> (ø)`
src/matrices.jl	`98.24% <0.00%> (ø)`
src/toporelations/boundary.jl	`98.31% <0.00%> (+1.02%)`	:arrow_up:
... and 2 more

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

Oct 16 '22 18:10 codecov[bot]

I will need a bit of time to work on the test cases, intersectiontypes for 2d are missing, i can provide the 5 test cases and the 8 subcases for collinear.

Actually we are lucky that some test cases which compare segments work, as the order of points is still important (we could use the ringequal function later or map isequal to ringequal at least for Segments (to be discussed in issue #310 ) @test s1 ∩ s2 == s2 ∩ s1 == Segment(P2(0,0), P2(1,0))

Oct 18 '22 07:10 dorn-gerhard

Looking forward to this one 💯 it is nice to see a PR where we delete more lines than we add, and increase the generality of the algorithm at the same time.

Feel free to request a review when the tests are in place 👍🏽

Oct 20 '22 10:10 juliohm

@dorn-gerhard did you have time to take a look into this?

Oct 27 '22 17:10 juliohm

I added a bunch of test cases for 2D with special focus on colinear case, including tests on IntersectionType

grafik

I didn't touch the old 2D test cases, of which some may have become obsolete.

Oct 28 '22 18:10 dorn-gerhard

Amazing work @dorn-gerhard , one more step towards a robust intersection library 💯

Oct 31 '22 16:10 juliohm

Meshes.jl
Meshes.jl copied to clipboard

Implement intersectparameters also in segments.jl remove intersectcollinear and intersectpoint

Codecov Report

Meshes.jl Meshes.jl copied to clipboard

Implement intersectparameters also in segments.jl remove intersectcollinear and intersectpoint

Codecov Report

Meshes.jl
Meshes.jl copied to clipboard