File Exchange

image thumbnail

Fast Inpolygon in MEX

version 1.2 (5.86 KB) by

Fast inpolygon function implemented in MEX. So far one of the fastest.

2 Downloads

Updated

View License

This is a C implementation of the great Matlab code provided by Darren Engwirda. You can find his code in:
http://www.mathworks.com/matlabcentral/fileexchange/10391-fast-points-in-polygon-test

According to my estimates, it works more than 2x as fast. So far, this is one of the fastest implementation that I know of. Sorting is big step of this algorithm. To make it an exact replica, I use stable_sort of std library.

Here is a sample call:

tic(); [In2 On2]=inpolygon_fast(x, y, xv, yv); toc();

The call interface is similiar to inpolygon and not to inpoly. Here x and y are the points to check, where xv and yv define the polygon.

The attachment includes the cpp file, a sample function for comparison and Darren's code.

Comments and Ratings (6)

Roger GALLOU

Tolga

I have made few tests with erractic errors. Comportment of DLL is very perturbated, ie :
x = 0.5;
y = 0.5;
xv = [0 1 1 0];
yv = [0 0 1 1];
[IN ON] = inpolygon_fast(x, y, [xv xv(1)], [yv yv(1)]);

Results could be sometimes 0 or 1 for the same MatLab session !!!
I do not have time to look further, but this feature requires substantial improvements.

I have found many cases where this function fails. There is a bug, somewhere in the code.
Could the author fix it? Otherwise unreliable.

Here is a counterexample:

X = 49936;
Y =-78883;
XV = [49370 54355 54355 49370];
YV = [-8406 -8406 -77126 -77126];
inpolygon(X,Y,XV',YV')

ans =

0

>> inpolygon_fast(X,Y,XV',YV')

ans =

1

The correct answer is that of inpolygon,
since the point is located outside the rectangle.
Use the following code to check it out yourself:

plot(XV,YV,'-b');
hold
plot(X,Y,'.r')

Yavor Kamer

So now that you know that this code is not the fastest would you kindly consider editing your bold claims just for the sake of not being misleading?

Alex Franquet

Tolga Birdal

Tolga Birdal (view profile)

You are right. Good to know.
Actually there is help and calling convention in the above documentation and I provided a sample file as well.
Error checking is not done for speed reasons (your code also lacks that in some sense).

Bruno Luong

Bruno Luong (view profile)

According to my test, fastest in_polygon is not this submission but this one:

http://www.mathworks.com/matlabcentral/fileexchange/27840-2d-polygon-interior-detection

The CPP mex file (not C) lacks help, document on calling convention, and error checking. I get few crashes when playing around with it.

Updates

1.3

n/a

1.2

Small updates in description.

MATLAB Release
MATLAB 7.9 (R2009b)
Acknowledgements

Inspired by: Fast points-in-polygon test

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video