No BSD License  

Highlights from
Fast points-in-polygon test

4.4 | 19 ratings Rate this file 65 Downloads (last 30 days) File Size: 22.5 KB File ID: #10391 Version: 1.0
image thumbnail

Fast points-in-polygon test


Darren Engwirda (view profile)


16 Mar 2006 (Updated )

Fast test to determine points located inside general polygon regions. Should be significantly faster

| Watch this File

File Information

Test a set of points in the 2D plane to determine which are located inside or on the edges of a polygon.

The polygon geometry can be non-convex and multiply-connected.

Similar to INPOLYGON, but generally much faster, more memory efficient and less prone to numerical rounding error.

INPOLY also displays superior scaling in terms of problem size (number of points, number of polygon edges) and hence the speedup when compared to INPOLYGON is significant for large problems and can easily be a factor of several hundred.

% UPDATE 31/03/2007
New algorithm! Massive speed improvements for large problems.

Untested on MATLAB pre-R6.5. These older releases lack JIT acceleration and may suffer speed penalties as a result.


This file inspired Maximum Inscribed Circle Using Distance Transform, Fast Inpolygon In Mex, Maximum Inscribed Circle Using Voronoi Diagram, The Barycentric Fixed Mass Method For Estimating Fractal Dimensions, and Flow Cytometry Gui For Matlab.

MATLAB release MATLAB 7 (R14)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (24)
26 Jan 2015 Ajay

Ajay (view profile)

Very dependable code, thanks.

Any recommendations for a 3-D point-in-polygon test, including non-convex cases?

20 Aug 2014 Luca

Luca (view profile)


running the following code, with N = 1000000, never gives inpoly faster than inpolygon.For "small" N (N=100-1000), they alternate.
However, when running the examples provided in polydemo.m, inpoly is consistently faster than inpolygon.

Am I doing anything wrong? A graphical check (commented in the code) gives what seems to be right, so I think I'm using the function as I should. Anyway, I don't see any improvement in speed, the contrary (for large N).

%%% sample code %%%%%%
for k=1:10

small_box = [ 1/3 1/3; 1/3 2/3; 2/3 2/3; 2/3 1/3];
N = 1000000;

A = rand(N,1);
B = rand(N,1);

% figure; hold on;
% plot(A,B,'.')
% patch([small_box(:,1); nan],[small_box(:,2); nan],ones(5,1))

tic; in = inpolygon(A,B,small_box(:,1),small_box(:,2)); t1=toc;
tic; in2 = inpoly([A B],small_box); t2=toc;

time_in_sec = struct('inpolygon',t1,'inpoly',t2);
if t2<t1
fprintf('inpoly is %f seconds faster\n',t1-t2)
fprintf('inpolygon is %f seconds faster\n',t2-t1)

% plot(A(in),B(in),'.r')
% plot(A(in2),B(in2),'.g')


Comment only

Nice, used it in a problem with an unstructured grid and worked perfect.

05 Mar 2013 Joseph

Joseph (view profile)

Not sure when matlab changed this but in matlab 2012b the inpolygon function works just slightly faster than this one. Still great work!

28 Jun 2012 Edison Lee

Hi was wondering could you tell me from which conference/journal paper this function algorithm is based from?


Comment only
09 Apr 2012 Michelle Tadmor


26 Mar 2012 Woody Wong  
01 Jul 2011 Luke Winslow

Luke Winslow (view profile)

Great and fast little tool. Much faster than matlab inpolygon. My only issue is that I wish it natively understood the typical "GIS" format for polygons which includes a NaN separated list of polygons (NaNs separate the major outline from the 'islands').

Of course you can just handle this with the edges field though, so for future reference, here's my simple create edges code for NaN separated GIS objects. 'shp' variable is n Nx2 matrix of latitudes and longitudes.

