Tuesday 20 July 2010

An uncertain existence

My contract at Imperial finishes at the end of the month. NERC have agreed in principal to additional funding for a nifty graphical interface to the Entangled Bank database that I have been creating for the last year. However, contractual issues between are delaying the funding and indeed potentially may scupper the whole exercise. Presuming the money is going to arrive, I will then have to apply to do the work in an open competition.

Such situations are common in academia and extremely stressful to live through, especially when it affects others. I am lucky that Mary is very supportive but this situation weighs heavily on our lives. How long do I wait for the funding to come though? - these things can take months. Should I apply for another post-doc and move the family for yet another short-term contract, or find a (probably less interesting) permanent non-academic post? Applying for jobs is very time consuming so these are important decisions. Write papers or job applications? Stop and establish a long-term relationship with a place or another temporary holding position? The older we, and Ben get, the more stability and a home beckon.

Wednesday 7 July 2010

PostGIS select across the +180/-180 meridian with a bounding box

Many geographical information systems, e.g. PostGIS, treat the earth as a Cartesian plane, despite data being in a geographical coordinate system with latitudes and longitudes. This is annoying when, for example, you want to select geometries that overlap, or are within, a bounding box that crosses the +180/-180 meridian. I have just implemented PostGIS cross +180/-180 meridian bounding box searches in the Entangled Bank as follows :

To select geometries that OVERLAP a box that extends from 90E over the meridian to 90W intersect (&&) the_geom with a pair of boxes either side of the meridian:

the_geom && ST_MakeBox2D(ST_Point(+90, -90), ST_Point(+180, +90))
OR the_geom && ST_MakeBox2D(ST_Point(-180, -90), ST_Point(-90, +90)

Select geometries that are WITHIN the box is slightly more complex as those that intersect the line that bounds the select box must be excluded. In PostGIS using the well-known-text format to code line the query is:

the_geom && ST_MakeBox2D(ST_Point(+90, -90), ST_Point(+180, +90))
OR the_geom && ST_MakeBox2D(ST_Point(-180, -90), ST_Point(-90, +90)
AND NOT the_geom && ST_LineFromText('LINESTRING(+180 +90, +90 +90, +90 -90, 180 -90)')
AND NOT the_geom && ST_LineFromText('LINESTRING(-180 +90, -90 +90, -90 -90, -180 -90)')"

When I have time I shall write the required function.



Tuesday 6 July 2010

How to prune a tree given a list of nodes to include?

I have a tree and a list of nodes that define a subtree. How do I prune the tree?

It took me a while to work this one out, so to save anyone else the trouble here is some pseudo code showing how I went about it.

Begin your tree by setting the least common ancestor of the node list as the root node, then 'walk the tree' using the subroutine walk: walk(parent, parent, 0) :

sub walk (parent, ancestor, distance from ancestor to parent) {

For each (child of parent with nodes) {

Case (Count(children) of parent with nodes) {
0: Return
1: Case(Count(grandchildren of child with nodes)) {
0: add_child()
1: walk(child, ancestor, distance())
>1: add_child()
walk(child, child, 0)
}
>1: Case(Count(grandchildren of child with nodes)) {
0: add_child()
1: walk(child, ancestor, distance())
>1: add_child()
walk(child, child, 0)
}
}
}
return
}

Where, 'with nodes' is true where the node or any descendant nodes are in the list.

add_child(ancestor) adds the child as a descendant of the ancestor with distance from the ancestor to the child.

distance() sums the distance from parent to child to the combined distance from the ancestor to the parent calculated.