This is a C implementation of the great Matlab code provided by Darren Engwirda. You can find his code in:
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.
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;
XV = [49370 54355 54355 49370];
YV = [-8406 -8406 -77126 -77126];
The correct answer is that of inpolygon,
since the point is located outside the rectangle.
Use the following code to check it out yourself:
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?
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).
According to my test, fastest in_polygon is not this submission but this one:
The CPP mex file (not C) lacks help, document on calling convention, and error checking. I get few crashes when playing around with it.
Small updates in description.