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)
Powered by vBulletin® Version 4.2.2 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.