CODEWITHSUNDEEP
algorithmgraphics
Aman
Aman

Reputation: 25

Determine number of integral coordinates lying inside or on a quadrilateral?

Can someone tell me any algorithm by which I can find total number of integral coordinates lying inside or on a quadrilateral. The coordinates of the quadrilateral will be given as input and you have to tell total no. of coordinates lying inside or on a quadrilateral. For example if the points given are (5,3) (1,1) (3,4) (6,1) then answer should be 14. If you draw the quadrilateral then you will find that only 14 integral coordinates like (3,2),(5,1)..etc lies inside and on the quadrilateral.

Upvotes: 0

Views: 1189

Answers (1)

MBo
MBo

Reputation: 80187

If your quadrilateral vertices have integer coordinates, then it is possible to use Pick's theorem. 

A = i + b/2 - 1

where A is area, i is the number of interior integer points, and b is the number of integer points at the borders (edges). You can find quad area with any method (for example, see here), and find number of border points on every edge as GCD(dx, dy) (+1 term excluded to avoid counting vertices twice)

Upvotes: 2

Related Questions