Archive for the ‘thesis’ Category

computational geometry rant

Monday, January 14th, 2008

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”?

Workshot

Monday, October 15th, 2007

This showes my python based geometry server and algorithms. It is basically a implementation of computing a 2d celldecomposition (arrangement), and the display is done using pygtk and opengl, and twisted for the networking, a better combination then wx+twisted (I no longer have any timeouts, nor do I have to move the mouse to force processing of network events, and ctrl-c actually works). Other then that, like always, the code is not very good, but it works. The right showes the current bug being investigated – the shape on the left is symmetric, and the resulting graph on the right should be too, but it isn’t. Probably more numerical inaccuracies (lines that should be parallel but are not, etc.).

NShape Visibility Bug

Citations Ahead

Thursday, September 20th, 2007

Let’s get this out of the system. I’ve spent the last day doing this:

  1. learning to script dia with python
  2. finding a script for searching with googlescholar from python
  3. adapting it to get the citations for the first found document, assuming a search for the full title will always lead to the document with that title being first (seems reasonable).
  4. fixing the bugs and getting the picture below.

To get it running I did the following (there is probably a much simpler way):

  1. got the python-startup.py from dia sources (apt-get source dia-libs)
  2. copied it to ~/src/dia_python
  3. put there the files attached (alonutil.py, BeautifulSoup211.py, googlescholar.py, bibliography.py)
  4. export DIA_PYTHON_PATH=~/src/dia_python
  5. dia

The result is that dia has an extra menu entry in the Objects menu. It expects you to have selected a “Flowchart – doc” type (see the attached dia file), and then goes and expands it through google scholar, putting new nodes. Due to a bug/lack of understanding on my part, you have to refresh the display somehow, by dragging around, to actually see the new nodes.

Missing: identifying same objects instead of creating them again, citations by, clickable links so you can easily go to the web, export to bib file / aigaion, go wild.

Since I can’t actually upload any of the non image files (dia, py) I’ll put them here

citation generation