# Finding how many points to which a certain point is connected

This may be a programming issue, not a mathematical one. If so, please let me know so that I can rewrite it specifically for that audience.

Consider a shape with a random border. Each point on its border has an x and y value that is an integer. This shape's interior is also composed of points that have integer values for both x and y. Each of these points is a distance of 1 from each other.

What is the most efficient way to get a total count of the points within that shape?

In case my question isn't clear enough, allow me to explain the specific issue I'm trying to solve.

It's a programming issue. I have an image that is divided up into different groups of pixels based on certain color analysis techniques. But I have no way of knowing when such a division occurs.

My program first analyzes all the pixels. In the process, it determines a specific pixel's "siblings" -- those that border it up, down, left, right and diagonally in each direction -- but that also satisfy a certain result from the color analysis I alluded to earlier. Therefore, one pixel's siblings can lead the program to their siblings, which lead the program to their siblings, and so on.

Beyond what I've written here, I'm having trouble offering a better formulation of this question. I'll happily edit my question if its current state is found lacking.

-
Do you know anything about the shape whether it is convex etc etc? –  user17762 Oct 18 '11 at 23:34

If all the corners are on lattice points, Pick's theorem applies. The area is the number of interior lattice points plus half the number on the border less $1$. It sounds like you want to use it in reverse. You can triangulate the polygon, add the areas of the triangles, get the area, and know how many lattice points are involved. To find the number of points on the border, given a segment from $(a,b)$ to $(c,d)$ there are 1+GCD(c-a,d-b) points on it. As the vertices will be double counted, you can just count each side as GCD(c-a,d-b)
If you know all points on the border you can find value of area, then you can use Pick's theorem and get number of the point, that are in. Area you can find as $\sum\frac{y_i+y_{i+1}}{2}(x_{i+1}-x_i)$