One crucial feature that CiteULike lacks is the ability to remove entries en masse; the only way to remove several entries is to go to each entry’s page, click on delete, and confirm the deletion– that’s about 3 clicks per removal. Imagine if you want to remove *all* of your entries!

That was the problem I encountered as I attempted to clear my account of all the papers not related to my research, so I decided it’d be worth the time to write a little Greasemonkey script to remove all the entries. Unfortunately, in addition to being very out of practice with Javascript and the DOM, I’ve never used Greasemonkey before, so I ended up writing a two-script hack. The first script loads the first entry on my CiteULike library page, and the second script deletes any entry once its page is loaded; together they eliminate entries one by one until none are left. Inelegant, but much more inefficient than doing it by hand.

Here’s the code for the two scripts– just remember to retask them to point to your citeulike account, and to DISABLE under Greasemonkey or delete them after you’re done.

// ==UserScript==
// @name           First citeulike article
// @namespace      http://tangentspace.net
// @description    Loads first citeulike article
// @include        http://www.citeulike.org/user/swiftset
// ==/UserScript==
 
articlelist = document.evaluate("//div[@class='list']", 
document, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, 
null).snapshotItem(0);
 
allarticles = document.evaluate("//a[@class='title']", 
articlelist, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, 
null);
 
document.location.href = allarticles.snapshotItem(0).href;

// ==UserScript==
// @name           Delete Citeulike Article on load
// @namespace      http://tangentspace.net
// @description    deletes any citeulike article on load of the article info page
// @include        http://www.citeulike.org/user/swiftset/article/*
// ==/UserScript==
 
allhidden = document.evaluate("//input[@name='user_article_id']", 
document, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, 
null);
anelem = allhidden.snapshotItem(0);
 
document.location.href="http://www.citeulike.org/delete?user_article_id="
+anelem.value+"&"+"from=%2fuser%2fswiftset";

Possibly relevant posts:

• Java Postscript interpreter! (12/22/2004)
• Code Highlighting Added (2/2/2005)
• SSH Key Authorization (9/30/2005)

My officemate asked me a Matlab question that’s worthy of consideration: what is a fast method for locating a submatrix within a matrix? In his case, we were dealing with two dimensional matrices, but to make it more challenging, attempt it with matrices of arbitrary dimension.

Some history: I coded a solution to this problem during my undergraduate research, to use in registering biomedical volumes. When I started working on the project, there were some reference subvolumes that had been extracted from various volumes, and exactly where they’d been extracted from had been lost. The data sets were relatively large, so the code had to be fast … too bad I can’t recall my solution off the top of my head.

It’d be intereresting to compare the performance of various solutions. I’ll try to recreate mine.

Possibly relevant posts:

• pseudo3d navigation (1/1/2006)
• Axiom vs other CASes (12/18/2003)
• Topologies out the wazoo! (3/24/2006)

Via Ars Mathematica, I came across a paper describing TeX’s math layout algorithm and offering an implementation of it in Standard ML. Sweet! I only wish I had come across this paper (it is about 10 years old) when I was daydreaming about a WYSIWYG gui interface that worked for multiple CASes. If I ever get back around to it, this will be really useful.

Possibly relevant posts:

• An Intro to Typography (5/31/2005)
• Math parser update (6/22/2005)
• pseudo3d navigation (1/1/2006)

I discovered a painful lesson today. I’m trying to put together the bookmark management system I mentioned earlier, using Ajax, just because I haven’t used PHP in months or dabbled in serious Javascript in years, and I’ve never used Ajax. Got to keep those skill sets up! Also I’m avoiding studying.

So, I got the MySQL database set up, the tables working, and wrote up the PHP backend, all of which went fairly smooth. Then I start delving into the Ajax side of things and everything starts going bonkers– figuring out how to do cross platform XML parsing in plain Javascript seems to be beyond me, so I get Sarissa (which is so lightweight I haven’t noticed it’s there, much less worried about its API), and that problem’s solved. Next, I run into the weirdest problem: all my POSTs are disappearing! It’s like any requests sent via POST are lost, and when I document the POST handling code in the PHP backend with error_log, nothing shows up in the errorlog. So, I spent *hours* trying to figure out what the problem is, and where it is: is it the Ajax, or the backend…

Turns out it’s neither. I’d noticed earlier that since I left the action attribute on the form empty, the interface page reloads itself everytime you click on the submission button– an annoying fact, but one I couldn’t figure out how to remedy, and which didn’t seem important. After all else failed, I paid more attention to this, and it seems that whenever the page reloads, it chops off the ongoing Ajax transaction and submits a GET query. This makes no sense to me, because the page is HTML, so it should be calling itself on reload, and the only place where the cgi is called is in Javascript code, so it shouldn’t know where to submit data. If any of that makes sense to you, please explain it to me.

