Page 1 of 1

Count number of points... ?

Posted: Thu Feb 23, 2006 2:19 pm
by unfriendlyboy
Given a convex-polygon with with integer x,y coordinate of vertices. Count how many integer x,y coordinate points that lies inside the polygon.

I figure out a algorithm that run in O(N * D) with N is the number of vertices and D is the distance of left-bound coordinate and right-bound coordinate. I heard that there is a formular for this problem. Is it true ?

Posted: Thu Feb 23, 2006 3:14 pm
by tywok

Posted: Thu Feb 23, 2006 4:27 pm
by unfriendlyboy
tywok wrote:You should read this: http://mathworld.wolfram.com/PicksTheorem.html
thanks for this useful information.
How about a polygon not a closed polygon (sorry I dont know the exact word to use)

Like this

Code: Select all

-------
\       |
 \      |
 /      |
/------