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!