-
Notifications
You must be signed in to change notification settings - Fork 5
/
brute_force.jl
54 lines (46 loc) · 1.88 KB
/
brute_force.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct PointNotFoundError{T,P} <: Exception
tri::T
q::P
end
function Base.showerror(io::IO, e::PointNotFoundError)
err = "The point, $(e.q), could not be located."
if !has_ghost_triangles(e.tri)
err *= " This may be due to the point being outside of the triangulation and your triangulation not containing ghost triangles. Consider using `add_ghost_triangles!` on your triangulation and try again."
end
return print(io, err)
end
"""
brute_force_search(tri::Triangulation, q; itr = each_triangle(tri))
Searches for the triangle containing the point `q` by brute force. An exception will be
raised if no triangle contains the point.
See also [`jump_and_march`](@ref).
# Arguments
- `tri::Triangulation`: The [`Triangulation`](@ref).
- `q`: The point to be located.
# Keyword Arguments
- `itr = each_triangle(tri)`: The iterator over the triangles of the triangulation.
# Output
- `V`: The triangle containing the point `q`.
"""
function brute_force_search(tri::Triangulation, q; itr=each_triangle(tri))
for V in itr
cert = point_position_relative_to_triangle(tri, V, q)
!is_outside(cert) && return V
end
return throw(PointNotFoundError(tri, q))
end
"""
brute_force_search_enclosing_circumcircle(tri::Triangulation, i) -> Triangle
Searches for a triangle in `tri` containing the vertex `i` in its circumcircle using brute force. If
`tri` is a weighted Delaunay triangulation, the triangle returned instead has the lifted vertex `i`
below its witness plane. If no such triangle exists, `($∅, $∅, $∅)` is returned.
"""
function brute_force_search_enclosing_circumcircle(tri::Triangulation, i)
for V in each_triangle(tri)
cert = point_position_relative_to_circumcircle(tri, V, i)
!is_outside(cert) && return V
end
tri_type=triangle_type(tri)
V = construct_triangle(tri_type, ∅, ∅, ∅)
return V
end