Name
Title | ||
|---|---|---|
An algorithm on discrimination of point-set in polyhedron based on three-dimensional convex hull |
Abstract | ||
|---|---|---|
This paper presents an algorithm to determine whether a point-set composed of n-points is in the polyhedron or not-which is called the convex hull method. With this method, it is not necessary to judge whether each point in a point set within a polyhedron. By constructing three-dimensional convex hull of the remain target points, by means of collision detection of spatial objects to judge the adjacency relations of the polyhedron and the three-dimensional convex hull of the point set, and then to judge whether the vertices of three-dimensional convex hull are within the polyhedron, or the vertices of polyhedron are within the three-dimensional convex hull, thus which points are spots within the polyhedron can be determined. The algorithm can be applied not only to a general polyhedron, but also to concave polyhedron. The efficiency of checking whether the three-dimensional point set is within the polyhedron can be greatly improved by this approach, which is an important support for the realization of real-time spatial analysis algorithm for three-dimensional Geographic Information System (3D GIS). The experimental results show that the algorithm is simple, reliable and highly efficient. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/GEOINFORMATICS.2010.5567834 | Geoinformatics |
Keywords | Field | DocType |
intersection detection,3d gis,point-set discrimination,three-dimensional point set,three-dimensional convex hull,geographic information systems,collision detection,computational geometry,polyhedron,three dimensional convex hull,spatial objects,geographic information system,gis,spatial analysis,convex hull,algorithm design and analysis,graphics,three dimensional,real time,construction industry | Combinatorics,Computer science,Polyhedron,Convex hull,Convex set,Algorithm,4-polytope,Convex polytope,Edge (geometry),Intersection of a polyhedron with a line,Face (geometry) | Conference |
ISBN | Citations | PageRank |
978-1-4244-7301-4 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yongzhi Wang | 1 | 0 | 0.34 |
| Yehua Sheng | 2 | 93 | 7.03 |
| Liangchen Zhou | 3 | 8 | 2.93 |
| Fei Guo | 4 | 1 | 1.37 |
| Yu Hu | 5 | 0 | 0.34 |