But the solution is simple: specify the button type to be button and the page won’t reload itself when you click the button. Turns out that the default type of a button is submit (I was leaving it blank). It seems more logical to me to make the button do nothing by default.

Possibly relevant posts:

• REQ: Development book recommendations (7/29/2007)
• Code Highlighting Added (2/2/2005)
• Greasemonkey hack for CiteULike article removal (6/20/2008)

I wanted to give PyCairo programming a go, and I’ve always been fascinated by some of the simple but important issues in computational geometry, like Voronoi diagrams and Delaunay triangulations, or in this case, calculating the boundary of the convex hull of a set of points.

Here’s the code: framework.py and convex_hull.py; PyGtk and PyCairo are required. The interface is basic: you enter points by clicking in the window, and the program updates the convex hull and its boundary as you add the points (you can resize the window during operation if you really want to pack in the points … to verify the probably exponential running time of the algorithm ).

The algorithm used to find the boundary is painfully obvious in hindsight: if an edge connecting two points in the set is such that all the points in the set lie to one side of it, then that edge is on the boundary of the hull.

My next goal is to orient the boundary– an algorithm for this follows immediately from an algorithm for the orientation of the boundary of a generic triangle, but I haven’t yet found a suitable algorithm. All the algorithms I’ve come up with seem forced, and more important, hairy to code.

(While I’m talking about Python and mathematical graphics, check Ghost Diagram out for a beautiful and more serious example of the possibilities)

Possibly relevant posts:

• Compiling Python Extensions w/ Mingw32 (5/30/2005)
• TeX/MetaFONT/MetaPOST (2/16/2003)
• The year of windows programming (1/1/2006)

I finally got a working implicit curve tracer running in Mathematica. It has severe limitations: the user must supply a seed point, tolerance, and step size, it only traces one connected curve from a given seed point, and if the curve escapes to infinity, so will the tracer.

On the upside, the algorithm does not require any analytic information– a density field would work as well as an analytic expression; all that’s necessary is that the surface is specified by the zero-level set of some function continuously differentiable on a compact neighborhood of the surface (in particular, normals must exist at each point in this set).

Overall, it’s a good starting point for a more robust algorithm.I’ve uploaded the Mathematica notebook– it’s uncommented, but is short enough to be self-explanatory, given the overview in this post. I’ll post any updates in the same place. Here’s a sample of its work for the surface , with starting point

Mathematica’s ImplicitPlot

tracing code’s results

How it works: Given a point on the surface, the outer normal is calculated using a 2nd FDD scheme (the stepsize for this FDD is one of those annoyingly necessary parameters), and the counterclockwise tangent vector is found by rotating the normal. Then a step is taken along this tangent vector (size determined by another parameter) to start looking for another point on the surface. The next surface point is determined by finding a root of the function starting from this candidate point, using Newton’s method. Proceeding in this manner until you return close to the original point (another parameter determined how close that it), you get samples of the curve.

Essentially the same algorithm can be used in 3D to polygonize surfaces, except instead of sampling points, you’re sampling triangles in the tangent plane, and instead of having a 1-dimensional front, the algorithm proceeds along multiple 2-dimensional fronts. I could probably adapt some of the techniques used to resolve the more complicated problems in the 3D regime to ease some of the restrictions of the code.

My reference was A marching method for the triangulation of surfaces by Hartmann. BTW, how can I get my hands on a copy of Hartmann’s paper “Numerical implicitization for intersection and Gn-continuous blending of surfaces”, without actually paying for it– or even a paper with equivalent ideas? Apparently Caltech doesn’t have it available electronically or in a paper copy.

Update While considering how to analyze the error involved with approximating an implicit curve using this algorithm, I realized that this curve tracer is pretty much looking at an implicit curve as the solution to an ODE and solving it using Euler’s method. The projection step is like a reinitialization process that helps keep down cumulative error.

Possibly relevant posts:

• Implicit Equation Grapher (5/28/2005)
• Simulated Annealing (5/26/2006)
• Q: convexity of level sets (1/29/2008)

I spent about three hours on Friday night converging toward an install process for pbrt– the instructions on the CD that come with the book are outdated, and the forums on pbrt weren’t incredibly helpful. It turned out you have to install some auxiliary libraries first– this was the hard part: I found I had to delve into config.log to solve some problems. So, if you’re interested in compiling pbrt (I expect you probably found the site through Google, so welcome ), here’s the process that worked for me.

These directions assume bash is being used, and that your home directory is /home/gittens. Also, due to the use of the pre tag, some of the longer instructions may be partially occluded by other page elements. To see them in their entirety, copy and paste them into a text editor.

First get the IlmBase and OpenEXR libraries from openexr.com. Install IlmBase with

./configure --prefix=/home/gittens/usr
make; make install

then install OpenEXR with

