Inhull

Efficient test for points inside a convex hull in n dimensions

Description

Testing if a point is inside a convex hull can be done in a variety of ways. Inhull converts the problem into a dot product. If not supplied, it also computes the convex hull too. Inhull also attempts to avoid memory problems, doing the computation in smaller blocks when appropriate.

Here is a comparison of inhull to tsearchn:
n = 500;
m = 100;
p = 5;
xyz = rand(m,p);
testpts = rand(n,p)-.1;

tic
tess = delaunayn(xyz);
in0 = ~isnan(tsearchn(xyz,tess,testpts));
toc
tic
in1 = inhull(testpts,xyz);
toc

tsearchn: Elapsed time is 641.046321 seconds.
inhull: Elapsed time is 0.610503 seconds.

• MATLAB release: MATLAB 7.0.1 (R14SP1)

[Liketo Stayanonymous]

No, sorry! I think you lost me with this one. What (again) is this software about??
Clear example will be much appreciated!

[Mia Ginsburg]

Just what I wanted. Much faster than tsearchn if you just want to test if a point is inside a convex hull.

[Quan Wen]

I agree with what Mia Ginsburg said. This code is very helpful. Thanks a lot.

[John Galt]

Ever heard of commenting your code?

[Jon KoS]

Great Job! Works really well and does what it says. I'll be using this function a lot. :) Not sure what the other reviewer was looking at but the code is well commented. Thanks!

[Yonas T. Weldeselassie]

Excellent! Great job. Well documented, easy to understand, very similar to inpolygon and what more? Thanks a lot.

[Lee Shunn]

Fast and easy to use. Thanks for the great code.

[Jayveer Thakoor]

huge time saver! thank you :)

[Titus Edelhofer]

Very nice. Just for ease of use: the example given in the help uses different variable names then the call to the function (and should call convhulln instead of convhull).

[Luigi Giaccari]

Very good code, readable, uderstandable and even fast.
The n-dimensions also make-it flexible.

The thing I like the most is a wonderfull example of dot product vectorization with memory management. It helps a lot to understdand how to make m-code more efficient.

The only thing i disagree is the comparison with tsearchn, I thing its purpose is to find where a point is located inside the hull and whether he is inside or not. The nan output values are just a secondary objective which occurs in the worst case when a point lies outside.

Anyway a five stars, very good work!

[Luigi Giaccari]

Very good code, readable, uderstandable and even fast.
The n-dimensions also make-it flexible.
 
The thing I like the most is a wonderfull example of dot product vectorization with memory management. It helps a lot to understdand how to make m-code more efficient.
 
The only thing i disagree is the comparison with tsearchn.
 I thing its purpose is to find where a point is located inside the hull and not whether he is inside or not. The nan output values are just a secondary objective which occurs in the worst case when a point lies outside.
 
Anyway a five stars, very good work!

[Nagarjuna]

very nice work

[Florian]

Thank you very much for this code. Particularly thanks to John for explaining me a problem I had with the code:

I have tried the following:
 tms=rand(1000,5);
in = inhull(tms,tms);
disp(length(find(in==0)))

which gave roughly ~319

as John points out:
"those 319 points were almost certainly on the surface of the convex hull.

Try this slight modification of your code instead.

tms=rand(1000,5);
in = inhull(tms,tms,[],1.e-13);
disp(length(find(in==0)))
     0

See that I've used a tolerance this time. The linear algebra used in the test is done in floating point arithmetic in matlab, as it must be. Without a tolerance, any test done in floating point arithmetic is suspect. By default that tolerance is zero, but this is also why I allowed the user a tolerance at all. "

Thanks John!!!!!

[Navid Samavati]

Excellent Code!

[David Gingras]

Another very usefull code provided by John! Thanks.