## Pointsinpolyhedron-Test if points are in polyhedron

Version 1.12 (45.3 KB) by
Test if points are inside/outside/on single material or multi-material triangulated polyhedron

Updated Mon, 24 Apr 2017 02:48:45 +0000

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.
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

### Cite As

YuFei Guo (2023). Pointsinpolyhedron-Test if points are in polyhedron (https://www.mathworks.com/matlabcentral/fileexchange/47909-pointsinpolyhedron-test-if-points-are-in-polyhedron), MATLAB Central File Exchange. Retrieved .

##### MATLAB Release Compatibility
Created with R2012a
Compatible with any release
##### Platform Compatibility
Windows macOS Linux

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

#### pointsinpolyhedron/html/

Version Published Release Notes
1.12

Fix some bugs.
update description

1.11.0.0

update my file as a toolbox

1.10.0.0

make description more clear.

1.9.0.0

make description more clear.

1.8.0.0

make description more clear.

1.7.0.0

make description more clear.

1.6.0.0

make description more clear.

1.5.0.0

Simplify our program, make it easy for our users to use.

1.4.0.0

Make our program better for customers to read.

1.3.0.0

Make the function easier to use.

1.2.0.0

make description more clearly.

1.1.0.0

make the description more clearly?

1.0.0.0