LD_LIBRARY_PATH=/home/gittens/usr LDFLAGS=-lpthread ./configure --prefix=/home/gittens/usr
make; make install

Now you should be able to install pbrt directly (I’m assuming you have the other, more standard-issue libraries already installed, such as libtiff and zlib– if not, these libraries have been around so long that installing them to /home/gittens/usr should be a streamlined, painless process). There are a couple of changes to be made to the Makefile:

• change the EXRINCLUDE, EXRLIBDIR variables to point to /home/gittens/usr/include/OpenEXR and /home/gittens/urs/lib.
• If you want to instrument the code for debugging with, e.g. gdb, change the line OPT=-O2 to OPT=-g. pbrt will run slower, but being able to debug is necessary for some exercises in the book, and might be useful besides.

Then a simple make should suffice; the pbrt executable is in the bin directory.

If additionally, you want to use the tools in the pbrt distribution (most useful is the exrtotiff application, that converts pbrt’s native EXR output format to TIFF– you’ll probably want this unless you have a working EXR viewer lieing around, and how likely is that?), you need to edit the Makefile in that dir also:

• Change the OPT to -O2 from -g (you’re not going to be debugging any of the tools, right?)
• Change the CXXFLAGS from $(OPT) -I/sw/include -I$(EXRDIR)/include -I$(PBRTDIR)/core to -I/home/gittens/usr/include/OpenEXR -I$(PBRTDIR)/core
• Change LDFLAGS = -L$(EXRDIR)/lib-linux to LDFLAGS=/home/gittens/usr/lib

To run pbrt, you’re going to need to make sure that the auxiliary libraries are in the linker’s search path and set up pbrt’s search path.
Write the following sh script into setupenv.sh:

export LD_LIBRARY_PATH=/home/gittens/usr/lib
export PBRT_SEARCHPATH=/home/gittens/work/pbrt-1.03/bin
export PATH=$PATH:PBRT_SEARCHPATH

and run this before you invoke pbrt.

Possibly relevant posts:

• User directory python package installation (3/21/2007)
• Circuit Macros helper script (1/31/2005)
• Installing TeTeX latex packages (2/28/2005)

All development technologies I’d like to have much more hands-on experience in. Best-of-the-best book recommendations enthusiastically welcomed– and by best-of-the-best, I mean on par with the Perl Book, Programming Python, or Javascript: The Definitive Guide– rather more leading towards huge tomes of specifications than tutorials.

Possibly relevant posts:

• HTML Button troubles (9/13/2007)
• Joys of Python (5/16/2005)
• Scheming out loud (2/22/2005)

Remember a one-form can be identified with a functional

on the set of piecewise differentiable curves . It can also be identified with a vector field.

In special cases, a one-form can also represent the total differential of a function: if there is a function such that and , then since the chain rule gives , the one-form is called the differential of the function . A one-form is called exact if there is some such that .

Note that if , then

which shows the integral of an exact one-form is independent of the path taken– it depends only on the endpoints. In particular, the integral of around any closed path is . In physics, conservative forces (fields) are exact one-forms.

What if someone gives you a one-form and asks you if it is exact? How could one determine an answer, or maybe even find a function with as its differential?

First, if , (assuming is smooth), then . The differential of a one-form is the two-form . So, if , then . One-forms such that are called closed.

By Stokes’ theorem,

if is a simple region, where . Consequently, for closed forms, Applying Stoke’s theorem to the illustration below gives that if is a closed form, so closedness implies path independence.

Clearly from an earlier comment, the first prerequisite for being exact is closedness. In fact, you can show that in star-shaped domains, closedness implies exactness. Basically, you fix a value at , the center of the star, and define for any point in the domain, where is a path from to . Taking derivatives shows any such has as a differential.

If is exact on two domains and , and is connected, then is exact on . The idea is that if on for , then on , which is connected, so on . Let , then the function which takes the values of on and on satisfies on .

A powerful consequence of the fact that a closed one-form is exact in a star-shaped domain is that locally any closed one-form is exact. It then follows readily that a path integral of a closed one-form can be calculated in ‘exact patches’. More specifically, if is a closed one-form on and is a smooth path in , then there is a subdivision and a collection of open subsets of such that maps into , and the restriction of to is the differential of a function . For any such choice of subdivision and open sets, if ,

The proof of this assertion is topological. First, for each point in , there is a neighborhood in which the form is exact. The preimages of these neighborhoods under forms an open cover of , of which a finite subcover can be chosen.

An application of the Lebesgue number lemma tells us that there’s a fine enough refinement of this cover into sets such that the image of each interval is contained in an . Applying local exactness gives the result.

Possibly relevant posts:

• Cauchy’s theorem via Homotopy (8/8/2007)
• 1-forms and topology (7/27/2007)
• A cool proof of what exactly? (4/29/2005)