0

This question is similar to an existing one, except that the current question requires the polygon centroid formula not to cube coordinates, which is essential to my application.

The nature of the application I am working on requires integer coordinates. For the purpose of computing areas we can double the number of bits, i.e. from 32 to 64 or from 64 to 128 bits, so that coordinate multiplication doesn't overflow. For centroid of a polygon we implemented the standard formula, the same one as in the SO question cited above as well as dozens other online sources. However, because the standard centroid of a polygon formula essentially cubes the coordinates (by multiplying coordinates by areas) we cannot use it; we have already seen integer overflow in some tests.

Thus the question: is it possible to find the centroid of a polygon without cubing the coordinates?

Michael
  • 5,775
  • 2
  • 34
  • 53

1 Answers1

0

The question can be answered by determining how many different values the coordinates can take. For the area, it is clear that all R² values are possible (where R is the coordinate range).

I see no reason it would not be R³ for the centroid (take a filled square and remove a single point anywhere, this already gives you R² different centroids). So you will need R³ numbers just to distinguish between the possible outcomes.

But why would you need exact coordinates ?

If you are ready to use 128 bit arithmetic, you can support a range of up to 42 bits, which is better than 12 digits.