Skip to main content
added pdf link to solution
Source Link
Victor Liu
  • 4.5k
  • 19
  • 28

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Edit: I should add that edge hopping should be $O(\log N)$ with a reasonable constant for a single point, so it would be $O(M \log N)$ for $M$ points. However, if you sort your points by locality (like using a Hilbert curve ordering first), you can initialize each new query with the triangle of the previous query, to further reduce the runtime (I'm not a CS theorist so I can't tell you what the big-O would be there).

Edit2: Found this PDF describing such a "walking" scheme that is guaranteed to terminate, and reviews the more naive approaches.

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Edit: I should add that edge hopping should be $O(\log N)$ with a reasonable constant for a single point, so it would be $O(M \log N)$ for $M$ points. However, if you sort your points by locality (like using a Hilbert curve ordering first), you can initialize each new query with the triangle of the previous query, to further reduce the runtime (I'm not a CS theorist so I can't tell you what the big-O would be there).

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Edit: I should add that edge hopping should be $O(\log N)$ with a reasonable constant for a single point, so it would be $O(M \log N)$ for $M$ points. However, if you sort your points by locality (like using a Hilbert curve ordering first), you can initialize each new query with the triangle of the previous query, to further reduce the runtime (I'm not a CS theorist so I can't tell you what the big-O would be there).

Edit2: Found this PDF describing such a "walking" scheme that is guaranteed to terminate, and reviews the more naive approaches.

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

added runtime info
Source Link
Victor Liu
  • 4.5k
  • 19
  • 28

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Edit: I should add that edge hopping should be $O(\log N)$ with a reasonable constant for a single point, so it would be $O(M \log N)$ for $M$ points. However, if you sort your points by locality (like using a Hilbert curve ordering first), you can initialize each new query with the triangle of the previous query, to further reduce the runtime (I'm not a CS theorist so I can't tell you what the big-O would be there).

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Edit: I should add that edge hopping should be $O(\log N)$ with a reasonable constant for a single point, so it would be $O(M \log N)$ for $M$ points. However, if you sort your points by locality (like using a Hilbert curve ordering first), you can initialize each new query with the triangle of the previous query, to further reduce the runtime (I'm not a CS theorist so I can't tell you what the big-O would be there).

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.

Source Link
Victor Liu
  • 4.5k
  • 19
  • 28

The usual randomized edge hopping method should work. Basically, start with any triangle of the mesh, then determine which of the edges the target point lies on the opposite side of. That is, determine which of the edges, when extended out to a line, separate the point from the interior of the triangle. When there are two possibilities, choose one at random, and consider the triangle that is adjacent to that shared edge, and repeat. The randomization should make this method converge with probability 1 for Delaunay triangulations, and I can't think of a reason it would not work for arbitrary triangulations.

Another alternative to using quadtrees is using a Triangulation Hierarchy. See Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. It works best for Delaunay triangulations, but can also work for non-Delaunay.

Basically whatever you do to speed up point location will require the construction of an auxiliary data structure. In the case of quadtrees or some other spatial subdivision, you need to build the subdivision tree. In the case of edge-hopping, you need to build the triangle adjacent topological structure. The triangulation hierarchy also requires building a tree of coarser triangulations.