MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

# inpolygon

Asked by AP on 4 Jun 2011

Is there a faster function than inpolygon? It takes forever when I want to check 1280x1024 pixels of an image whether they are inside or outside of a closed polygon.

## 1 Comment

Walter Roberson on 4 Jun 2011

So your polygon is closed. Aren't they all?

Is your polygon convex? Does it have holes? Is it self-intersecting? Is it complicated or relatively simple?

## Products

No products are associated with this question.

Answer by Image Analyst on 4 Jun 2011

What are you really wanting to do? Because there's a chance you can do it without using inpolygon. For example

[rows columns, numberOfColorChannels] = size(originalImage); pixelsInPolygon = poly2mask(polygonXCoordinates, polygonYCoordinates, rows, columns)

should do what you asked. It will produce a map of which pixels "are" or "are not" inside your polygon. But I have a feeling that this is just one intermediate step in what you really want to do.

Answer by John D'Errico on 4 Jun 2011

No. In fact, inpolygon is already blazingly fast. But no matter how fast you make something, someone will throw a million plus points at it, or a billion points, or a trillion points, and then decide it is too slow for their purposes.

Computers are not infinitely large or infinitely fast. The creative (or the ignorant or the foolish or the lazy) can always find a way to exceed the capabilities of any algorithm on any machine. In fact, problems quickly tend to grow in size to always just exceed those capabilities.

In any problem, there may be tricks one can use to reduce the work. For example, if you feel it is too slow to throw 1.2 million pixels at the tool, perhaps you can decide that entire simple regions are inside the polygon, therefore nothing inside that sub-domain need be tested?

Answer by Jan Simon on 4 Jun 2011

There is a faster function than INPOLYGON. If it is not written yet, it is possible to do, e.g. as C-Mex or in assembler and achieve an acceleration of 10% or 500%. But your problem "takes forever". A factor 5 will not help to reduce this remarkably.

Most likely it will be more helpful to exploit the geometry of the polygon: Exclude all points outside enclosing rectangle (very cheap), exclude all points outside the convex hull (semi cheap), etc.

Answer by carl howell on 28 Oct 2011

Are there nan's at the end of your polygons? If you've read in a shapefile, than likely so... If so, try removing them (nan's) before you call inpolygon...

## 1 Comment

carl howell on 28 Oct 2011

Never mind, looks like I had a bug in my code making it seem like it was faster with nan's removed... Still working on similar problem...