computational geometry rant

I have my own version of an arrangement creation code (side note: so it is arrangement, not arrangment! cgal is driving me crazy!). This version works iteratively, and as a result very very slowly. But it does work, and I’ve used it quite a lot and know that the output seems ok. I don’t have enough tests and especially enough good tests to qualify that remark furthur. Enter a CGAL based sweep (batch) version which is totally fast and amazing, so what’s the problem? the results look (when displayed) virtually the same, but are different:

my old results: <DCEL: 7045/28416/7165>

new code results:  <DCEL: 7086/28566/7199>

At first I thought this was due to the creation of ~0 length edges due to different underlying numerical types I and CGAL use. That is a different problem I’m yet to handle, but for this particular instance of the computation it wasn’t the problem, as evidenced by this tests:

[he for he in d.edges if he.norm() < 1e-6]

So what’s the problem? I’m not sure. Which code is correct? I’m not sure. How do I check it? I need a set of postconditions, and then just test each. Work I didn’t set out to do. Doh.

p.s. I guess a first test should be for almost zero area faces – which means basically bogus faces. Altough I think there should be none.
p.p.s given n numbers, how do you bin them into m bins in a way that “seems natural”?

Leave a Reply