3D Acoustics Architecture Autocad Bags Byggesystem C-meshes class A surfacing Condura Construction continuity types Covers e-learning Ergo Fabric structures Fabrics Filt Flat Panels folding GDS Geometry Hardware Inventar Learning M Materialer Materials Math membranes Minecraft Modeling nurbs opdeling i flader opmåling origami Panels photoshop Physics Planar mesh Rhino3d ribbon swirls Sail Sail; cover; shade Science Shades single curved panels SketchUp Software Space Sunlight Thermal Barrier Tools tutorial Unfold Unfold Patterns Voronoi Zipper
Walking in a Triangulation - VoroWiki: "Given the Delaunay triangulation (DT) of a set S of n points and a query point p, the point location problem consists of determining inside which triangle of lies p.
This is a necessary operation for the incremental constructing of a DT, for deleting a vertex from it, and also for different spatial analysis operations.
The method described here is called walking in a triangulation, and does not need any pre-processing or any additional data structures.
The adjacency relationships between the simplices in a DT are used to perform the point location. The algorithm was described in the earliest papers about the construction of the DT in two dimensions (Gold et al., 1977); Green and Sibson, 1978): in a DT, starting from a triangle τ, we move to one of the neighbours of τ (τ has 3 neighbours; we choose one neighbour such that the query point p and τ are on each side of the triangle shared by τ and its neighbour) until there is no such neighbour, then the triangle containing p is τ. The algorithm is illustrated on the right."