Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I have 2D-points, which boundaries depict a polygon. The points are at integer positions (no fractions possible).
Now I want to build an enumerator in C# that returns all points that are inside the polygon. Implementing the enumerator is not the issue, but how do I efficiently get all the points? The polygon can be quite big.
What you are seeking is a solution to the "point-in-polygon" problem. It is described in Wikipedia here:
You can find C code following the links to Computational Geometry in C, or at many other locations found by searching for "point-in-polygon" code.
You will need to process all the points at least once so if this check is done only once there isn't much you can do to speed up the test other than brute-forcing it using parallelism.
If the test is going to be run multiple times there are ways to pre-calculate tables to help, such as a grid of cells marked as [definitely inside (green in image), outside (red), and maybe (blue)], only points that fall in the blue cells need to be tested against the polygon.
But if it's run only once with just few points relative to the grid or too many "maybe" cells then building this table is likely to take more time than just brute-force testing your points.
You need to have many more points than cells (low resolution grid) for this to turn a "profit", and most cells must end up as definite inside or outside (high resolution grid), so finding a balance that speed things up between those two factors can be difficult.
It's easier and more consistent in terms of gains to just split the number of points between multiple threads and do a simple odd-even intersection test. GPGPU processing such as OpenCL can give you an easy and huge speed up for this kind of test simply by using a massive number of cores.
Every polygon can be represented as lines[L] with interception points[P].For each line you calculate weather it is above or below a point Pn(n is the index of array P) which is not part of the line Lm.When you measure all the lines you save the result in one dimensional bool array V[number_lines].When you have a random point A.Then you make for loop for each line and you make the same check if point A is below or above line Li.As you do it you compare the result to V[i] and if its not the same you return true if point A is over the line Li else you return false.Once the loop though all lines from [L] you can return true.As you do this you can know if a point is inside or outside an polygon easly which means that you can loop though all A points in the polygon bound box Box[Px(min),Py(min),Px(max),Py(max)].To detect weather point A is above or below line L you must turn line L into function f(x)=y=ax+b by using the two points representing the line as x=P1.x y=P1.y and x=P2.x x=P2.x including them into system.Once you have calculated the function f(x) you must simply test if f(A.x) ><= A.y . If f(A.x)>A.y then the line L is above point A.If =0 then its on the line else its below it. It might look a bit complicated, but the most of those calculations are instant and can be calculated only once. As you store V,L,P arrays in the polygon represented class.
PS: If line L with points P1 and P2 is such so P1.x=P2.x then you cant create an function based on f(x)=ax+b you must simply check if the point A(which you are comparing if its below or above line L)A.xP1x. its above.of if A.x=P1.x then its on it
You could possibly treat it as a graph traversal problem. If you treat adjacent points as 'children' of each other and add each child of your boundary points to a list of open nodes (ie. unvisited nodes), then your enumerator could explore this list.
In case you're unfamiliar with search algorithms, this would probably look something like:
For each point; add the point to a set of closed nodes (ie. visited). If the point is within the polygon, add it to your enumerator and add it's children to your list of open nodes. Continue until your list of open nodes is empty. Also, only add nodes to your open list if they're not already on your closed list.
A couple of notes:
Have a look at this. It works through some very clear diagrams.
http://www.mathopenref.com/coordpolygonarea2.html
They are just calculating area and you are enumerating points. However you can adapt these ideas. Look carefully at 'A More Complex Case' and how the horizontal lines divide the polygon into a set of trapezoids (if you recognize a triangle as degenerate trapezoid with a zero length side).
If your polygons are (potentially) concave you need to discard some trapezoids based on the direction of travel Y(n)-Y(n+1) rule mentioned in the text.
So, now you've reduced enumerating points in a polygon to enumerating points in a series of trapezoids. That shouldn't be too hard particularly given the trapezoids are nicely oriented being 'trapped' two lines both parallel to the X axis. It is probably easiest to do that in a raster scan so you only have calculate the start X and end X of each raster row.
Your data structure might look like a list of polygons, an index indicating which polygon you're in, which x and y coordinate your at and the end index of the raster row you're in.
I'm assuming you don't mind what order you enumerate in!
Further complexity will be incurred if your 'polygons' included disjoint shapes (i.e. actually more than one polygon or could contain polygonal 'holes'.
The complexity of obtaining the trapezoids is quite low but iterating over a vast number of points may be quite slow. I have no idea what you're doing this for but as pointed out by Stephane Hockenhull above a conventional weight of making it easier is to used a coarsening approximation.
That would mean actually scanning in steps of (say) 5 and (if your algorithm is ameanable) treat the centre point of a 5*5 'cell' as somehow representative.
I hope you weren't looking for an easy answer? I'd love to see some code for this!
