How to find points in a convex hull/polygon in a 2D grid ?

[aredo]

I don't have knowledge of texturing and 3D algorithms but I have to solve an issue for a program.
On a integer coordinates 2D grid world I have to determine which points lie inside a convex hull/polygon. The convex hull vertex lists is given and already known in clockwise order.
Now, I looked at Andrew, QuickHull, Graham Scan and such but I couldn't find any example to reverse the problem. Graham Scan actually checks all the points in a set to find the convex hull but I already got the convex hull and what I need is a way to do the reverse that Graham Scan does. I need to build up a list of elements inside the convex hull that lie on 2D grid points and their maximum number (the area made of 2D grid points in practice) including those that lie on the convex hull border (between any two vertices of the convex hull the 2D grid points that lie on the line joining them).
I thought about the fact that if Graham Scan could be inverted it would automatically give me the number of maximum elements that could be contained within the convex hull as well as the list of of them, right ? But I couldn't find any example, not even pseucode ones to invert Graham Scan to obtain what I need.

Could anyone please help me about how to solve this ?
Thanks.

[Elementer]

Hello,
there are some approach to this, I think scan-line algorithm isn't better choise for that, did you have already tried with half-space test ? If the polygon is convex, each side is a segment that is colinear with an infinite plane, each of this plane divide the space into 2 half-space. You must find a method to check if a point is in on one side of line or the other side. To achieve it, you must transform each segment into vector (with the same order), and with dot product you can determine if a point lie on either side of each plane, or on the plane itself.

Thus you have your point P(x,y) (that is a vector), and each polygon side (that I said sides are also vectors all in same order) each side with its normal vector N. With dot product between point P and all normal vectors, you can test if point P lies inside the polygon. Try to draw it before start to write code, it's simple ;)

Regards

[andytim]

Hi,
I think you should try the XD++ MFC Library,maybe it includes the source code you would like:
http://www.********.net
Andy

[aredo]

Hello,
there are some approach to this, I think scan-line algorithm isn't better choise for that, did you have already tried with half-space test ? If the polygon is convex, each side is a segment that is colinear with an infinite plane, each of this plane divide the space into 2 half-space. You must find a method to check if a point is in on one side of line or the other side. To achieve it, you must transform each segment into vector (with the same order), and with dot product you can determine if a point lie on either side of each plane, or on the plane itself.

Thus you have your point P(x,y) (that is a vector), and each polygon side (that I said sides are also vectors all in same order) each side with its normal vector N. With dot product between point P and all normal vectors, you can test if point P lies inside the polygon. Try to draw it before start to write code, it's simple ;)

Regards,


I've tried implementing cross-product that should tell me if the given point is inside or outside based on any sign inversions and if the cross product is zero then it's on the border. The problem is that on a convex polygon I have a vertical straight line aligned to the 2D grid. To find out which points of the smallest enclosing rectangle are inside and which ones are outside I created a loop to test each point coordinate with each polygon vertex but cross-product gives me 0 on a point that has its y coordinate 1 less that the vertex coordinate of this straight-line of the border. (its X coordinate it's the same as the points that lie on this vertical straight line of the polygon border, while it's just 1 point below at the Y coordinate)
I don't get it, it shouldn't result in any 0 but it does. The point is outside on the test polygon on the grid if I draw it but the cross-product result gives 0 just because the edge vector X coordinate results in 0 and the V vector in 0 as well...
BTW, I am calculating vectors :

E = vertex[i+1] - vertex[i]
V = P - vertex[i]
S = sign of (E x V)

Is the case of straight line aligned to the grid a special case that I should care of ? And if yes, then how should I solve this issue to ensure that cross-product works with any polygon border lines aligned to the grid and doesn't give a false 0 like in this case for a point outside the polygon while it should detect every single point that lies on the border line itself ??
Could anyone please tell me what is the trick ? I couldn't find it anywhere so far.

I haven't checked for all miscalculation errors in my debugging code but if there is even just one miscalculated point there then it's not good and needs to be fixed for proper calculation of which points are really inside, which ones are outside and which ones lie on the border including the same polygon vertices in the counting.