Wrong intersection of line segments

[Wikunia]

I'm currently puzzled by this intersection error.

import Luxor
using LazySets
Luxor.@png begin 
	a1 = Float32[-34.67, -46.06]
	a2 = Float32[-13.03, -49.77]

	b1 = Float32[-22.473152, -48.13686]
	b2 = Float32[-19.031397, -48.730015]
	Luxor.scale(20)
	Luxor.translate(20.67, 46.06)
	Luxor.line(Luxor.Point(a1...), Luxor.Point(a2...), :stroke)
	Luxor.sethue("red")
	Luxor.line(Luxor.Point(b1...), Luxor.Point(b2...), :stroke)

	is = intersection(LineSegment(b1, b2), LineSegment(a1, a2))
	Luxor.sethue("blue")
	Luxor.line(Luxor.Point(is.p...), Luxor.Point(is.q...), :stroke)
end

which produces this image

If I let it run with Float64 I get an empty set which works.

[schillic]

Yes, this is a bug. It has nothing to do with Float32, but in Float64 the line segments are simply not close enough to be considered intersecting (numerical precision). The algorithm added in #2138 is only correct if the line segments are going from bottom left to top right. The problem is that the x and y coordinate of the resulting line segment are computed independently, and hence you can get two points that are not on any of the original line segments.

Here is a plot with Plots. Not sure why your plot is mirrored. I never used the Luxor backend, so maybe there is another issue there.

[Wikunia]

Yeah I just looked at the code and was wondering about the max, min section. Luxor has a flipped y axis as it's more for image stuff and I think they start at the top left corner with 0, 0. Wondering why that part was build in a way that this works only when the lines are in that orientation?

[schillic]

The algorithm was probably derived from an example where it worked. But clearly it does not always work.

Conceptually, the correct algorithm is simple: the result is a line segment that ends at two of the four end points of the original line segments. And the result uses the "inner" two points. But to do that programmatically in an efficient way is not totally obvious.

[schillic]

I have a quick fix in #3630. It will probably take time to get this reviewed and merged.

[schillic]

@Wikunia, the fix is now merged to master, but I prefer to wait with a release because there are two breaking changes already and two more to come in open PRs, so it would be good to ship them together. I hope that is okay with you.