Code covered by the BSD License

### Highlights from Fast Inpolygon in MEX

2.5
2.5 | 2 ratings Rate this file 13 Downloads (last 30 days) File Size: 5.86 KB File ID: #30819 Version: 1.2

# Fast Inpolygon in MEX

### Tolga Birdal (view profile)

22 Mar 2011 (Updated )

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

File Information
Description

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.

Acknowledgements

Fast Points In Polygon Test inspired this file.

Required Products Image Processing Toolbox
MATLAB release MATLAB 7.9 (R2009b)
29 Oct 2014 Roger GALLOU

### Roger GALLOU (view profile)

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.

Comment only
09 Dec 2012 Marco Cococcioni

### Marco Cococcioni (view profile)

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')

10 Oct 2011 Yavor Kamer

### Yavor Kamer (view profile)

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?

Comment only
25 May 2011 Alex Franquet

### Alex Franquet (view profile)

22 Mar 2011 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).

Comment only
22 Mar 2011 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.

Comment only