Algorithm772:STRIPACK:Delaunay Triangulation and Voronoi Diagram on the Surface of a Sphere
ROBERT J.RENKA
University of North Texas
STRIPACK is a Fortran77software package that employs an incremental algorithm to construct a Delaunay triangulation and,optionally,a Voronoi diagram of a set of points (nodes)on the surface of the unit sphere.The triangulation covers the convex hull of the nodes,which need not be the entire surface,while the Voronoi diagram covers the entire surface.The package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions.For N nodes,the storage requirement for the triangulation is13N integer storage locations in addition to3N nodal https://www.doczj.com/doc/a812988471.html,ing an off-line algorithm and work space of size3N,the triangulation can be constructed with time complexity O?N log N?.
Categories and Subject Descriptors:G.1.1[Numerical Analysis]:Interpolation;G.1.2[Nu-merical Analysis]:Approximation;G.4[Mathematics of Computing]:Mathematical Soft-ware
General Terms:Algorithms
Additional Key Words and Phrases:Delaunay triangulation,Dirichlet tessellation,sphere, Thiessen regions,Voronoi diagram
1.INTRODUCTION
The Delaunay triangulation[Delaunay1934]and its dual,the Voronoi diagram[Voronoi1908],have a large and growing number of applications, among which are finite-element grid generation,scattered data fitting,and the efficient solution of closest-point problems[Preparata and Shamos 1985].Most of the literature on these structures describes the planar case, but the applications also frequently arise in R3and on the surface of a sphere[Augenbaum and Peskin1985;Renka1984a;1997].
This material is based upon work supported by the National Science Foundation under Award https://www.doczj.com/doc/a812988471.html,R-9111671.
Author’s address:Department of Computer Sciences,University of North Texas,Denton,TX 76203-1366.
Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage,the copyright notice,the title of the publication,and its date appear, and notice is given that copying is by permission of the ACM,Inc.To copy otherwise,to republish,to post on servers,or to redistribute to lists,requires prior specific permission and/or a fee.
?1997ACM0098-3500/97/0900–0416$5.00
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997,Pages416–434.
STRIPACK is a revision of the triangulation portion of Algorithm 623
[Renka 1984b].The language has been updated to Fortran 77;the data structure has been changed;the time complexity has been reduced;and a number of capabilities have been added.The additions include a subroutine that constructs the Voronoi diagram associated with a given Delaunay triangulation,and a function that locates a point relative to a polygon on the surface of the sphere.These are further discussed in Section 3.Both were motivated by the development of a new model of plate tectonics in which plate motion is driven by the frictional forces exerted by the underlying mantle [Fohlmeister and Renka 1994;Fohlmeister et al.1990].It is assumed that the mantle flow at the surface is directed radially outward from each of a set of hotspots at various locations on the surface of the earth (modeled by the unit sphere).We partition the surface into a set of Voronoi regions (spheres of influence),each centered on a hotspot.Refer to Figure 1.
We present definitions in Section 2,some theoretical background in Section 3,a discussion of algorithms in Section 4,and a description of the software package in Section
5.
Fig.1.Hotspot-centered Voronoi regions (convection cells).
Algorithm 772:STRIPACK ?417
ACM Transactions on Mathematical Software,Vol.23,No.3,September 1997.
2.DEFINITIONS AND TERMINOLOGY
Denote the unit sphere centered at the origin by
U??p?R3:?p??1?,
where???is the Euclidean norm on R3.A metric on U is defined by d?p,q??arccos?p,q??p,q?U,where??,??is the inner product associated with R3,and the angular separation(arclength)between p and q is in the interval?0,??.A subset H?U is convex if,for every pair of points p,q?H,a geodesic joining p to q(uniquely defined unless d?p,q???)is contained in H.The convex hull H of a finite set S of points of U is the smallest convex set that contains all the points.Note that,if the elements of S are contained in a single hemisphere,H has an interior(the smaller region)and an exterior(the larger region)with a boundary curve consisting of geodesics joining elements of S.Otherwise, H is the entire sphere surface.The convex hull of three distinct points is a (spherical)triangle with the points as vertices.If the vertices are collinear (lie on a common great circle),the triangle is null(has zero area).
Let S??p i?i?1N denote a set of N distinct elements of U,referred to as nodes,not lying on a common great circle,for N?3,and let H denote the convex hull of S.A triangulation T of S is a set of triangles that satisfy the following properties:
(1)the triangle vertices are nodes,
(2)no triangle contains a node other than its vertices,
(3)the triangle interiors are pairwise disjoint,and
(4)the union of triangles covers H.
It follows from the definition that the set of vertices coincides with S and the triangulation partitions H.If H is contained in a hemisphere,the triangulation has boundary edges(triangle sides that are not shared by two triangles),the endpoints of which are referred to as boundary nodes.An edge that is not a boundary edge is an interior edge,and a node that is not a boundary node is an interior node.
A triangle with vertices p i,p j,and p k?S will be denoted?p i,p j,p k?, where the vertices are specified in counterclockwise order,i.e.,det ?p i,p j,p k???p i?p j,p k??0,where det?p i,p j,p k?denotes the determinant of the matrix with rows(columns)p i,p j,and p k in that order, and p i?p j denotes the vector cross product.The circumcenter of a triangle?p i,p j,p k?is
v ijk?
?p j?p i???p k?p i???p j?p i???p k?p i??
.
418?Robert J.Renka
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
Algorithm772:STRIPACK?419 Note that since the vertices cannot lie on a common line,v ijk is well defined even for a null triangle.Also,since?v ijk,p l??det?p i,p j,p k?/??p j?p i???p k?p i??for l??i,j,k?,v ijk is equidistant from the vertices(as is?v ijk,but no other point of U).v ijk and?v ijk are the intersections of the perpendicular bisectors(great circles)of the triangle sides.The circum-radius of?p i,p j,p k?is r ijk?d?v ijk,p l?for l??i,j,k?,and the circum-circle of?p i,p j,p k?is
C ijk??p?U:d?v ijk,p??r ijk?.
Note that0?r ijk??/2,and C ijk contains p i,p j,and p k.
A Delaunay triangulation T*of S is a triangulation of S with the empty circumcircle interior property,i.e.,no circumcircle of a triangle of T contains a node in its interior.It is uniquely defined up to the neutral case of four or more nodes lying on a common circle(plane).Delaunay triangu-lations have also been referred to as Thiessen triangulations.The circum-circle property implies a reasonably uniform triangulation which provides a good basis for interpolation of data values associated with the nodes [Lawson1984;Renka1984a;1984b].
For each node p i?S,we define a Voronoi region R i as the closure of the set of points closer to p i than to any other node,i.e.,
R i??p?U:d?p,p i??d?p,p j??p j?S?.
The set of Voronoi regions?R i?i?1N partitions U into a Voronoi diagram,also termed a Dirichlet or Thiessen tessellation[Rhynsburger1973].A Voronoi edge is the intersection of two Voronoi regions that share a point,and a Voronoi vertex is the intersection of three or more Voronoi regions that share a point.Hence Voronoi edges are portions of perpendicular bisectors of geodesics joining pairs of nodes,and Voronoi vertices are circumcenters or negative circumcenters of triangles with vertices in S.
3.DUALITY AND EXTENSION OF THE TRIANGULATION
We now illustrate the duality between the Delaunay triangulation and the Voronoi diagram.This provides the basis for an algorithm that constructs one from the other.The theory for the analogous planar tessellations is well known[Lawson1977;Sibson1978].In that case,there is a one-to-one correspondence between Voronoi regions and triangulation vertices(nodes); Voronoi edges are portions of perpendicular bisectors of triangulation edges;and the set of Voronoi vertices coincides with the set of triangle circumcenters.(In the neutral case of four or more nodes lying on a common circle,one or more Voronoi edges degenerates to a point.)Thus, given a Delaunay triangulation,the Voronoi region associated with a node is defined by the(cyclically)ordered sequence of circumcenters of the triangles containing the node.Conversely,a Delaunay triangulation may be constructed from a Voronoi diagram by connecting nodes whose Voronoi
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
420?Robert J.Renka
regions share more than one point and,in the case of k nodes on a common circle for k?3,choosing an arbitrary set of k?3nonintersecting edges.Both algorithms have operation counts of O?N?.
We will show that the case of nodes on the surface of the sphere is
completely analogous to the planar case if the convex hull H is the entire surface.This restriction seems to be an implicit assumption in the litera-ture[Augenbaum and Peskin1985].If the nodes are contained in a single hemisphere,however,the set of Voronoi vertices is a superset of the triangulation circumcenters.The question is then how to select the addi-tional Voronoi vertices in an algorithm for constructing the Voronoi dia-gram from a given Delaunay triangulation.This section is primarily addressed to answering that question.
Consider the simplest case in which N?3.There are two Voronoi vertices:the circumcenter and its negative.In the case of four nodes and two triangles,the Voronoi vertices are the two circumcenters along with the negatives of the circumcenters of the other possible pair of triangles (the two triangles obtained by swapping the shared edge for the other
diagonal).More generally,there are2N?4Voronoi vertices,correspond-ing to the number of triangles in a triangulation that covers the surface,
while the number of triangles is2N?N B?2for N B boundary nodes if N B?0.Thus the number of additional Voronoi vertices is N B?2.This is the number of triangles in a triangulation in which all nodes are
boundary nodes,and in fact the solution is to construct a triangulation T B of the boundary nodes using an“empty circumcircle exterior”criterion.The additional Voronoi vertices are then the negative circumcenters of the triangles of T B.These may be thought of as the circumcenters of a set of pseudotriangles that cover the exterior of H.The following results make these ideas more precise.
L EMMA 3.1.A triangle circumcenter or its negative q??v ijk is a Voronoi vertex if and only if q is not contained in the interior of a Voronoi region,i.e.,for every node p l?S,d?q,p l??d?q,p m?for some node p m p l.
P ROOF.This follows immediately from the definitions.e
Let T*be a Delaunay triangulation of S.
T HEOREM3.2.If?p i,p j,p k??T*,then v ijk is a Voronoi vertex.
P ROOF.Suppose?p i,p j,p k??T*.Then d?v ijk,p l??r ijk?p l?S by the empty circumcircle interior criterion.Hence,for every p l?S,d?v ijk, p l??d?v ijk,p m?for some p m p l(using m??i,j,k???l?),i.e.,v ijk is a Voronoi vertex by Lemma3.1.e
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
Algorithm772:STRIPACK?421 L EMMA3.3.Suppose p i is an interior node of T*.Then,for every triangle ?p i,p j,p k?of T*that contains p i,?v ijk is closer to some node p l than to p i,p j,or p k.
P ROOF.If some circumcircle C ijk contains all nodes,then every node is a boundary node.Hence,for an interior node p i,C ijk has a node in its exterior,i.e.,?p l?S such that d?v ijk,p l??r ijk,implying that d??v ijk,p l????d?v ijk,p l????r ijk?d??v ijk,p m?for
m??i,j,k?.e
Let p l be the closest node to?v ijk.Then either?v ijk is not a Voronoi vertex(it is interior to R l)or it is a Voronoi vertex(circumcenter or negative circumcenter)associated with some triangle containing p l.In either case,we have the following.
T HEOREM3.4.The negative circumcenter?v ijk of a triangle of T*that contains an interior node need not be included in the set of Voronoi vertices. (If it is a Voronoi vertex,it coincides with the circumcenter of another triangle or the negative circumcenter of a triangle containing only boundary nodes.)Thus,if all nodes are contained in a single hemisphere,the addi-tional Voronoi vertices(other than v ijk for?p i,p j,p k??T*)are negative circumcenters of triangles containing only boundary nodes.
By Theorem3.4,the additional Voronoi vertices associated with nodes in a single hemisphere are obtained by triangulating the set of N B boundary nodes S B.Let T B*denote a triangulation of S B in which all triangle circumcircles have no nodes in their exteriors:the complement of a Delau-nay triangulation.
T HEOREM 3.5.For each triangle?p i,p j,p k??T B*,?v ijk is a Voronoi vertex(in the Voronoi diagram associated with S).
P ROOF.For?p i,p j,p k??T B*,all nodes of S B are on or interior to C ijk, i.e.,for every node p l?S B,d?v ijk,p l??r ijk.Hence d??v ijk,p l????d?v ijk,p l????r ijk?d??v ijk,p m??m??i,j,k?.
Thus?v ijk is not interior to a Voronoi region and is therefore a Voronoi vertex by Lemma3.1.e
As in the case of the Delaunay triangulation,T B*can be constructed from an arbitrary triangulation T B of S B by swapping diagonal arcs in convex quadrilaterals consisting of pairs of adjacent triangles.Note that,in the case of T B*,all such quadrilaterals are necessarily convex.The swap test applied to interior edges is a local application of the circumcircle criterion: the shared edge in a pair of adjacent triangles is swapped out if and only if the fourth vertex is exterior to the circumcircle of(either)one of the triangles.In the case of collinear nodes,T B*will contain null triangles,but their circumcenters are well defined.
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
422?Robert J.Renka
The following theorem provides a simple computational procedure for applying the swap test without computing distances.The operation count is 9multiplications,14additions,and a comparison.
T HEOREM 3.6.Given adjacent triangles?p i,p j,p k?and?p j,p i,p l?in T B,the diagonals should be swapped if and only if
det?p j?p i,p k?p i,p l?p i??0.
P ROOF.
d?v ijk,p l??r ijk
N arccos?v ijk,p l??arccos?v ijk,p i?
N?v ijk,p l???v ijk,p i?
N?v ijk,p l?p i????p j?p i???p k?p i?
,p l?p i??0
??p j?p i???p k?p i??
N det?p j?p i,p k?p i,p l?p i??0e
Corollary3.7.The swap test is well defined,i.e.,given adjacent trian-gles?p i,p j,p k?and?p j,p i,p l?in T B,
p l is exterior to C ijk
N p k is exterior to C jil
N p i is interior to C klj
N p j is interior to C lki.
P ROOF.By Theorem 3.6,p l is exterior to C ijk if and only if det?p j?p i,p k?p i,p l?p i??det?p j,p k,p l??det?p i,p k,p j??
det?p i,p j,p l??det?p i,p l,p k??0.Permuting subscripts,p k is exterior to C jil if det?p i?p j,p l?p j,p k?p j??det?p i,p l,p k??det?p j,p l,p i??det?p j,p i,p k??det?p j,p k,p l??0.Equivalence of the first two criteria follows from equality of the determinants.The other results are obtained by a similar computation:p i is interior to C klj if and only if det?p l?p k,p j?p k,p i?p k??0,and p j is interior to C lki if and only if det?p k?p l,p i?p l,p j?p l??0,where det?p l?p k,p j?p k,p i?p k??det?p k?p l,p i?p l,p j?p l??
?det?p j?p i,p k?p i,p l?p i?.e
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
The following theorem relates the local circumcircle criterion to the global property defining T B *.We define an edge of T B to be locally optimal if and only if it is a boundary edge or it is an interior edge that satisfies the local circumcircle criterion.
T HEOREM 3.8.All circumcircles of T B have empty exteriors ?T B ?T B *?if and only if all edges of T B are locally optimal.
P ROOF .The “only if”part follows immediately from the definitions.For the other part,suppose the theorem is false,i.e.,that all edges are locally optimal and that there is a circumcircle C ijk with some node p m in its exterior.Refer to Figure 2.We may assume without loss of generality that p k and p m lie on opposite sides of the edge e ij joining p i and p j ,i.e.,e ij is an interior edge,and det ?p i ,p j ,p m ??0.Among all triangles of T B whose circumcircles have p m as an exterior point,assume without loss of general-ity that none is closer to p m in the sense that they share a point with the geodesic joining p m to an interior point of e ij .Let ?p i ,p l ,p j ?be the triangle that shares edge e ij with ?p i ,p j ,p k ?.Since e ij is locally optimal,p l is not exterior to C ijk ,and p l p m .If both e il and e lj were boundary edges,then p m would be contained in ?p i ,p l ,p j ?.Hence either e il is an interior edge with det ?p i ,p l ,p m ??0,or e lj is an interior edge with det ?p l ,p j ,p m ??0.Hence p m is closer to ?p i ,p l ,p j ?than ?p i ,p j ,p k ?,and a contradiction will be reached if it is shown that p m is exterior to C ilj .The great circle containing p i and p j defines two hemispheres,one of which contains p l ,and the portion of C ilj that lies in this hemisphere is on or interior to C ijk .It follows that p m is exterior to C ilj .e
The following algorithm constructs T B *incrementally.
(1)Cyclically order the nodes of S B in counterclockwise order.Denote the
sequence by ?p i ?i ?1N B
.
Fig.2.Theorem 3.8.
Algorithm 772:STRIPACK ?423
ACM Transactions on Mathematical Software,Vol.23,No.3,September 1997.
(2)Initialize the triangulation to T 3???p 1,p 2,p 3??.
(3)For k ?4to N B
(a)construct T k by connecting p k to p 1and p k ?1,i.e.,T k ?T k ?1*???p 1,p k ?1,p k ??(b)construct T k *from T k by applying the swap test and appropriate
swaps to the interior edges opposite p k beginning with the edge joining p 1to p k ?1.Following each swap there are two new edges opposite p k which,if not boundary edges,must be tested for swaps.
We will show that the algorithm results in T N B
*?T B *.First note that any reasonable data structure for a triangulation T of S includes the ordered sequence of boundary nodes implicitly,if not explicitly.The operation count for step (1)is therefore at most O ?N B ?given the index of some boundary node.The worst-case operation count for step (3b)is O ?k ?,resulting in O ?N B 2?for step (3)but,for randomly generated nodes,step (3b)runs in constant expected time,resulting in an operation count linear in N B .Since the nodes lie on the boundary of a convex region,p 1and p k ?1are the only nodes visible from p k at step (3a),and execution of the step results in a triangulation T k of the first k nodes.To show that all circumcircles of T k *have empty exteriors,it suffices to show that all edges are locally optimal following step (3b).This follows from Theorem 3.8.It is sufficient to show that,following each swap,the new edge containing p k will remain locally optimal regardless of subsequent swaps (but may be swapped out when additional nodes are added).
T HEOREM 3.9.Let T k ?1*be a triangulation of ?p i ?i ?1k ?1in which no circum-
circle has a node in its exterior,and let T k be a triangulation of ?p i ?i ?1k .Let
?p i ,p j ,p k ?and ?p j ,p i ,p l ?be adjacent triangles of T k ,where ?p j ,p i ,p l ?is
also a triangle of T k ?1*.Suppose the swap test results in edge e ij being
replaced by edge e kl .Then no sequence of swap tests and appropriate swaps will result in the removal of e kl .Note that p j ,p i ,and p l are not necessarily the first vertices to which p k was connected.
P ROOF .By the assumptions,p k is the only node exterior to C jil .Suppose that at some point e kl is to be swapped for some edge e rs joining nodes p r and p s (either of which might coincide with p i or p j ).Refer to Figure 3.Then p r and p s must lie on opposite sides of e kl ;p k and p l must lie on opposite sides of e rs ;and p l must be interior to C rks (by Theorem 3.6).
Partition C rks into three arcs p r p k ?,p k p s ?,and p s p r ?.Since p k is exterior to
C jil and p r is not,p r p k ?must intersect C jil at some point q r (which may
coincide with p r ).Similarly,p k p s ?intersects C jil at some point q s .Thus,
C rks is partitioned into two portions:q r p k q s ?outside of C jil and q s p s p r q r
?424?Robert J.Renka
ACM Transactions on Mathematical Software,Vol.23,No.3,September 1997.
inside C jil .The arc of C jil between q s and q r that lies outside C rks contains p l ,contradicting the assumption that p l is interior to C rks .e
https://www.doczj.com/doc/a812988471.html,PUTATIONAL PROCEDURES
With the exception of the floating-point computations,the triangulation is constructed by the same incremental algorithm that we have used in the planar case [Cline and Renka 1984;Lawson 1977].The incremental algo-rithm has two advantages over an off-line algorithm such as divide-and-conquer:it is not necessary that all nodes be present before processing begins,and it allows for efficiently updating the triangulation with nodal additions and deletions.As described in Section 4.2,the optimal O ?N log N ?run time can be achieved in the case that all nodes are immediately available.The package also allows a set of prespecified trian-gulation arcs to be included,resulting in a constrained Delaunay triangu-lation [Cline and Renka 1990].
4.1Floating-Point Computations
A new node to be added to a triangulation is located relative to the triangulation and connected to all visible nodes,resulting in a new trian-gulation which is then optimized (converted to a Delaunay triangulation)by systematically applying swap tests and the appropriate swaps to the interior arcs opposite the new node.(Following each swap,there are two new arcs opposite the new node,and these must be tested for swaps.)The algorithm that locates a point p ?U relative to a triangulation employs a left test which locates p relative to a directed arc:
p left p i 3p j N det ?p ,p i ,p j ??
0.
Fig.3.Theorem 3.9.
Algorithm 772:STRIPACK ?425
ACM Transactions on Mathematical Software,Vol.23,No.3,September 1997.
Note that det?p,p i,p j???p,p i?p j??0if and only if p lies in the left hemisphere as viewed from p i toward p j.
The swap test applied to an interior arc p i3p j is a local application of the circumcircle criterion:adjacent triangles?p i,p j,p k?and?p j,p i,p l?are replaced by triangles?p k,p l,p j?and?p l,p k,p i?if and only if
det?p j?p i,p k?p i,p l?p i??0,
or equivalently,p l lies above(on the side opposite the origin)the plane of p i,p j,and p k and is therefore interior to the circumcircle of?p i,p j,p k?.As in the case of the reverse swap test(Theorem3.6),the swap test and the triangles resulting from a swap are well defined,i.e.,a swap is only applied to a convex quadrilateral,and the new triangles satisfy the circumcircle criterion with respect to the fourth vertex.An alternative way of viewing the Delaunay triangulation is as follows:the planar triangle corresponding to each spherical triangle lies on the boundary of the convex hull of the nodes(as elements of R3).An anonymous referee pointed out that the triangulation can be efficiently constructed by a standard convex hull algorithm with the possible addition of an auxiliary point(in case the convex hull is not the entire sphere surface)and some postprocessing.
The floating-point computations required to implicitly extend the Delau-nay triangulation to the entire surface when the nodes are contained in a single hemisphere are the distance computation,
d?p,q??arccos?p,q?,
and the circumcenter of triangle?p i,p j,p k?,
v ijk?
?p j?p i???p k?p i???p j?p i???p k?p i??
.
Although not necessary for constructing the Delaunay triangulation or Voronoi diagram,many applications require that a surface point p be located relative to a polygonal region R of U(such as a tectonic plate in the application described in Section1).Let the boundary of R be defined by a cyclically ordered sequence of vertices which form a simple closed curve. Our procedure consists of selecting a point q interior to R(by a heuristic method that attempts to avoid ill-conditioning)and traversing the bound-ary sequence to find all intersections of arc p3q with the boundary.Then p is contained in R if and only if the number of intersections is even.
Let n?p?q be the(nonzero)normal to the plane of p and q,and let v13v2denote a segment of the boundary curve such that v1and v2are on opposite sides of the plane(so that v13v2intersects the great circle containing p and q).The point of intersection r must be computed to determine if it lies on arc p3q:
426?Robert J.Renka
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
r?
v1?t?v2?v1?
?v1?t?v2?v1??
for t?
?n,v1?
?n,v1?v2?
.
Since?n,v1?and?n,v2?have opposite signs(or one of them is zero),t is well defined and lies in the interval?0,1?.Hence r is a normalized convex combination of v1and v2(assumed to be linearly independent)and is orthogonal to n,i.e.,r is the required intersection point.Finally,r lies in the interior of arc p3q if and only if?r,n?p?and?r,q?n?are both positive.
Note that all of the floating-point computations involve vector cross products and dot products for which Cartesian coordinates are required.It is thus convenient to store surface points as triples of Cartesian coordi-nates rather than spherical coordinates or latitude/longitude pairs.
4.2An O?N log N?Point-Location Method
It has been shown that,regardless of the nodal distribution,if the nodes are inserted in random order,the expected number of structural changes (swaps and swap tests)is O?N?[Guibas et al.1992].The time complexity of an incremental algorithm is therefore determined by the cost of locating each new node relative to the triangulation of the previously added nodes. Guibas et al.describe an O?N log N?algorithm based on a tree structure containing all the intermediate triangulations along with links between overlapping triangles.A new node is located by tracing,in the order of their creation,all triangles that contain it[Guibas et al.1992].Barber et al. [1997]present an off-line algorithm(for constructing convex hulls and Delaunay triangulations of nodes in R d)based on an alternative data structure in which the unprocessed nodes are partitioned into subsets associated with triangles.We take a similar approach,but instead of storing the containing triangle of each unprocessed node,we store the nearest triangulation node.This results in both less storage and improved efficiency.
Since our search procedure begins with an arbitrarily specified triangu-lation node,we obtain constant search time by maintaining the nearest triangulation node to each unprocessed node.The data structure consists of three length-N arrays:NEAR,NEXT,and DIST.For each unprocessed node I, the index of the nearest triangulation node and its distance are stored in NEAR(I)and DIST(I).For each triangulation node J,the set of unproc-essed nodes in J’s Voronoi region(those having J as nearest triangulation node)are stored as a linked list in NEAR and NEXT.The linked list uses the nodal indexes as links and includes a zero terminator.The sequence is thus I1?NEAR(J),I2?NEXT(I1),I3?NEXT(I2),...,0?NEXT(Ii).The triangulation and nearest-node data structures are initialized with a triangulation consisting of a single triangle,and the remaining N?3 nodes are added one at a time.Following the insertion of node K,only the unprocessed nodes associated with a neighbor J of node K need to be
Algorithm772:STRIPACK?427
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
considered for a move from J ’s set to K ’s set of unprocessed nodes (since the nearest node to K is a neighbor of K in the Delaunay triangulation).Since the N ?k unprocessed nodes are distributed over k sets,the average set size is ?N ?k ?/k ,and the expected total time complexity is
O ??k ?1N N ?k k ??O ?
N ?k ?1N 1k ?N ??O ?N log N ?.
Since only relative distances between nodes are needed,we obtain an improvement in efficiency (a smaller constant in the N log N term)by using an increasing function of distance:the distance ?between nodes p i and p j is replaced by ?cos ??????p i ,p j ?.In order to empirically verify the expected time complexity,we tabulated triangulation times T ?N ?for N randomly generated nodes with N ?5000,10,000,15,000,...,80,000,and we plotted the sequence of 16points ?N ,T ?N ?/?N log N ??.The sequence was slowly increasing but clearly asymptotic to a constant.The tests were run on a 200MHz Pentium Pro processor using the Lahey F77L3Fortran compiler (with a 32-bit DOS extender).The time required for N ?80,000was 9.26seconds.(The same test on a 133MHz Pentium machine required 28.4seconds.)The nodes were obtained by using a pseudorandom-number generator to get points uniformly distributed in the cube [–1,1]3and then normalizing the points to unit vectors.
5.SOFTWARE
The software package is described in the following four subsections:Usage,Data Structures,Organization of the Code,and Subprogram Descriptions.
5.1Usage
A driver named STRITEST is provided with the package.That program reserves storage,reads a set of nodal coordinates,calls subroutine TRMESH to construct the Delaunay triangulation and subroutine CRLIST to con-struct the Voronoi diagram,and prints the data structures.The call to CRLIST ,along with the statements that reserve storage for the Voronoi diagram,may be removed if only the triangulation is needed.
All information needed to use the package is contained in the header comments in the source code.Subroutine TRMESH includes brief descrip-tions of the additional subprograms that a user might wish to call directly.
5.2Data Structures
The triangulation data structure is essentially identical to that used by the planar triangulation package TRIPACK [Renka 1996].It consists of the number of nodes N ,type REAL arrays X ,Y ,and Z of length N containing the Cartesian coordinates of the nodes,and a linked list requiring approxi-428?Robert J.Renka
ACM Transactions on Mathematical Software,Vol.23,No.3,September 1997.
Algorithm772:STRIPACK?429 mately13N storage locations and which contains the adjacency list(or-dered sequence of neighbors)for each node:
LIST Set of nodal indexes which,along with LPTR,LEND,and LNEW,define the triangulation as a set of N adjacency lists:counterclockwise-ordered sequences of neighboring nodes such that the first and last neighbors of a boundary node are boundary nodes(the first neighbor of an interior node is arbitrary).In order to distinguish between interior and boundary nodes,the last neighbor of each boundary node is represented by the negative of its index.
LPTR Set of pointers(LIST indexes)in one-to-one correspondence with the elements of LIST.LIST(LPTR(I))indexes the node that follows LIST(I)in cyclical counterclockwise order(the first neighbor fol-lows the last neighbor).
LEND Set of pointers to adjacency lists.LEND(K)points to the last neigh-bor of node K for K?1to N.Thus,LIST(LEND(K))?0if and only if K is a boundary node.
LNEW Pointer to the first empty location in LIST and LPTR(list length plus one).
Since LIST and LPTR contain two entries for each triangulation arc(each endpoint stored as a neighbor of the other),their length is L?2N a,and more generally
N t??2N?4if N b?0
2N?N b?2if N b?3?,
N a??3N?6if N b?0
3N?N b?3if N b?3?,
L??6N?12if N b?0
6N?2N b?6if N b?3?,
where
N?Number of nodes,
N b?Number of boundary nodes,
N t?Number of triangles,
N a?Number of arcs,and
L?Length of LIST/LPTR.
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
430?Robert J.Renka
Thus L?6N?12and the storage required for the linked list is less than13N.
The Voronoi diagram is obtained by implicitly extending the triangula-
tion to the entire surface(constructing a triangulation of the set of boundary nodes)if N b 0,computing the2N?4triangle circumcenters (Voronoi vertices)and circumradii,and storing a set of adjacency lists
similar to LIST,but containing triangle indexes instead of nodal indexes.
Subroutine CRLIST takes the triangulation data structure as input and
returns the following arrays:
XC,YC,ZC Type REAL arrays of length2N?4containing the
Cartesian coordinates of the triangle circumcenters(in-
cluding those associated with pseudotriangles as the
first N b?2entries).
RC Type REAL array of length2N?4containing circum-
radii in one-to-one correspondence with circumcenters.
LTRI Type INTEGER work space array of length6N
b?12
if N b 0.LTRI is used to store the triangulation of the
set of boundary nodes as a6-by-?N B?2?triangle
list,each column of which represents a triangle by its
vertex indexes and neighboring triangle indexes.This
is used internally to construct LISTC.
LISTC Array containing triangle indexes(indexes to XC,YC,
ZC,and RC)stored in one-to-one correspondence with
LIST/LPTR entries(or entries that would be stored in
LIST for the extended triangulation):the index of tri-
angle?p i,p j,p k?is stored in LISTC(K),LISTC(L),
and LISTC(M),where LIST(K),LIST(L),and LIST(M)
are the indexes of p j as a neighbor of p i,p k as a
neighbor of p j,and p i as a neighbor of p k.The Voronoi
region associated with a node is defined by the counter-
clockwise-ordered sequence of circumcenters in one-to-
one correspondence with its adjacency list(in the ex-
tended triangulation).
LPTR,LEND,LNEW Arrays of pointers updated for the addition of
pseudotriangles if the original triangulation contains
boundary nodes(N b 0).If N b 0and both the
triangulation and Voronoi diagram are needed,copies
of LPTR,LEND,and LNEW must be saved before calling
CRLIST.
5.3Organization of the Code
The code is written in1977ANSI Standard Fortran.All variable and array
names conform to the default typing convention:I–N for type INTEGER and ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
Algorithm772:STRIPACK?431 A–H or O–Z for type REAL.(There are no DOUBLE PRECISION variables.) There are35modules,and they are ordered alphabetically in the package. (The term module here refers to a subprogram rather than a Fortran90 module.)Each consists of the following sections:
—the module name and parameter list with spaces separating the param-eters into one to three subsets:input parameters,I/O parameters,and output parameters(in that order);
—type statements in which all parameters are typed and in which arrays are dimensioned;
—a heading with the name of the package,identification of the author,and date of the most recent modification to the source code;
—a description of the module’s purpose and other relevant information for the user;
—input parameter descriptions and output parameter descriptions in the same order as the parameter list;
—a list of other modules required(called either directly or indirectly);
—a list of intrinsic functions called,if any;and
—the code,beginning with type statements and descriptions of all local variables.
5.4Subprogram Descriptions
The package is comprised of the following modules.An asterisk appears before each module that the calling program(user)is expected to call directly.However,some of these modules are also called by other modules. Also,subprograms AREAS,CIRCLE,INSIDE,INTRSC,IRAND,PROJCT,SCO-ORD,STORE,and TRANS have applications independent of the triangulation package.
*ADDNOD Subroutine which updates the triangulation data structure with the addition of a new node.
*AREAS Real function which returns the area of a spherical triangle on the unit sphere.
BDYADD Subroutine called by ADDNOD to add a boundary node.
*BNODES Subroutine which returns an array containing the indexes of the boundary nodes in counterclockwise order.Counts of
boundary nodes,triangles,and arcs are also returned.
*CIRCLE Subroutine which returns the Cartesian coordinates of a se-quence of uniformly spaced points on the unit circle centered at
(0,0).
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
432?Robert J.Renka
*CIRCUM Subroutine which computes the circumcenter of a spherical triangle defined by user-specified vertices on the unit sphere.
COVSPH Subroutine called by ADDNOD to connect a new node to all boundary nodes when all boundary nodes are visible from the
new node.The nodal addition thus extends the convex hull of
the nodes to the entire surface.
*CRLIST Subroutine which constructs a Voronoi diagram from a Delau-nay triangulation.
*DELARC Subroutine which removes a boundary arc from a triangulation resulting in a nonconvex triangulation.
DELNB Subroutine called by DELARC and DELNOD to delete a neighbor from an adjacency list.
*DELNOD Subroutine which deletes a node from a triangulation,preserv-ing the circumcircle property.
*EDGE Subroutine which forces a pair of nodes to be adjacent by applying any necessary swaps.A sequence of calls to EDGE may
be used to force the presence of arcs defining the boundary of a
nonconvex and/or multiply connected region,or to introduce
barriers,resulting in a constrained Delaunay triangulation.
Note,however,that subsequent nodal additions may remove
some of the arcs.
*GETNP Subroutine which determines an ordered sequence of closest nodes to a given node,along with the associated distances.
INSERT Subroutine called by BDYADD,COVSPH,and INTADD to insert a neighbor into an adjacency list.
*INSIDE Logical function which locates a point relative to a polygonal region on the surface of the unit sphere.
INTADD Subroutine called by ADDNOD to add an interior node.
*INTRSC Subroutine called by INSIDE to find a point of intersection between a pair of great circles.
*IRAND Integer function which returns a uniformly distributed pseudo-random integer.This is used by TRFIND to select a starting
node for the search in the unlikely event that the default or
previously selected starting node results in failure.
LEFT Logical function called by DELNOD,EDGE,and TRMESH to locate
a point relative to a directed geodesic(which defines a left and
right hemisphere).
LSTPTR Integer function called by ADDNOD,CRLIST,DELARC,DELNOD, INTADD,NEARND,SWAP,and TRFIND to determine the LIST
index of a specified neighbor of a specified node.
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
Algorithm772:STRIPACK?433 NBCNT Integer function called by DELNOD to determine the number of neighbors of a specified node.
*NEARND Integer function which returns the index of the nearest node to an arbitrary point,along with its angular distance.
OPTIM Subroutine called by DELNOD and EDGE to optimize a portion of
a triangulation defined as the triangles that share a set of
specified interior arcs.
*PROJCT Subroutine which applies a depth-perspective transformation to a point in3-space.
*SCOORD Subroutine which converts a point from Cartesian coordinates to spherical coordinates.
*STORE Real function used by TRFIND in computing the machine preci-sion.It forces a value to be stored in main memory so that the
precision of floating-point numbers in memory locations rather
than registers is computed.
SWAP Subroutine called by ADDNOD,DELNOD,EDGE,and OPTIM to swap diagonal arcs in a convex quadrilateral defined by a pair
of adjacent triangles.
SWPTST Logical function called by ADDNOD,CRLIST,and OPTIM to apply the swap test(local circumcircle test)to an interior arc.
*TRANS Subroutine which transforms spherical coordinates into Carte-sian coordinates on the unit sphere.
*TRFIND Subroutine called by ADDNOD and NEARND to locate a point relative to the triangulation.
*TRLIST Subroutine which converts the linked list triangulation data structure to a triangle list.
*TRLPRT Subroutine which prints the triangle list created by Subroutine TRLIST.
*TRMESH Subroutine which creates a Delaunay triangulation.
*TRPLOT Subroutine which,when linked to a user-supplied graphics package,creates a graphical display of a triangulation.
*TRPRNT Subroutine which prints the triangulation data structure.
REFERENCES
A UGENBAUM,J.M.AND P ESKIN,C.S.1985.On the construction of the Voronoi mesh on a https://www.doczj.com/doc/a812988471.html,put.Phys.59,177–192.
B ARBER,C.B.,D OBKIN,D.P.,AND H UHDANPAA,H.1996.The Quickhull algorithm for convex hulls.ACM Trans.Math.Softw.22,4(Dec.),469–483.
C LINE, A.K.AN
D R ENKA,R.J.1984.A storage-efficient method for construction of a Thiessen triangulation.Rocky Mt.J.Math.14,1,119–139.
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
434?Robert J.Renka
C LINE,A.K.AN
D R ENKA,R.J.1990.A constrained two-dimensional triangulation and the solution of closest node problems in the presence of barriers.SIAM J.Numer.Anal.27,5 (Oct.),1305–1321.
D ELAUNAY,B.1934.Sur la sphère https://www.doczj.com/doc/a812988471.html,SR7,793–800.
F OHLMEISTER,J.F.AND R ENKA,R.J.1994.Hotspots,mantle convection and plate tectonics: A synthetic calculation.Pure Appl.Geophys.143,673–695.
F OHLMEISTER,J. F.,R ENKA,R.J.,AND S TOUT,J.H.1990.Lithospheric plate motions predicted by a quantitative theory.Trans.Am.Geophys.Union71,43(Oct.).
G UIBAS,L.J.,K NUTH,D.E.,AND S HARIR,M.1992.Randomized incremental construction of Delaunay and Voronoi diagrams.Algorithmica7,381–413.
L AWSON,C.L.1977.Software for C1surface interpolation.In Mathematical Software III, J.R.Rice,Ed.Academic Press,Inc.,Orlando,FL,161–194.
L AWSON,C.L.1984.C1surface interpolation for scattered data on a sphere.Rocky Mt.J. Math.14,1,177–202.
P REPARATA, F.P.AND S HAMOS,https://www.doczj.com/doc/a812988471.html,putational Geometry:An Introduction. Springer texts and monographs in computer science.Springer-Verlag New York,Inc.,New York,NY.
R ENKA,R.J.1984a.Interpolation of data on the surface of a sphere.ACM Trans.Math. Softw.10,4(Dec.),417–436.
R ENKA,R.J.1984b.Algorithm623:Interpolation on the surface of a sphere.ACM Trans. Math.Softw.10,4(Dec.),437–439.
R ENKA,R.J.1996.Algorithm751:TRIPACK:Constrained two-dimensional Delaunay tri-angulation package.ACM Trans.Math.Softw.22,1(Mar.),1–8.
R ENKA,R.J.1997.Algorithm773:SSRFPACK:Interpolation of scattered data on the surface of a sphere with a surface under tension.ACM Trans.Math.Softw.23,3(Sept.). This issue.
R HYNSBURGER, D.1973.Analytic delineation of Thiessen polygons.Geograph.Anal.5, 133–144.
S IBSON,R.1978.Locally equiangular https://www.doczj.com/doc/a812988471.html,put.J.21,243–245.
V ORONOI,G.1908.Nouvelles applications des parametres continuisàla theorie des formes quadratiques:Deuxième mémorie:Recherches sur les paralléloèdres primitifs.J.Reine Angew Math.134,198–287.
Received:July1995;revised:August1996;accepted:March1997
ACM Transactions on Mathematical Software,Vol.23,No.3,September1997.
基于协同过滤的推荐算法与代码实现 什么是协同过滤？ 协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤(Collaborative Filtering, 简称CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。 协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。当然其中有一个核心的问题： 如何确定一个用户是不是和你有相似的品位？ 如何将邻居们的喜好组织成一个排序的目录？ 简单来说： 1. 和你兴趣合得来的朋友喜欢的，你也很有可能喜欢； 2. 喜欢一件东西A，而另一件东西B 与这件十分相似，就很有可能喜欢B； 3. 大家都比较满意的，人人都追着抢的，我也就很有可能喜欢。 三者均反映在协同过滤的评级（rating）或者群体过滤（social filtering）这种行为特性上。 深入协同过滤的核心 首先，要实现协同过滤，需要一下几个步骤： 1. 收集用户偏好 2. 找到相似的用户或物品 3. 计算推荐 (1)收集用户偏好 要从用户的行为和偏好中发现规律，并基于此给予推荐，如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多方式向系统提供自己的偏好信息，而且不同的应用也可能大不相同，下面举例进行介绍：
以上列举的用户行为都是比较通用的，推荐引擎设计人员可以根据自己应用的特点添加特殊的用户行为，并用他们表示用户对物品的喜好。 在一般应用中，我们提取的用户行为一般都多于一种，关于如何组合这些不同的用户行为，基本上有以下两种方式： 将不同的行为分组：一般可以分为“查看”和“购买”等等，然后基于不同的行为，计算不同的用户/物品相似度。类似于当当网或者Amazon 给出的“购买了该图书的人还购买了...”，“查看了图书的人还查看了...”
三维互动平台系统 1.系统概况 三维互动平台以三维影像、二维动画、互动行为集合的展示系统，通过三维仿真技术及友好简单的操作界面，清晰全面进一步提高房地产营销效果，从传统的人与人交流，转变为人与信息的互动，让消费者获取开发商已设定的商业内容。 ［系统概念］互动展示系统集合了三维影像、二维动画、室内虚拟现实、互动行为等等多种媒体展示优势的互动传播平台。并将重点放在全面整合讯息传播方式，并提供有效的互动行为，在设定的媒介渠道上让消费者获悉自己想要的咨询。 ［系统平台］新媒体交互操作，全新的展示手段吸引看楼者，颠覆常规营销宣传手法，建立开发商与消费者沟通新渠道，它是连接销售人员和顾客的桥梁。 手指触及之处每每带来新意，在互动之间获悉一切讯息。
［产品优势］拥有动画的精美画质、沙盘的全局感受和三维游戏的全方位互动体验。直观、全面、身临其境地体验室内装修、建筑外观设计，进一步提升产品整体形象。 2.系统开发 在三维互动平台系统建设中，我们结合强大的三维资源，以高度仿真三维视觉技术呈
现产品的建筑空间设计；系统展示效果不再是以往的静态静止图，结合多媒体触摸屏技术，我们采用了更多互动行为，从城市区域沙盘到户型室内空间都以三维景观仿真技术实现，通过手指拖动可360度观看沙盘及建筑各个角度，在室内空间方面三维仿真技术更是细腻逼真，每个细节真实、全面，形如亲临现场；信息处理方面，摆脱以往信息系统的单一文字表格形式和单一按钮点击操作，信息以视像化归类处理，架构清晰明了，以手指拨动操作选择相关信息更添趣味性。 ［系统功能］互动系统以实景图片、效果图、影像视频、文字资讯等多种媒体结合形式对产品进行介绍：包括城市区域沙盘、项目建筑沙盘、标准户型展示、室内虚拟漫游、商家楼书互动，通过菜单操作方式，可自由进行操控，自主选择阅读内容，交互体验简单明了，精准无误。 ［开发技术］根据建设的范围、周期和难易程度，从技术路线上分成三大部分的内容：(1).程序架构的互动系统：采用Action Script程序、Flash制作系统程序架构； (3).形像平面设计：Photoshop、IllustratorCS3、CorelDRAW12制作平面内容 (2).三维仿真数码影像：采用3ds Max、Premiere、After Effects制作三维立体影像。 系统开发工具包括有： 程序架构Action Script 二维动画Flash 图象处理PhotoshopCS3、IllustratorCS3、CorelDRAW12 三维图像3DMX 影像数据After Effects、Premiere
Hans Journal of Data Mining 数据挖掘, 2019, 9(3), 81-87 Published Online July 2019 in Hans. https://www.doczj.com/doc/a812988471.html,/journal/hjdm https://https://www.doczj.com/doc/a812988471.html,/10.12677/hjdm.2019.93010 Overview and Prospect of Personalized Recommendation Algorithm Xinxin Li Dalian University of Foreign Languages, Dalian Liaoning Received: Jun. 19th, 2019; accepted: Jul. 2nd, 2019; published: Jul. 9th, 2019 Abstract In recent years, the word “information overload” frequently appears in people’s vision, it has be-come a hot word in the field of computer, and it is also an important problem that researchers ur-gently need to solve. In order to solve the problem of information overload, researchers in the field of computer constantly optimize the personalized recommendation algorithm, strive to re-duce the difficulty of information retrieval for users, to provide users with the best personalized recommendation results. This paper gives a brief overview of the personalized recommendation methods which are widely used and common. Combined with the experience of using personalized recommendation algorithm to generate results in daily life, the author puts forward expectations for the development of personalized recommendation algorithm in the future. Keywords Personalized Recommendation, Collaborative Filtering, Hybrid Recommendation 个性化推荐算法概述与展望 李鑫欣 大连外国语大学，辽宁大连 收稿日期：2019年6月19日；录用日期：2019年7月2日；发布日期：2019年7月9日 摘要 近年来，“信息过载”一词频繁出现在人们的视野中，它成为了计算机相关领域中的热门词汇，同时它也是研究人员急待解决的重要问题。为解决信息超载的问题，计算机领域研究人员不断优化个性化推荐
计算几何课程设计报告 基于Voronoi图的简单多边形骨架提取
引言 骨架（Skeleton）又称中轴（Medial Axis），通常使用烧草模型和最大球（圆）模型来描述。骨架有着与原物体相同的拓扑和形状信息，是一种性能优良的几何特征，能够有效的描述物体，因此，在物体识别、路径规划、医学工程等领域多有应用。在物体识别等应用领域里，骨架提取的输入可以看作是空间内的点构成的多边形，对于多边形的骨架提取也成为了这些应用的基本技术，具有重要的应用意义。在此次课程设计中，我们实现了基于Voronoi 图的任意多边形的骨架提取，并提供了多边形骨架提取的演示界面。 多边形骨架 一个多边形的骨架，如上图所示，可以看作是由无数点对之间的骨架点组成的。两点间的骨架（skeleton）（等同于对中轴(medial axis)的求取）是到两点距离相等的点的轨迹，它是两点连线的垂直平分线，每一点所邻接的半平面是到其距离最小的点集相应地可扩展为离散点集的中轴定义。它是下列性质点的轨迹：其上任一点到最近两离散点距离相等，相应地也产生各点到其距离最小的点集；两线间的中轴是到两线距离相等的点的轨迹，它在两线相交时为角平分线——两线平行时为到两线距离——的平行线，每一线所邻接并以中轴为界的区域是到其距离最小的点集。一线和一点间的中轴是到该点(线距离相等的点的轨迹,它是以该点为焦点、该线为准线的抛物线。该点或线所邻接并以中轴为界的区域是到其距离最小的点集。 多边形骨架的几何算法 多边形骨架（中轴）的几何算法，是由多边形的某一点开始，找出参与中轴线计算的相应的线段与线段、点与线段、点与点，实质都转化为求某个特定点（中轴转折点）的问题，
基于内容的推荐算法（Content-Based Recommendation）1.基本思想 基本思想就是给用户推荐与他们曾经喜欢的项目内容相匹配的新项目。 基于内容的推荐的基本思想是：对每个项目的内容进行特征提取(FeatureExtraction)，形成特征向量(Feature Vector)；对每个用户都用一个称作用户的兴趣模型(User Profile)的文件构成数据结构来描述其喜好；当需要对某个用户进行推荐时，把该用户的用户兴趣模型同所有项目的特征矩阵进行比较得到二者的相似度，系统通过相似度推荐文档。 （基于内容的推荐算法不用用户对项目的评分，它通过特定的特征提取方法得到项目特征用来表示项目，根据用户所偏好的项目的特征来训练学习用户的兴趣模型，然后计算一个新项目的内容特征和用户兴趣模型的匹配程度，进而把匹配程度高的项目推荐给用户。） 2.基于内容的推荐层次结构图：
CB的过程一般包括以下三步： （1）Item Representation：为每个item抽取出一些特征（也就是item的content 了）来表示此item；对应着上图中的Content Analyzer。 （2）Profile Learning：利用一个用户过去喜欢（及不喜欢）的item的特征数据，来学习出此用户的喜好特征（profile）；对应着上图中的Profile Learner。 （3）Recommendation Generation：通过比较上一步得到的用户profile与候选item 的特征，为此用户推荐一组相关性最大的item。对应着上图中的Filtering Component。 3.详细介绍上面的三个步骤： 3.1 Item Representation 项目表示：对项目进行特征提取，比如最著名的特征向量空间模型，它首先将一份文本（项目）以词袋形式来表示，然后对每一个词用词频-逆向文档频率（TF-IDF）来计算权重，找出若干权重较大的词作为关键词（特征）。每个文本（项目）都可以表示成相同维度的一个向量 TF-IDF词频-逆文档频率计算： TF 词项t在文档d中出现的次数，df 表示词项t在所有文档出现的次数，idf 为反向文档频率，N为文档集中所有文档的数目。 TF-IDF公式同时引入词频和反向文档频率，词频TF表示词项在单个文档中的局部权重，某一词项在文档中出现的频率越高，说明它区分文档内容的属性越强，权重越大。IDF表示词项在整个文档集中的全局权重，某一词项在各大文档都有出现，说明它区分文档类别属性的能力越低，权值越小。
一、单通道三维立体投影显示系统 单通道三维立体投影显示系统是一套基于高端PC 虚拟现实工作站平台的入门级虚拟现实三维投影显示系统，该系统通常以一台图形计算机为实时驱动平台，两台叠加的立体版专业LCD或DLP投影机作为投影主体显示一幅高分辨率的立体投影影像，所以通常又称之为单通道立体投影系统。我们采用成熟的偏振光成像技术或世界最先进的光谱分离立体成像技术来生成单通道立体图像。 采用光谱分离立体成像技术最大的优点是三维立体图像色彩饱和度更高、立体感更强，为虚拟仿真用户提供一个有立体感的沉浸式虚拟三维显示和交互环境，同时也可以显示非立体影像，而由于虚拟仿真应用的特性和要求，通常情况下均使用其立体模式。 在虚拟现实应用中用以显示实时的虚拟现实仿真应用程序，该系统通常主要包括专业投影显示系统、悬挂系统、成像装置等三部分，在众多的虚拟现实三维显示系统中，单通道立体投影系统是一种低成本、操作简便、占用空间较小（可选择正投或背投）具有极好性能价格比的小型虚拟三维投影显示系统，其集成的显示系统使安装、操作使用更加容易方便，被广泛应用于高等院校和科研院所的虚拟现实实验室中。投影系统是正投或背投，应该依据展示空间面积大小与实际需要来选择。正投系统更为紧凑，占用的空间更小，投影幕墙具有较好的稳定性。背投主要适用于空间比较大，而且投影前需要讲解人的场合。由于光线从另一侧打在投影幕上，讲解人不会挡住光线，也不会被强烈的光线损伤视力。 系统结构示意图
二、双通道立体投影显示系统 为了拓宽观察视角，满足控制室与演示中心多面板现实的需要，我们使用两套立体投影设备拼接成为宽幅面的双通道平板立体显示系统。 双通道显示系统的宽度适宜进行平 板显示（如果是更大的视角，使用柱面环 幕则更有利于产生视野封闭的巨大沉浸 感。） 对于双通道立体投影显示系统而言， 各通道间的亮度与色彩平衡也是至关重 要的技术要求。目前通常采用偏振立体成 像技术实现被动式三维立体成像，就是在 输出左右立体像对的两台高亮度的LCD 或DLP投影机前安装具有不同极化方向 的偏振片。但其所使用的投影幕必须是具 有高增益指数的金属投影幕，而且投影幅 面一般应该控制在150英寸范围以内，否则在不同的视点观看时会出现因高增益而引起的“太阳效应”，所以不适用于多通道立体投影显示系统。目前，一种全新的基于光学虑波的技术成功解决了这个问题，它就是来自德国的Infitec plus，Infitec plus是目前世界最先进的立体成像技术，中铭科技推出的多通道虚拟现实系统正是基于该项技术的一套完美的多通道虚拟现实投影显示系统解决方案。 偏振技术成像的太阳效应Infitec立体成像技术的效果Infitec技术（干涉滤波技术）采用高质量滤光技术，分离光谱以便适合人的每只眼睛，生成无重像的被动立体图像，所以，无需特殊的具有偏振特性的屏幕或电子眼镜，只需配戴专业Infitec眼镜即可，Infitec 眼镜不需要配备电源和复杂 的电路，因此舒适感和沉浸 感更好，眼镜轻便，由于不 需信号同步发射器，所以配 戴者的头部可随意移动，配 戴者互相之间不会产生干 扰，这样Infitec还可以满足 有大量观众场合的应用。
Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形 ◆Delaunay 三角网的定义: 由一系列相连的但不重叠的三角形的集合, 而且这些 三角形的外接圆不包含这个面域的其他任何点。 ◆Voronoi图的定义： Voronoi图把平面分成N 个区，每一个区包括一个点， 该点所在的区域是距离该点最近的点的集合。 ◆Delaunay三角网的特性： ◆不存在四点共圆； ◆每个三角形对应于一个Voronoi图顶点； ◆每个三角形边对应于一个Voronoi图边； ◆每个结点对应于一个Voronoi图区域； ◆Delaunay图的边界是一个凸壳； ◆三角网中三角形的最小角最大。 空外接圆准则最大最小角准则最短距离和准则 在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成 的凸四边形中，这两三角形 中的最小内角一定大于交换 凸四边形对角线后所形成的 两三角形的最小内角 一点到基边的两端的距离 和为最小 Delaunay三角剖分的重要的准则
张角最大准则面积比准则对角线准则 一点到基边的张角为最大三角形内切圆面积与三角形 面积或三角形面积与周长平 方之比最小 两三角形组成的凸四边形 的两条对角线之比。这一 准则的比值限定值，须给 定，即当计算值超过限定 值才进行优化 Delaunay三角剖分的重要的准则 不规则三角网(TIN)的建立 ●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。 ●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。 方法说明方法实例 收缩生长算法先形成整个数据域的数据边界（凸壳）， 并以此作为源头，逐步缩小以形成整个三 角网 分割合并算法 逐点插入算法 扩张生长算法从一个三角形开始向外层层扩展，形成覆 盖整个区域的三角网 递归生长算法
推荐系统的出现 推荐系统的任务就是解决，当用户无法准确描述自己的需求时，搜索引擎的筛选效果不佳的问题。联系用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对他感兴趣的人群中，从而实现信息提供商与用户的双赢。 推荐算法介绍 基于人口统计学的推荐 这是最为简单的一种推荐算法，它只是简单的根据系统用户的基本信息发现用户的相关程度，然后将相似用户喜爱的其他物品推荐给当前用户。 系统首先会根据用户的属性建模，比如用户的年龄，性别，兴趣等信息。根据这些特征计算用户间的相似度。比如系统通过计算发现用户A和C比较相似。就会把A喜欢的物品推荐给C。 优缺点： ?不需要历史数据，没有冷启动问题 ?不依赖于物品的属性，因此其他领域的问题都可无缝接入。 ?算法比较粗糙，效果很难令人满意，只适合简单的推荐 基于内容的推荐 与上面的方法相类似，只不过这次的中心转到了物品本身。使用物品本身的相似度而不是用户的相似度。
系统首先对物品（图中举电影的例子）的属性进行建模，图中用类型作为属性。 在实际应用中，只根据类型显然过于粗糙，还需要考虑演员，导演等更多信息。 通过相似度计算，发现电影A和C相似度较高，因为他们都属于爱情类。系统还会发现用户A喜欢电影A，由此得出结论，用户A很可能对电影C也感兴趣。 于是将电影C推荐给A。 优缺点： ?对用户兴趣可以很好的建模，并通过对物品属性维度的增加，获得更好的推荐精度 ?物品的属性有限，很难有效的得到更多数据 ?物品相似度的衡量标准只考虑到了物品本身，有一定的片面性 ?需要用户的物品的历史数据，有冷启动的问题 协同过滤 协同过滤是推荐算法中最经典最常用的，分为基于用户的协同过滤和基于物品的协同过滤。那么他们和基于人口学统计的推荐和基于内容的推荐有什么区别和联系呢？ 基于用户的协同过滤——基于人口统计学的推荐 基于用户的协同过滤推荐机制和基于人口统计学的推荐机制都是计算用户的相似度，并基于“邻居”用户群计算推荐，但它们所不同的是如何计算用户的相似度，基于人口统计学的机制只考虑用户本身的特征，而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度，它的基本假设是，喜欢类似物品的用户可能有相同或者相似的口味和偏好。 基于物品的协同过滤——基于内容的推荐
Computer Science and Application 计算机科学与应用, 2019, 9(9), 1803-1813 Published Online September 2019 in Hans. https://www.doczj.com/doc/a812988471.html,/journal/csa https://https://www.doczj.com/doc/a812988471.html,/10.12677/csa.2019.99202 Review of Classical Recommendation Algorithms Chunhua Zhou, Jianjing Shen, Yan Li, Xiaofeng Guo Information Engineering University, Zhengzhou Henan Received: Sep. 3rd, 2019; accepted: Sep. 18th, 2019; published: Sep. 25th, 2019 Abstract Recommender systems are effective tools of information ?ltering that are prevalent due to cont i-nuous popularization of the Internet, personalization trends, and changing habits of computer us-ers. Although existing recommender systems are successful in producing decent recommend a-tions, they still suffer from challenges such as cold-start, data sparsity, and user interest drift. This paper summarizes the research status of recommendat ion system, presents an overview of the field of recommender systems, describes the classical recommendation methods that are usually classified into the following three main categories: content-based, collaborative and hybrid recommendation algorithms, a nd prospects future research directions. Keywords Recommender Systems, Cold-Start, Data Sparsity, Collaborative Filtering 经典推荐算法研究综述 周春华，沈建京，李艳，郭晓峰 信息工程大学，河南郑州 收稿日期：2019年9月3日；录用日期：2019年9月18日；发布日期：2019年9月25日 摘要 推荐系统作为一种有效的信息过滤工具，由于互联网的不断普及、个性化趋势和计算机用户习惯的改变，将变得更加流行。尽管现有的推荐系统也能成功地进行推荐，但它们仍然面临着冷启动、数据稀疏性和用户兴趣漂移等问题的挑战。本文概述了推荐系统的研究现状，对推荐算法进行了分类，介绍了几种经
0引言 对于静态数据三角化(数据点不能动态插入与删除)，有许多D-三角网构建算法[1-5]；对于动态的点插入，使用逐点插入的方法进行动态局部更新；对于动态的点删除，使用的方法有两种，一是基于凸耳权值的点删除方法[6-7]，二是基于空外接圆准则和凸耳性质的点删除方法[8-9]，上述两种方法都是基于凸耳删除的方法，存在难以理解或算法效率差的缺点。本文提出了一种数据结构来存储D-三角网和表现其拓扑关系，对其中的点删除算法进行了改进，可实现D-三角网中数据点的快速删除操作。 1存储结构 对于三角格网的存储结构，本文设计了点、有向边的存储 表示，三角形的信息在有向边的遍历中隐含，其C++实现如下： Class Point2d {double x,y;} Class Edge { Public:Int num;Edge* next;Edge* prev; Point2d*data;Edge (){data =0;} Edge*Sym (){return (num<1)?this+1:this-1;}Edge*Onext (){return next;}Edge*Oprev (){return prev;} void EndPoints (Point2d*or,Point2d*de ){data =or;Sym ()->data =de;} TwinEdge*Tedge (){return (TwinEdge *)(this -num );}}; Class TwinEdge {Private:Edge e [2];Public:TwinEdge (){ e [0].num =0;e [0].next =&(e [0]);e [1].num =1;e [1].next =&(e [1]); 收稿日期：2007-03-01E-mail ：mengl@https://www.doczj.com/doc/a812988471.html, 基金项目：国家863高技术研究发展计划基金项目(2002AA114020、2001AA135210)；中国科学院知识创新基金项目(20036020)。 作者简介：孟亮(1968－)，男，山西临汾人，博士研究生，研究方向为GIS 、计算机图形学；方金云(1968－)，男，山东青岛人，博士，副研究员，研究方向为海量空间数据处理关键支撑技术、网格GIS 等；唐志敏(1966－)，男，江苏江阴人，研究员，博士生导师，研究方向为计算机系统结构、网络并行处理。 Delaunay 三角网表示和点删除方法 孟 亮，方金云，唐志敏 (中国科学院计算技术研究所，北京100080) 摘 要：对于三角网的表示方法，提出了一种双循环链表结构，这种结构能够方便的表示三角网的边拓扑和面拓扑信息，以及多边形结构。基于这种结构，对三角网点删除算法进行了改进。以前的点删除算法是基于连续的凸耳删除，提出的方法是基于多边形边的构建方法，利用D-三角网的空外接圆属性。与其它方法相比，这种方法具有容易理解，效率高的优点。关键词：Delaunay 三角网;凸耳;点删除;拓扑结构;双循环链表中图法分类号：TP391;P208 文献标识码：A 文章编号：1000-7024(2008)03-0738-03 Delaunay TIN expression and point deletion method MENG Liang, FANG Jin-yun, TANG Zhi-min (Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100080,China ) Abstract ：As to representation of triangulated irregular network (TIN ),a dual-circulation linked list structure is proposed,this structure can conveniently express edge and plane topology information of triangulated irregular network,and polygon structure.Based on this structure,improvements are achieved about TIN point deletion algorithm.Previous point deletion algorithm is based on continuous ears deletion,the methods proposed is based on edge construction method of polygon,using Delaunay TIN circumcircle https://www.doczj.com/doc/a812988471.html,pared with other methods,this method has the advantage of easy understanding,higher efficiency. Key words ：Delaunay triangulated irregular network;ears;point deletion;topology structure;dual-circulation linked list 2008年2月计算机工程与设计 Feb.2008 第29卷第3期Vol.29 No.3 Computer Engineering and Design
一般图形Voronoi图的离散生成
————————————————————————————————作者：————————————————————————————————日期：
一般图形Voronoi图的离散生成-工程论文 一般图形Voronoi图的离散生成 刘欣LIU Xin （承德石油高等专科学校社科与数理部，承德067000）（Department of Social Science and Mathematics，Chengde Petroleum College，Chengde 067000，China） 摘要：由于一般图形形状和位置的任意性，一般图形Voronoi图往往比较复杂，难以将传统的构造法直接应用到一般图形Voronoi图的构造中。本文介绍了一般图形Voronoi图的离散构造法，并给出算法步骤及优势分析。Abstract：Because of the random graph shape and position，the general Voronoi graph is often more complex，it is difficult to construct the traditional method of direct application to the general structure of Voronoi graph. This paper introduces the construction method of general discrete Voronoi graph，and puts forword the algorithm steps and its advantages. 关键词：一般图形；Voronoi图；离散生成 Key words：general graphs；Voronoi diagram；discrete generation 中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2015）19-0162-02 基金项目：河北省高等学校科学技术研究项，编号为QN20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数
1. 前言 随着互联网技术和社会化网络的发展，每天有大量包括博客，图片，视频，微博等等的信息发布到网上。传统的搜索技术已经不能满足用户对信息发现的需求，原因有多种，可能是用户很难用合适的关键词来描述自己的需求，也可能用户需要更加符合他们兴趣和喜好的结果，又或是用户无法对自己未知而又可能感兴趣的信息做出描述。推荐引擎的出现，可以帮用户获取更丰富，更符合个人口味和更加有意义的信息。 个性化推荐根据用户兴趣和行为特点，向用户推荐所需的信息或商品，帮助用户在海量信息中快速发现真正所需的商品，提高用户黏性，促进信息点击和商品销售。推荐系统是基于海量数据挖掘分析的商业智能平台，推荐主要基于以下信息： ●热点信息或商品 ●用户信息，如性别、年龄、职业、收入以及所在城市等等 ●用户历史浏览或行为记录 ●社会化关系 2. 个性化推荐算法 2.1. 基于人口统计学的推荐（同类人喜欢什么就推荐什么） 基于人口统计学的推荐机制（Demographic-based Recommendation）是一种最易于实现的推荐方法，它只是简单的根据系统用户的基本信息发现用户的相关程度，然后将相似用户喜爱的其他物品推荐给当前用户。 首先，系统对每个用户都有一个用户 Profile 的建模，其中包括用户的基本信息，例如用户的年龄，性别等等；然后，系统会根据用户的 Profile 计算用户的相似度，可以看到用 户 A 的 Profile 和用户 C 一样，那么系统会认为用户 A 和 C 是相似用户，在推荐引擎中，可以称他们是“邻居”；最后，基于“邻居”用户群的喜好推荐给当前用户一些物品。 这种基于人口统计学的推荐机制的好处在于： ●因为不使用当前用户对物品的喜好历史数据，所以对于新用户来讲没有“冷启动（Cold Start）”的问题。 ●这个方法不依赖于物品本身的数据，所以这个方法在不同物品的领域都可以使用，它是领域独立的（domain-independent）。 然后，这个方法的缺点和问题就在于，这种基于用户的基本信息对用户进行分类的方法过于粗糙，尤其是对品味要求较高的领域，比如图书，电影和音乐等领域，无法得到很好的推荐效果。另外一个局限是，这个方法可能涉及到一些与信息发现问题本身无关却比较敏感的信息，比如用户的年龄等，这些用户信息不是很好获取。 2.2. 基于内容的推荐（用户喜欢什么，就推荐相同类型的） 基于内容的推荐是在推荐引擎出现之初应用最为广泛的推荐机制，它的核心思想是根据推荐物品或内容的元数据，发现物品或者内容的相关性，然后基于用户以往的喜好记录，推荐给用户相似的物品。这种推荐系统多用于一些资讯类的应用上，针对文章本身抽取一些tag作为该文章的关键词，继而可以通过这些tag来评价两篇文章的相似度。
三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。 然后有两个问题要解决：
1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路
泰森多边形(Voronoi图)生成算法
一、文档目的 本文描述了在geomodel模块中，生成泰森多边形所使用的算法。 二、概述 GIS和地理分析中经常采用泰森多边形进行快速插值，和分析地理实体的影响区域，是解决邻接度问题的又一常用工具。 荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图，或dirichlet图。 图1 泰森多边形 泰森多边形的特性是： ●每个泰森多边形内仅含有一个离散点数据 ●泰森多边形内的点到相应离散点的距离最近 ●位于泰森多边形边上的点到其两边的离散点的距离相等 泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。 在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。 三、Delaulay三角形的构建 Delaunay三角网的构建也称为不规则三角网的构建，就是由离散数据点构建三角网，如图2，即确定哪三个数据点构成一个三角形，也称为自动联接三角网。即对于平面上n个离散点，其平面坐标为(x i，y i)，i＝1，2，…，n，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。 图2 Delaunay三角网
推荐算法实施方案 一、目的 为了使平台功能更加多样化，多方面满足平台用户的需求，配合目前流行的机器学习方法，增加推荐功能，使用python实现推荐算法，通过用户的详细信息和使用习惯，智能化推送平台相关内容，实现用户个性化定制，带动平台发展，最大程度化推广平台。 二、运用场景 场景1：基于超市平台，根据企业的经营范围、简介、地域等相关信息，通过计算平台上所有机构与该企业相关信息的相似性，将匹配度高的服务机构推荐给该企业。 场景2：基于超市平台，省平台根据需求列表，通过计算需求的内容和供给资源内容的相似度，将相似度高的资源展示在该需求旁，同理技术资源也可如此展示。 场景3：基于智能制造平台，为了推荐符合企业需求的政策服务，可以提供中文分词技术，提取出政策中的关键词，并将其和企业所需的政策内容关键词进行匹配，推荐其相似度高的政策。 …… 三、流程规划
1． 数据收集：前期准备工作，收集大量相关数据，大规模数据能增加自主学习的准确率 公司简介（主要） 用户输入 地域 其他 数据构成 服务机构（主要） 平台功能 政策（主要） 供需 新闻、通知公告 其他 2． 数据清洗： 1）无效数据、空数据处理，格式标准统一； 2）挑选有分析价值的数据，以公司简介为例，描述字符要大于25个，后期会根据实验需求，对各类特征数据标准进行调整； 3）jieba 分词：将收集好的中文数据进行分词，此算法帮助去除一些无效字符，提取段落关键字，初步为相关对象打上关键字标签。 3． 数据分析： 根据处理好的信息，进行分析，比如地域分析，经营状况分析，还有分词后的关键字分析，目的主要是为了模型的特征提取。特征的可靠性越高，模型
总第２６１期 ２０１１年第７期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏｌ．３９Ｎｏ．７ ５７ 基于格网划分的Ｄｅｌａｕｎａｙ三角剖分算法研究＊ 李小丽 陈花竹 （河南大学软件学院 郑州 ４５００００） 摘 要 为了提高海量数据的Ｄｅｌａｕｎａｙ三角网的构网速度，本文采用格网划分的三角剖分方法，首先将数据按照线性四叉树方式划分为若干格网块，构建块内子三角网，然后按照自下而上的合并方式对块进行合并，形成全局Ｄｅｌａｕｎａｙ三角网。在此基础上，为了避免出现过小锐角的情况，通过加入约束角来对三角格网进行优化。 关键词 Ｄｅｌａｕｎａｙ；格网划分；约束角 中图分类号 ＴＰ３０１．６ Ｓｔｕｄｙｏｆ Ｍａｓｓｉｖｅ Ｄａｔａ ＤｅｌａｕｎａｙＴｒｉａｎｇｕｌａｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｇｒｉｄ Ｐａｒｔｉｔｉｏｎ Ｍｅｔｈｏｄ Ｌｉ Ｘｉａｏｌｉ Ｃｈｅｎ Ｈｕａｚｈｕ （Ｓｏｆｔｗａｒｅ Ｃｏｌｌｅｇｅ，Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５００００） Ａｂｓｔｒａｃｔ Ｔｏ ｒａｉｓｅ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ｏｒｉｅｎｔｅｄ ｍａｓｓｉｖｅ ｄａｔａ，ｔｈｉｓ ｔｈｅｓｉｓ ｕｓｅｓ ｔｈｅｇｒｉｄ ｐａｒｔｉｔｉｏｎ ｍｅｔｈｏｄ．Ａｔ ｆｉｒｓｔ，ｉｔ ｄｉｖｉｄｅｓ ｔｈｅ ｄａｔａ ｉｎｔｏ ｃｅｒｔａｉｎ ｇｒｉｄ ｔｉｌｅｓ ｂｙ ｑｕａｄｔｒｅｅ ｍｅｔｈｏｄ，ｃｏｎｓｔｒｕｃｔｓ ｓｕｂ Ｄｅｌａｕｎａｙ ｔｒｉａｎ－ｇｕｌａｔｉｏｎ．Ｔｈｅｎ，ｉｔ ｍｅｒｇｅｓ ｔｗｏ ｔｒｉａｎｇｕｌａｔｉｏｎｓ ｆｒｏｍ ｂｏｔｔｏｍ ｕｐ ｔｏ ｆｏｒｍ ｔｈｅ ｗｈｏｌｅ Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｔｉｏｎ．Ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈａｔ，ｔｏ ａｖｏｉｄ ｐｒｏｄｕｃｉｎｇ ｔｏｏ ａｃｕｔｅ ａｎｇｌｅｓ，ｗｅ ｇｉｖｅ ａ ｔｈｒｅｓｈｏｌｄ ａｎｇｌｅ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｎｇｌｅｓ ｏｆ ｔｈｅ ｔｒｉａｎｇｕｌａｔｉｏｎ．Ｋｅｙ Ｗｏｒｄｓ Ｄｅｌａｕｎａｙ，ｇｒｉｄ ｐａｒｔｉｔｉｏｎ，ｔｈｒｅｓｈｏｌｄ ａｎｇｌｅ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３０１．６ １ 引言 Ｄｅｌａｕｎａｙ三角网在地形拟合、三维建模、有限元分析等方面应用广泛。并且它具有空外接圆、最小内角最大以及唯一性等重要性质，Ｄｅｌａｕｎａｙ三角网一直被公认为是优的三角剖分。经过长期的研究，国内外出现了大量算法，主要归纳为三类：逐点插入算法、三角网生长算法和分治算法。近年来随着Ｄｅｌａｕｎａｙ三角网在应用领域的不断拓展以及应用需求的不断深入，特别是对海量数据的管理和分析，已成为Ｄｅｌａｕｎａｙ三角剖分的一大研究热点，并出现了格网划分的的三角剖分思想［１］。本文在点插入算法和分治算法的基础上，采用格网划分的思想，对海量数据进行分块管理和构建，希望获得 较高的算法效率。并对加入了约束角的三角格网如何优化进行了分析。 ２ 基于格网划分的Ｄｅｌａｕｎａｙ三角剖分算法 随着科学技术的不断发展，海量数据的廉价获取已成为可能，而且目前人们在可视化方面的要求也越来越高，那么针对海量数据的管理和分析也越来越普遍。但是普通计算机仍无法满足对海量数据处理的要求，即便是硬件配置较高的计算机，当数据量达到一定程度后仍无法正常处理。怎么在普通计算机上进行海量数据的Ｄｅｌａｕｎａｙ三角网构建是一个亟待解决的问题［１］。本文采用基于格网划分的海量数据Ｄｅｌａｕｎａｙ三角剖分算法，通过分 ＊收稿日期：２０１１年１月９日，修回日期：２０１１年２月１７日 作者简介：李小丽，女，硕士研究生，助教，研究方向：地理信息系统。陈花竹，女，硕士研究生，助教，研究方向：偏微分方程的图像处理。