Code covered by the BSD License  

Highlights from
Fast Inpolygon in MEX

2.5

2.5 | 2 ratings Rate this file 21 Downloads (last 30 days) File Size: 5.86 KB File ID: #30819
image thumbnail

Fast Inpolygon in MEX

by

 

22 Mar 2011 (Updated )

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

| Watch this File

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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
29 Oct 2014 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.

09 Dec 2012 Marco Cococcioni

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

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?

25 May 2011 Alex Franquet  
22 Mar 2011 Tolga Birdal

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

22 Mar 2011 Bruno Luong

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

Small updates in description.

22 Mar 2011

Contact us