PDA

View Full Version : Geometry (all points inside a polygon)



nitro_n2o
August 5th, 2008, 12:31 AM
Hi,

I was wondering if anybody knows an algorithm that will return all the integer points lying within a given boundary (e.g inside a polygon define by 6 points)

so, given a bunch of points defining a closed shape; how to get all points inside that shape

Thanks a lot

CptPicard
August 5th, 2008, 12:44 AM
http://en.wikipedia.org/wiki/Point_in_polygon

A simple way would be just to find the min and max of the polygon in given dimensions, just producing all integer points, and then filtering according to this... but I am sure you can adapt it further.

nitro_n2o
August 5th, 2008, 12:52 AM
Thanks for the reply, I was trying to find a faster way to do it though..
I think I should probably start with brute force way then find a fancier solution.

Thanks!

CptPicard
August 5th, 2008, 01:05 AM
Considering that the majority of integer points inside the bounding box are likely to be inside the polygon, you aren't really wasting much time querying in that sense.

Perhaps one could make use of closeness of nearby points and their presence in the same part of the space partition... look at the planar partition idea where the polygon is divided into slabs. But I get the feeling that even if you got many integer points at once from each "slab" you would end up wasting more actual computation time in your data structures and more complicated algorithm than you would need if you just went through the points and queried individually using a simpler method.

nitro_n2o
August 5th, 2008, 01:29 AM
yeah I think you are right! :)
I've implemented it and it seems fast enough

Thanks a lot

hod139
August 5th, 2008, 01:50 AM
If you know the polygon will always be convex there are faster algorithms available. A good website for geometry algorithms (with lots of free C code implementations) is available at:
http://geometryalgorithms.com/algorithm_archive.htm

The chapter on point in polygon is here:
http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm

CptPicard
August 5th, 2008, 01:57 AM
For a convex polygon it is possible to do a whole row of integer points at once until you hit the opposing edge of the polygon... just do a planar partition along the x-axis (so that you get horizontal divisions) first, then it is trivial to find integer points inside the slabs.

(Works analogously in the other direction ofc)