cg_lab_search_triangulation.pdf
版权申诉
175 浏览量
2023-06-18
13:11:30
上传
评论
收藏 196KB PDF 举报
Computational Geometry Lab:
SEARCHING A TRIANGULATION
John Burkardt
Information Technology Department
Virginia Tech
http://people.sc.fsu.edu/∼jburkardt/presentations/cg lab search triangulation.pdf
August 28, 2018
1 Introduction
This lab continues the topic of Computational Geometry. Having studied triangles and triangulations, we
will now turn to the question of searching. In particular, we will suppose that we have a computational
region R, and a set of points P which are contained in R. (Actually, we will also allow the possibility that
some points are outside the region.)
We further suppose that we have constructed a triangulation τ of R, consisting of t num triangles, with
a typical triangle indicated by T
i
. We now wish to know, for each point p
i
, the identity of the triangle T
i
that contains the point. If the point is shared by several triangles, it is sufficient to give just one triangle. If
the point does not lie in any of the triangles, then we may be satisfied with a flag value of “-1”, or perhaps
we would be interested in the index of a triangle that is near to the point.
We already know, from a previous lab, how to determine whether a point lies inside a triangle. So if we
have a triangulation, and ask which triangle contains a point, we could simply check each triangle, stopping
as soon as we find one. This would mean that on average we’d have to check about
t num
2
triangles.
It’s hard to imagine, but it’s possible to carry out this task much faster. There is a method called the
Delaunay search, which makes roughly only
√
t num checks to locate a point in a triangulation. It is not
unusual for a triangulation to have a million triangles, in which case the Delaunay method is about 500
times faster than the straightforward searching method. And the advantage becomes even greater when we
go to a 3D mesh.
This faster method only works on special triangulations, namely, those that have the Delaunay property,
which is explained and discussed in another lab. Moreover, a certain amount of preprocessing must be done
in order to record which triangles are neighbors of each other. However, once that is done, the algorithm
works beautifully, starting with a random tetrahedron as a first guess, and then “walking” from one triangle
to the next, more or less directly towards the correct one.
1.1 Where is a Point Relative to a Triangle?
Let us recall information from the lab on barycentric coordinates for triangles. We suppose we have a triangle
T={a,b,c} and a point p. We presume we have a function Area(a,b,c) for the area of the triangle formed
1
资源评论