shpEnd = find(isnan(shp(:,1)));
shpEnd = vertcat(0,shpEnd);
edges = nan(length(shp(:,1))-length(shpEnd),2);
count = 1;
for j=1:length(shpEnd)-1
endCount = count+length((shpEnd(j)+1:shpEnd(j+1)-2));
edges(count:endCount,:) = [(shpEnd(j)+1:shpEnd(j+1)-2)' ...
(shpEnd(j)+2:shpEnd(j+1)-1)';shpEnd(j+1)-1 shpEnd(j)+1];
count = endCount+1;

26 Oct 2010 Sven

Sven (view profile)

indeed the on edge test is not robust, points on the edge will not be detected as on edge or as inside polygon. So watch out with that!

I am using the build in inpolygon routine now, works for me.

05 Jun 2010 Bruno Luong

Bruno Luong (view profile)

This is a quality code

23 Nov 2008 Luigi Giaccari

Thank You,
it was very helpfull, impressive code.

If I can suggest an improvement:
a mex version will be the top of performance.

07 Nov 2008 Dag Lindbo

Very nice routine!

Is it reasonable to look for more efficient method for the particular case when the points to query at can be assumed to lie on a cartesian grid? E.g. imagine

in = inpoly(p,node);

with p = {X, Y}, where [X Y] = meshgrid(x,y)


18 Sep 2008 Lili Wan

It is a good job, but I still find some problems when detecting a point of a polygon lies on the polygon edge. My test run in Matlab R2006a. Suppose node be the points of a polygon,
"[in,on] = inpoly(node,node);" can get right results, but after running
"[in,on] = inpoly(node(1,:),node);", on is false.

03 Apr 2008 Armin Müller

Very fast, very accurate. Good jobb, Darren!

25 Mar 2008 Joseph Marks

My review below is too harsh.

After examining several runs on many different "ultra-concave" polygons, I have found inpoly to be very good.

If the error problem I reported earlier is real, it is very rare. It could have been due to some other factor in my software including my own bug.

inpoly is very much faster than inpolygon for large test vectors.

19 Mar 2008 Joseph Marks

inpoly provides a very large speed increase for large polygon problems!

Unfortunately, I too noticed a bug.

I am checking a very large rectangle grid's points to see if they are in a "massively concave polygon" -- think the outline of a "robot with arms, legs, etc."

The inpoly algorithm "incorrectly" *ADDS* a "shock of hair" to the "robot" -- obviously I am speaking metaphorically here -- and hence I am stuck using the *MUCH SLOWER* "inpolygon".

Has anyone reported an error like this to you?

Is there anything I can do?

Is there some middle ground between the two -- for example, by and large, I am dealing with concave polygons that just have an outside boundary -- no hole or anything.

16 Apr 2007 Darren Engwirda

Small bug (as noted below) fixed.

Users don't beware, inpoly should work in all cases.

Further bugs can be emailed if necessary...

Comment only
12 Apr 2007 Alex Storer

Very fast, but fails on some cases. Users beware! Perhaps older versions are more robust?

08 Apr 2007 Michael M

It's an incredible speed up compared with the poor inpolygon function delivered with MATLAB! Must be O(M*log(N)) ;-)

12 Feb 2007 Matt K.

Perfectly suited for my needs of finding points on the boundary of a polygon

19 Mar 2006 Urs (us) Schwarz

The reason that cnect is defined on its own is so that the domain can be multiply connected (polygon with "islands").
please, note that i said at run-time, i still feel that you should make the third arg optional

Comment only
17 Mar 2006 Darren Engwirda (The author)

The reason that cnect is defined on its own is so that the domain can be multiply connected (polygon with "islands").

If you assume that cnect can be built by taking consecutive nodes this is no longer possible.

Thanks though, I will update it to flag boundary points as us mentioned.

Comment only
17 Mar 2006 John D'Errico

While I prefer the edge list implementation this code uses as opposed to Matlab's polygon, it would be easy enough to generate the connectivity assuming consecutive points on the polygon as us points out.
Regardless, this code is indeed fast and nice.

17 Mar 2006 Urs (us) Schwarz

very nice (and indeed fast) snippet with a good help section and economic implementation of the crossing number test
minor comments:
- the third arg CNECT should be computed automatically (if not defined at run-time) on the assumption that the user-defined points are connected consecutively; this behavior could/should be mentioned in the help section
- unfortunately, unlike INPOLYGON it does not (yet) distinguish between IN and ON the polygon
- the help section should give a pointer to INPOLYGON

20 Mar 2006

Detect points on boundaries

06 Dec 2006


01 Apr 2007

New algorithm

02 Apr 2007

Error checking added

13 Apr 2007

Bug fix (floating point roundoff)

21 May 2007

Binary search added, bit faster

Contact us