Integer division error with Float32 for clipped Voronoi #72
Comments
|
Due to infinities somehow: (p, q, r) = ((0.015137732f0, 0.31555605f0), (0.0044495463f0, 0.97074896f0), (-Inf32, -Inf32))
┌ Warning: Invalid input, empty interval is returned
└ @ IntervalArithmetic C:\Users\User\.julia\packages\IntervalArithmetic\EquAX\src\intervals\intervals.jl:106
┌ Warning: Invalid input, empty interval is returned
└ @ IntervalArithmetic C:\Users\User\.julia\packages\IntervalArithmetic\EquAX\src\intervals\intervals.jl:106 |
|
This is the issue julia> p
(0.007668495f0, 0.7747718f0)
julia> q
(0.0044495463f0, 0.97074896f0)
julia> r
(0.015137732f0, 0.31555605f0)
julia> DelaunayTriangulation.triangle_area(p, q, r)
0.0f0
julia> DelaunayTriangulation.triangle_area(Float64.(p), Float64.(q), Float64.(r))
7.196139036472352e-6 |
|
This formula squared_triangle_area(ℓ₁²::Number, ℓ₂²::Number, ℓ₃²::Number) = (4ℓ₁² * ℓ₂² - (ℓ₁² + ℓ₂² - ℓ₃²)^2) / 16 # Heron's formulais not always the best. If I use this formula squared_triangle_area(ℓ₁²::Number, ℓ₂²::Number, ℓ₃²::Number) = let a = sqrt(ℓ₃²), b = sqrt(ℓ₂²), c = sqrt(ℓ₁²)
return (a + (b + c)) * (c - (a - b)) * (c + (a - b)) * (a + (b - c)) / 16 # https://people.eecs.berkeley.edu/~wkahan/Triangle.pdf
endthen julia> DelaunayTriangulation.triangle_area(p, q, r)
2.0964168f-5 |
This was referenced Aug 6, 2023
|
I'm still getting this error while trying to build a clipped voronoi plot (I can provide the code if you think its helpful). If you believe the issue is because of a division by zero error, I think a better formula to use would be the shoelace formula, which is basically a determinant of the coordinates of the triangle which doesn't require a division. |
|
The shoelace formula would perform worse in most cases; the division is not impactful here. Can you provide an MWE for your case, please? |
|
Unfortunately my code is far from minimum length, but I was able to reproduce the issue on a simpler geometry: using GeometryBasics, DelaunayTriangulation, CairoMakie
function is_point_in_polygon(point::Point, polygon::Polygon)
# Check if the point is on the boundary of the polygon
point in polygon && return false
n = length(coordinates(polygon))
inside = false
p1 = polygon[1]
for i in 2:n+1
p2 = polygon[mod1(i, n)]
if ((p1[2] > point[2]) != (p2[2] > point[2])) && (point[1] < (p2[1] - p1[1]) * (point[2] - p1[2]) / (p2[2] - p1[2]) + p1[1])
inside = !inside
end
p1 = copy(p2)
end
return inside
end
b_vec = reverse([Point(0.0, 0.0), Point(0.0, 1.0), Point(1.0, 1.0), Point(1.0, 0.0), Point(0.5, 0.5)])
p = Polygon(b_vec)
p2 = coordinates(p)
push!(p2,p2[1])
boundary_nodes, points2 = convert_boundary_points_to_indices(getxy.(p2))
triangulation = triangulate(points2; boundary_nodes)
minx, miny = extrema(p2)[1]
maxx, maxy = extrema(p2)[2]
for i in range(minx + 0.05, maxx - 0.05, step=0.05)
for j in range(maxy - 0.05, miny + 0.05, step=-0.05)
if is_point_in_polygon(Point(i, j), p)
try
add_point!(triangulation, (i, j))
catch
@warn "There was a problem adding this point."
end
end
end
end
vorn = voronoi(triangulation, false)
voronoiplot(vorn,show_generators = true)Here you can see two issues, one is that sometimes |
|
Thanks for the MWE. I will try and find the time soon to look into it. |
|
I somehow completely forgot about this @CNOT, sorry. I should've re-opened the issue (:. I can confirm that this issue is still present: ┌ Warning: The triangle (163, 151, 1) has a degenerate circumcenter, (-Inf, -Inf). You may encounter issues with this tessellation. You can disable this warning using toggle_inf_warn!().
└ @ DelaunayTriangulation C:\Users\danjv\.julia\packages\DelaunayTriangulation\FJ3Ab\src\algorithms\voronoi\unbounded.jl:35
┌ Warning: The triangle (256, 205, 2) has a degenerate circumcenter, (-Inf, -Inf). You may encounter issues with this tessellation. You can disable this warning using toggle_inf_warn!().
└ @ DelaunayTriangulation C:\Users\danjv\.julia\packages\DelaunayTriangulation\FJ3Ab\src\algorithms\voronoi\unbounded.jl:35
┌ Warning: The triangle (256, 221, 205) has a degenerate circumcenter, (-Inf, -Inf). You may encounter issues with this tessellation. You can disable this warning using toggle_inf_warn!().
└ @ DelaunayTriangulation C:\Users\danjv\.julia\packages\DelaunayTriangulation\FJ3Ab\src\algorithms\voronoi\unbounded.jl:35
Voronoi Tessellation.
Number of generators: 266
Number of polygon vertices: 360
Number of polygons: 266This seems to be a really weird case. I am going to very soon have an even better method for computing triangle areas using AdaptivePredicates.jl, so hopefully that fixes it. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Found while looking into MakieOrg/Makie.jl#3102.
The text was updated successfully, but these errors were encountered: