GitHub

Point Location

DelaunayTriangulation.brute_force_search — Function
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.

Arguments

  • tri::Triangulation: The Triangulation.
  • 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.
source
DelaunayTriangulation.jump_and_march — Function
jump_and_march(tri, q; kwargs...) -> Triangle[, Bool]

Find the triangle in the triangulation tri containing the query point q using the jump-and-march algorithm.

Arguments

Keyword Arguments

  • point_indices=each_solid_vertex(tri): The indices of the vertices to consider as possible starting points for the algorithm.
  • m=default_num_samples(num_vertices(point_indices)): The number of samples to use when selecting the initial point.
  • try_points=(): A list of points to try as the initial point in addition to the m sampled.
  • rng=Random.default_rng(): The random number generator to use.
  • k=select_initial_point(tri, q; point_indices, m, try_points, rng): The initial point to start the algorithm from. See select_initial_point.
  • store_history=Val(false): Whether to store the history of the algorithm.
  • history=nothing: The history of the algorithm. If store_history, then this should be a PointLocationHistory object.
  • maxiters=2 + num_exterior_curves(tri) - num_solid_vertices(tri) + num_solid_edges(tri): The maximum number of iterations to perform before restarting the algorithm with restart_jump_and_march.
Restarting the algorithm

If the algorithm restarts, then the initial point k is selected again using select_initial_point, and the algorithm is restarted from there. This is done if the algorithm gets stuck in a loop, or if the algorithm is not able to find the correct triangle containing q after maxiters iterations. For a convex geometry, maxiters can be safely ignored, as the sequence of triangles visited is acyclic [see H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Combinatorica 10 (1990) 251-260.)].

  • concavity_protection=false: Whether to use concavity protection. See concavity_protection_check. This is only needed if your triangulation is not convex.
  • use_barriers::Val{U}=Val(false): Whether to stop searching beyond any segments in the triangulation.
Found triangles with barriers

If you are using barriers, it will be your responsibility to verify that any found triangle from this function actually contains the triangle. This can be verified using the returned flag (see below), although the point might still be on the triangle's boundary.

Walking past vertices of barriers

If you are using barriers, it is possible that the algorithm can walk past vertices of barriers. One way this can happen is if the initial search line intersects a vertex, in which case the segment might not be considered. Another way this can happen is if you start the algorithm directly on a segment vertex, in which case the algorithm can go past it (e.g. this means that it is possible that a ghost triangle might still be returned if you start the algorithm on a boundary node).

Output

  • V: The triangle containing q, with type given by triangle_type(tri).
Hitting barriers

If a barrier is hit before any initial triangle is properly identified, the returned triangle is (0, 0, 0); this is only possible if use_barriers == Val(true). Moreover, if use_barriers == Val(true), the final triangle may not even be valid if invisible_flag == true (defined below).

If you have use_barriers == Val(true), then we also return

  • invisible_flag: false if the triangle was found without hitting a barrier, and true otherwise.
Non-convex geometries

While this function does still work for non-convex geometries, it may be significantly slower than for convex geometries, as most of the details of the algorithm assume that the geometry is convex, and so the algorithm may have to restart many times at new initial vertices k.

Ghost triangles

For this function to work best, the triangulation should have ghost triangles, which you can add using add_ghost_triangles! in case tri does not already have them. Without ghost triangles, the function may not be able to find the correct triangle containing q.

Extended help

The algorithm underlying this function is complicated and broken into many parts. Here, we describe a brief overview of the algorithm, but note that the documentation contains a much more detailed description.

  1. Firstly, the algorithm is initialised depending on whether k is a boundary or an interior vertex, using initialise_jump_and_march_boundary_vertex or initialise_jump_and_march_interior_vertex respectively.
  2. From the initial triangle (i, j, k) chosen, we then check if q is one of pᵢ, pⱼ, and p = pₖ and then return according to jump_and_march_return_on_vertex if needed.
  3. If we do not return above, we need to step from the initial triangle towards q. Since we put pᵢ and pⱼ to the left and right of the line pq, respectively, this means that we step until the triangle pᵢpⱼq is no longer positively oriented. So, while the triangle is positively oriented, we step according to jump_and_march_across_triangle.
  4. If we have not yet returned and the triangle is no longer positively oriented, we check if the triangle is degenerate using jump_and_march_degenerate_arrangement and reinitialise the algorithm if needed. Otherwise, we have found the triangle containing q and return the triangle.
source
DelaunayTriangulation.find_polygon — Function
find_polygon(tri::Triangulation, q) -> Integer

Given a point q, finds the index of the polygon in the triangulation tri that contains q. If q is on the boundary of the triangulation or outside the triangulation, the function returns 0.

See also dist and distance_to_polygon.

source