PINPOLYHEDRON:
This function is an implementation of a novel algorithm. It tests whether
points are inside/outside/on a polyhedron defined by triangular faces and
vertices. It can be used for various complicated models such as non-convex
volumes, multi-material bodies, and there is no assumption about orientation
of the face normals. Above all, the algorithm is very efficient especially
for large-scale problems.To the authors' best knowledge, it is the fastest
code in a large-scale setting.
SYNTAX:
output = pinpolyhedron (p,vertices,faces);
INPUT:
p : The points to be tested represented as an Nx3 matrix of XYZ coordinates,
e.g., [x1 y1 z1; x2 y2 z2; …].
vertices : The vertices of the polyhedron, in an Mx3 matrix of XYZ coordinates,
e.g., [x1 y1 z1; x2 y2 z2; …].
faces : The faces of the polyhedron, in an Mx3 matrix,
e.g., [a1,b1,c1; a2,b2,c2; ...].a b c are the index numbers of the three vertices
forming the triangular faces.
OUTPUT:
output : an Mx4 array. The first three columns are same as the input p.
The function set the fourth column as -1 and 0, standing for
outside or inside the polyhedron respectively ,and -2 stands for
p on the boundary.
ABOUT multi-material polyhedron:
A body may be composed of different materials, from which one can get a
multi-material polyhedron by triangulating its outer boundary and inner
boundaries between different materials.
Our algorithm can be used for multi-material polyhedrons too.
The syntax in this case is almost the same. However, the input of faces
should be an Mx5 matrix, e.g., [a1,b1,c1,m11, m12; a2,b2,c2,m21,m22; ...].
Here a b c are still index numbers of vertices, and m1 m2 are the two
materials on either side of a face.
Invoking the function in this way, it will indicate, for a point inside
the body, which material the point is in by setting the fourth column output
value as the material number. If a testing point is exactly on a triangular face,
whether the face is on the outer boundary or an inner one, the function
will set the output value as -2.
AUTHOR: Guo YuFei, Jose M. Maisog, Liu JF
REFERENCE : Liu JF, Y.Q. Chen, Jose M. Maisog, George Luta, A new point
containment test algorithm based on preprocessing and determining triangles,
Computer-Aided Design, vol 42, No.12, December 2010, Pages 1143-1150.
22 Sep 2014 : Version 1.0
So far, our work is cited by 16 research papers from a verity of areas:
1)Breitenfeld M. Quasi-static non-ordinary state-based peridynamics for the modeling of 3D fracture[D]. University of Illinois at Urbana-Champaign, 2014.
2)Magalhães S V G, Andrade M V A, Franklin W R, et al. PinMesh—Fast and exact 3D point location queries using a uniform grid[J]. Computers & Graphics, 2016, 58: 1-11.
3)Bongiorno E G, Goia A. Classification methods for hilbert data based on surrogate density[J]. Computational Statistics & Data Analysis, 2016, 99: 204-222.
4)Bartoněk D, Bureš J, Opatřilová I. Optimization of pre-processing of extensive projects in geographic information systems[J]. Advanced Science Letters, 2014, 20(10-11): 2026-2029.
5)Wei X, Joneja A, Tang K. An Improved Algorithm for the Automated Design of Large-Scaled Robot Skin[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(1): 372-377.
6)Maisog J M. How To Make an R Package Based on C++ And Manage It With R-Forge: A Tutorial[J]. 2011.
7)Lu P, Jiang X, Lu W, et al. Fast, Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees[J].
8)Horvat D, Žalik B. Inclusion Test for Polyhedra Using Depth Value Comparisons on the GPU[J]. International Journal of Computer Theory and Engineering, 2017, 9(2): 137.
9)Li L, Cazzell M, Babawale O, et al. Automated voxel classification used with atlas-guided diffuse optical tomography for assessment of functional brain networks in young and older adults[J]. Neurophotonics, 2016, 3(4): 045002-045002.
10)Barbeito A, Painho M, Cabral P, et al. Beyond Digital Human Body Atlases: Segmenting an Integrated 3D Topological Model of the Human Body[J]. International Journal of E-Health and Medical Communications (IJEHMC), 2017, 8(1): 19-36.
11)de Magalhaes S V G, Andrade M V A, Franklin W R, et al. Exact intersection of 3D geometric models[J].
12)Li J, Wang W. Fast and robust GPU-based point-in-polyhedron determination[J]. Computer-Aided Design, 2017.
13)Moretti V F. Inclusao entre nuvem de pontos e digitalizaçao 3D: estratégias e implementaçao[D]. UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL, 2015.
14)林明億. 人體仰臥下個人化脊椎型態分析[J]. 臺灣大學醫學工程學研究所學位論文, 2016: 1-45.
15)Opatřilová I. Metodika řešení masivních úloh v GIS[J]. 2015.
16)Bongiorno E G, Goia A. Classification methods for hilbert data based on surrogate density[J]. Computational Statistics & Data Analysis, 2016, 99: 204-222.
Problems or suggestions? Email me: guoyufei2014@gmail.com