v-O_O-v's blog

How to implement PICK'S theorem in c++
By v-O_O-v, history, 6 years ago, In English

Hello! I am unable to find any resource on implementing pick's theorem for a polygon in c++. Can anyone suggest me a site or code where i can understand it.

Thanks.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Well Pick Theorem states that: S = I + B / 2 - 1 Where S — polygon area, I — number of points strictly inside polygon and B — Number of points on boundary.

In 99% problems where you need to use this you are given all points of a polygon so you can calculate S and B easily

Polygon Area
Points on boundary

So by having S and B you can get I using some simple maths: I = S + 1 - B / 2

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I did not understand how you found boundary points. Can you explain in detail.Photon_

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      So points with integer coordinates on line segment is GCD(dx,dy) + 1

      Where GCD is Greatest common divisor, dx is distance between x coordinates of points, dy — is distance between y coordinates of points

      Why?
      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ats+=abs(__gcd(dx,dy)) - 1;

    That -1 should not be there.

    EDIT: Ah sorry I missed the = A.size(), it works out fine, my bad.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what happens if vertices of polygon don't have integer coordinates? how to handle that case?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      It also works for rationals, and all the numbers you can read are rational ... you can maybe multiply them by $$$\frac{1}{\epsilon}$$$. with $$$\epsilon$$$ the minimum $$$10^{-k}$$$ value that you can work.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

(https://www.google.com/amp/s/www.geeksforgeeks.org/count-integral-points-inside-a-triangle/amp/)

→ Reply