Boost C++ Libraries: Ticket #11928: surveyor area method is inaccurate

awulkiew — Mon, 25 Jan 2016 22:40:34 GMT

The name of the formula seems to be older than Wikipedia [1][2].

I haven't measured it but I'd rather guess that nowadays the most expensive part in both cases is data access.

Furthermore I guess that in the case of the trapezium rule the result is also not precise in general when coordinates are big. So I'd rather fight with this issue by moving all of the coordinates closer to the origin of the coordinate system before passing them into the strategy, so doing it on the fly while calculating the area with any strategy. Similar technique was used before to improve the precision of centroid(). This solution should improve the precision of a function no matter what strategy was used.

With that said I'm not against changing the formula. But should trapezium rule be better in all cases or is there a reason why the old one could be left as it was?

[1] Flint, Abel. "A System of Geometry and Trigonometry: together with a treatise on surveying: teaching various ways of taking the survey of a field; also to protract the same and find the area. Likewise, Rectangular Surveying; Or, an accurate method of calculating the area of any field arithmetically, without the necessity of plotting it.", 1808

[2] Braden, Bart. "The surveyor’s area formula.", 1986

Tue, 26 Jan 2016 15:51:27 GMT

Thanks for the reference to Abel Flint (a great name!). You will see on pp. 59-63 that he describes the trapezium rule and not the so-called surveyor's method! Most of his contemporaries who were mathematicians would have recognized this as such and not, therefore, have seen it as some special technique invented by a surveyor.

The analysis of why

sum x_i y_i+1 - x_i+1 y_i

is typically subject to worse round off errors than

sum (x_i+1 - x_i) (y_i+1 + y_i)

goes as follows. Each formula contains

products
differences in forming each term in the sum
differences in forming the sum itself

In the surveyors formula 2 follows 1 and so the mild round off errors from the products are sometimes catastrophically magnified. In the trapezium rule 2 precedes 1 and there is no round off error if x_i+1 and x_i are within a factor of 2 of each other (which is a common situation).

Both formulas are subject to potentially dangerous round off with 3. Centering the numbers might ameliorate this problem. Alternatively, merely switching to the other trapezium rule involving (y_i+1 - y_i) would help, e.g., in the case of UTM coordinates where often the northings are much larger than the eastings.

Tue, 26 Jan 2016 16:37:57 GMT

By the way, in GeographicLib, I use an Accumulator class to perform the summation. This effectively sums at double the normal precision.

status, milestone changed; resolution set

awulkiew — Thu, 28 Jan 2016 13:52:18 GMT

status new → closed
resolution → fixed
milestone To Be Determined → Boost 1.61.0

I tweaked the formula as you suggested. Thanks.