Count number of points... ?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
unfriendlyboy
New poster
Posts: 7
Joined: Wed Jan 18, 2006 7:10 am
Contact:

Count number of points... ?

Post by unfriendlyboy » Thu Feb 23, 2006 2:19 pm

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 ?

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Thu Feb 23, 2006 3:14 pm

Impossible is nothing

unfriendlyboy
New poster
Posts: 7
Joined: Wed Jan 18, 2006 7:10 am
Contact:

Post by unfriendlyboy » Thu Feb 23, 2006 4:27 pm

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

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

Post Reply

Return to “Algorithms”