Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Do you know anything about the shape whether it is convex etc etc? –  user17762 Oct 18 '11 at 23:34
add comment

2 Answers

up vote 1 down vote accepted

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)

share|improve this answer
    
Any mention of Pick's Theorem gets my vote. –  Gerry Myerson Oct 19 '11 at 2:21
add comment

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)$

share|improve this answer
    
See my comment on Ross' answer. –  Gerry Myerson Oct 19 '11 at 2:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.