Grasshopper

algorithmic modeling for Rhino

Hey people,

Does anybody know some good (and tested) library (.net) for robust geometry?

Currently I try to implement exact arithmetic, and the geometry predicates formulated by Jonathan Richard Shewchuk.
But this isn't an easy task.
So, if there is no library, maybe someone wants to join, implenting this kind of stuff...

greets
Mark

Views: 396

Replies to This Discussion

Hey Tom,

Good questions!
Independence is the major reason, but also exactness...

A simple TestCase which fails hard:

(sure, this isn't a real-world example, its just simple arithmetic. But I guess important to be correct/robust)

[TestMethod]
public void SimpleArithmetic()
{
    double a = 12312.23223213;
    double b = 12455343.123187843;

    var xa = new ExactNummeric(a);
    var xb = new ExactNummeric(b);

    ExactNummeric xr = (xa + xb + xb) * xa * xb;
    ExactNummeric xrs = (xa * xa * xb + xb * xa * xb + xb * xa * xb);
    ExactNummeric xre = xr - xrs;

    double r = (a + b + b) * a * b;
    double s = (a * a * b + b * a * b + b * a * b);
    double e = r - s;

    double xrd = xre;

    Assert.AreEqual(0d, xrd);
    Assert.AreNotEqual(0d, e);
}

The second Assert:

Expected = 0
Actual = 1024 (variable 'e')

(For testing, there are .cs files attached)


gaußian solver
I'm going to have a look at this. thanks to point this out. I had a quick look; looks promising. But I have to have a deeper look... In the meantime, thanks...


Attachments:

It's not simple arithmetic. You found out limitations of floating points numbers.

Aside from that your testcase is comparing two floating point numbers without a "epsilon" value (some would argue this to be mortal sin). There are much more cases where two floating points will not be exactly the same.

You correctly point out that there's a limitation around 15 to 17 digits. (s/r are about this size). In proportion the error between the two numbers is about 2.67E-16.

Not sure what you're trying to accomplish with the ExactArithmatic / ExactNumber? But if you change the type from double to decimal in C#, this testcase will succeed.

decimal a = 12312.23223213M;
decimal b = 12455343.123187843M;
decimal r = (a + b + b) * a * b;
decimal s = (a * a * b + b * a * b + b * a * b);
decimal e = r - s;

// e = 0

.NET floating point numbers:

https://msdn.microsoft.com/en-us/library/9ahet949.aspx|

Floating point guide: http://floating-point-gui.de/

This is also why you never should compare floating point numbers to check if they're exact, but if they're close enough. 

I still have no clue where you would want to be going from here? What problem are you trying to solve?

RSS

About

Translate

Search

Photos

  • Add Photos
  • View All

© 2023   Created by Scott Davidson.   Powered by

Badges  |  Report an Issue  |  Terms of Service