Fast InPolygon detection MEX

Fast detection points inside a polygonal region

Description

Fast detection points inside a polygonal region.
To my knowlegde, the code is faster than all the inpolygon functions found on MatLab File Exchange

[IN,ON,IN_strict] = InPolygon(px,py,cx,cy);

input: px - nPM x nPN (Matrix) X-coordinates of the points to be tested
       py - nPM x nPN (Matrix) Y-coordinates of the points to be tested
       cx - nC x 1 (Vector) X-coordinates of the polygon
       cy - nC x 1 (Vector) Y-coordinates of the polygon
output:
   IN - boolean matrix of 1 if px(i,j),py(i,j) is
in or on the polygon defined by cx,cy
   ON - boolean matrix of 1 if px(i,j),py(i,j) is
on the polygon defined by cx,cy
   IN_strict - boolean matrix of 1 if px(i,j),py(i,j) is
exclusively in the polygon defined by cx,cy

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
MClust Spike sorting toolbox

• MATLAB release: MATLAB 7 (R14)
• Other requirements: A C compiler to compile mex file for different plateform than win32

[Darren Engwirda]

Generally good, but not the fastest available on the tests I've run.

Offers similar functionality to the MATLAB inpolygon routine although not much help provided unless you want to read the C code.

It appears that only polygons with one bounding contour can be tested, rather than general multiply connected regions.

Based on a polygonal map of Lake Superior with 225 vertices, this code compared with my code "inpoly" as follows:

10,000 test points:
inpoly: 0.016 sec
InPolygon: 0.032 sec

100,000 test points:
inpoly: 0.06 sec
InPolygon: 0.33 sec

1,000,000 test points:
inpoly: 0.71 sec
InPolygon: 3.39 sec

These times are the average of 3 successive runs using MATLAB R14 on an Intel Core2 Duo laptop. The performance may vary for other benchmarks.

[Guillaume Jacquenot]

I agree that Daren's code is faster on this example.
My function presents the advantage of directly being able to substiture with MatLab inpolygon function.

[Guillaume Jacquenot]

I correct my previous comment: Daren's code is faster than mine.

[Mex Dll]

m-file please. Why do you put a file on MCFE if one can't peer into your code? That's not the purpose of this all...

[Guillaume Jacquenot]

There is no M-file, this a MEX file, however the function is called like a standard M-function (like the standard inpolygon). The function is a C -code interfaced with MatLab. I share this C-code interfaced with MatLab, because compiled code runs much faster than interpreted ones.
To have it work on your computer, you just have to compile it with MEX utility, and call it like the function inpolygon.

Moreover, MCFE has been developped to promote exchange between MATLAB users. And experimented users do not satisfy themselves with only M-files, they also use C-codes or Fortran codes that they interface with MatLab.

[Samy Makarsky]

That's exactly what I was looking for!