search

jeffThompson / CollisionDetection

A book and examples on collision detection
418 stars 53 forks source link

Heron’s Forumula [sic] and other issues on tri-point.php #20

Open angrave opened 4 years ago

angrave commented 4 years ago

On the page tri-point.php

  1. "Heron’s Forumula:" ^ Formula is misspelt.

  2. Also a visual check of the formula suggests this is actually the Shoelace formula not Heron's formula.

  3. Adding up the area is a clever mathematical approach but it suffers from machine arithmetic issues, especially with long skinny triangles. It would be useful to discuss this limitation and how a small delta can be used to address this limitation..

jeffThompson commented 4 years ago

Thanks for this!

Re shoelace vs Heron – can you point me to a reference? A lot of these examples are built on examples by other folks, so it's quite possible they had it wrong and I just copied it :)

Re long/skinny triangles – can you explain how that's the case? What do you mean by "small delta"?

angrave commented 4 years ago

https://en.wikipedia.org/wiki/Shoelace_formula It looked to me that your area formula would expand out to this form shoelace (image from the above above wikipedia page)

Re. small delta: The problem is machine arithmetic. Addition and multiplication does not have infinite precision. So an exact comparison can fail. This is most likely to happen if you start with non-integers (e.g. a third and many other rational numbers cannot be represented exactly) Or the results of a multiplication exceed the precision that is being used. Similarly adding/subtracting a very small number to a very large number can result in a loss in precision. By analogy suppose I said "take 199 away from 10000" but the human computer only worked to 3 significant figures, their final result would be close but inexact.

With a little thought you can see how the error becomes a significant fraction when you subtract the result of two multiplications. Here's an exact calculation: 5.55 x 5.55 - 5.44 x 5.66 = 30.8025 - 30.7904 = 0.0121 Now let's run this in a machine that only represents numbers to 3 significant decimal digits 5.55 x 5.55 - 5.44 x 5.66 output: 30.8 - 30.8 = 0

In all of these kinds of problems the final "==" can fail. so rather than x == y. it is better to see if they are approximately equal, abs(x-y) < delta where delta is typically a small number e.g. 0.00000001 An exact analysis of an appropriate delta depends on the accuracy of the machine representation, the input range and the formulas used.

Long skinny triangles are an example where you adding tiny values to large values.

Perhaps the demos work on your web page because your x,y positions are small integers, but it wont work in the general case.

jeffThompson commented 4 years ago

Amazing, thank you! Let me dig into this when I have a minute and will update the tutorial