I actually thought this up around sometime in Feb 2007; I had been reading Sipser’s Intro to Computer Science text, and hallucinated the following abstract while drifting off to sleep:

This paper presents an isomorphism between the set of problems in P and the Natural Numbers, and an isomorphism between the set of problem in NP and the reals. Using this isomorphism the properties of the equivalent classes P and NP are investigated. A property is found which holds for one class but not the other, thus P != NP. The isomorphisms are then used to prove that the Continuum Hypothesis is false because of the relationship between P and NP.

It’s pretty likely that this approach would have a fundamental flaw, but if so, I don’t have enough background to know what it is. Hopefully, I will be able to gain insight on the problem while here at University. Specifically, I’ll begin with the question: What is the cardinality of P?

I am a dyed-in-the-wool geek. When I first moved into my apartment here at UCI, and found out that all my stuff didn’t quite fit into my room, what did I do about it?

I drafted the floor plan of my room, and made paper cutouts of all my furniture. Then arranged and re-arranged all the paper squares until I found a layout I liked. It was a rather tedious process, but it worked quite well. The paper was much easier to shuffle around than the furniture it represented.

Then, I decided that the corner where I put my desk was not very well lit; and instead of a lamp, I wanted ceiling lights. At a nearby Lowes I saw some under-counter lights, a pack of six 20-Watt Xenon pucks. Well, given that my desk sits in a recessed section of the room, and that a line of lights isn’t nearly as nice as, say, a half-ellipse, I had to figure out some way of generating the coordinates for the placement of those lights.

Originally I was going to do this by hand, on paper, so, I checked out the wikipedia article about the ellipse; which gave me a nice parameterized formulation.

where may be restricted to the interval .

Using this formula, I whipped up a program to generate the coordinates for the lights:

#include <QApplication>
#include <QtGui>
#include <QDebug>
 
int main( int argc, char *argv[] )
{
    QApplication app(argc, argv);
 
    QPixmap pix(100,100);
    pix.fill();
    QPainter painter(&pix);
    painter.translate(50,50);
    painter.setRenderHint( QPainter::Antialiasing );
 
    painter.setPen( QPen(QBrush(Qt::green), 1) );
    painter.drawPoint( QPointF(0.,0.) );
    painter.drawRect( -36,0, 72,24 );
 
    painter.setPen( QPen(QBrush(Qt::blue), 1) );
    painter.drawEllipse( -36,-24, 72,48 );
 
    painter.setPen( QPen(QBrush(Qt::red), 2) );
    for (int i=0; i<6; i++) {
        qreal t = 3.14159*(i+.5)/6.;
        qreal x = 36*cos(t);
        qreal y = 24*sin(t);
        qDebug() << "x: " << 36-x << " y: " << y;
        painter.drawPoint(QPointF(x,y));
    }
    painter.end();
 
    QLabel *label = new QLabel;
    label->setPixmap(pix);
    label->show();
 
    return app.exec();
}

Which, generated the output:

x: 34.7733 y: 6.21165 x: 25.4559 y: 16.9706 x: 9.31752 y: 23.1822 x: -9.31743 y: 23.1822 x: -25.4558 y: 16.9706 x: -34.7733 y: 6.21171

For quite some time now I’ve wanted to do a program that demonstrates Image Tiling using threads. Everyone should be familiar with the results of this technique, it’s used in Google Maps, Google Earth, NASA Worldwind, KDE’s Marble, and the like.

So, to begin I started off looking for example of how this is accomplished in the real world. I found a series of posts about Marble’s Secrets (Part I: Behind the Scenes, Part II: Walking in the shoes of Slartibartfast, Part III: The Earth in a Download). While these didn’t tell me what happens in the gory detail, it gave me enough of an idea that I’m not too terribly lost when wandering around the source code.

The first thing I noticed is that Marble doesn’t use the QGraphics framework, and they opted to do all their own painting (I assume they went to the trouble so that they would be able to do Spherical distortion on their quadtiles). So, I’m not able to get away with easily stealing stuff from Marble.

Track 2: Since I’ve already done one project that would breakup an image into tiles; The real core of the problem becomes threading the loading and unloading of these tiles. So I turned to Trolltech’s Mandelbrot example.

Before we begin, we should remember something about QThreads. Namely, that a QThread instance has affinity for the thread that created it, not to itself. I had to discover this the hard way; but the issue is discussed in slide 42 of Bradly Huges’ talk at Trolltech’s DevDays, 2007. The point of this is that, if you make a subclass of QThread called MyThread, then objects created in MyThread’s constructor actually reside in the thread that instantiated MyThread. I initially expected them to reside in their own thread, to which the MyThread class would provide an interface. So, from a software engineering perspective, the thing to do is create a QThread and instantiate your worker objects, then move those objects to the QThread.

Now, grab a big image to play with, a map of the London underground, which is crisp and has detail that you won’t be able to decipher when zoomed out. (It’s also not geographically correct, hence the need for ‘walklines’)

From an engineering point of view it’s really convenient to be able to map from image coordinates and zoom level to a designated and unique TileId. This allows us to have very fast lookups for images that will be kept in hashtables and caches. To accomplish this we shamelessly swipe the TileId class from Marble/src/lib. A quick check of it’s internals reveals that it will be suitable to our needs.

TileId::TileId( int zoomLevel, int tileX, int tileY )
  : m_zoomLevel( zoomLevel ), m_tileX( tileX ), m_tileY( tileY )
{
}
 
TileId::TileId()
  : m_zoomLevel( 0 ), m_tileX( 0 ), m_tileY( 0 )
{
}
 
bool operator==( TileId const& lhs, TileId const& rhs )
{
    return lhs.m_zoomLevel == rhs.m_zoomLevel
        && lhs.m_tileX == rhs.m_tileX
        && lhs.m_tileY == rhs.m_tileY;
}
 
uint qHash( TileId const& tid )
{
    quint64 tmp = ((quint64)(tid.m_zoomLevel) << 36)
        + ((quint64)(tid.m_tileX) << 18)
        + (quint64)(tid.m_tileY);
    return qHash( tmp );
}

We also want to add some convenience functions for the translation of TileId’s to actual image sizes. To do this we first add tileSizeX and tileSizeY parameters to the TileId header, and prototypes for the conversion functions.

class TileId
{
    public:
        ...
        QRect rect() const;
        QSize size() const;
        ...
    private:
        ...
        static int tileSizeX;
        static int tileSizeY;
};

And the requisite definitions:

TileId::tileSizeX = 25;
TileId::tileSizeY = 25;
 
QRect TileId::rect() const
{
    return QRect( m_tileX, m_tileY,
                  m_zoomLevel * TileId::tileSizeX + 1,
                  m_zoomLevel * TileId::tileSizeY + 1 );
}
 
QSize TileId::size() const
{
    return QSize( TileId::tileSizeX+1, TileId::tileSizeY+1 );
}

The reason for the +1’s is that we wish to have one pixel of overlap on all our tiles, at all zoom levels. This slightly improves image rendering within the QGraphics framework. We’ll be treating the rect() as the clipped tile out of the source image, and the size() as the actual size that the tile will be once on screen. Given these formulae, a level 1 tile will mean native resolution, while a level 10 tile will be zoomed way out.

Initially I’d decided that we would load and unload the tiles dynamically onto/from a subclass of QGraphicsScene. After writing some code, and browsing around I realized that this may not be the best plan. The QGraphicsScene is really supposed to be a model for attached QGraphicsView’s, it’s setup so that you can have more than one view attached to a single model. I browsed around the internal code of QGraphicsView to see where it asks for rendered updates of the QGraphicsScene but wasn’t really able to find it. Anyway, it’s not clear to me that dynamic loading and unloading of QGraphicsPixmapItem is really the right way to go about this, especially so if I don’t have easy access to a list of regions (and zoomlevels) being viewed.

Looking back at the Marble project. They solved this problem by creating their own MarbleMap class that interacts with a custom MarbleModel. The MarbleMap gets Tiles (images), Vectors (political borders, coastlines), and Placemarks from the MarbleModel. It then uses this info to render a picture of the Globe with appropriate image projections by composition of layers. (Actually, MarbleMap::paint() calls MarbleModel::paintGlobe() and then paints the layers on top of that. Naturally they both use the custom GeoPainter class).

Right now I’m somewhat lost on where to head next, so I’ll be punting this topic until next weekend. So far my options seem to be:

1. Make custom rendering widget and associated model, ala Marble
2. Go ahead with the Graphics Framework, but with the caveat that users might not be able to use more than one QGraphicsView on the customized scene.
• custom QGraphicsPixmapItem that knows how to fetch and delete it’s image data in it’s own QThread. The drawback being the spawing of as many threads as there are tiles.
• potentially might have to create custom QGraphicsView that explicitly hand viewing parameters to a custom QGraphicsScene
• the custom QGraphicsScene could manage a set of worker threads, and store the pixmaps in a cache, then the QGraphicsScene is responsible for all the memory management of all items in the scene. At the moment this seem the most attractive path.

So, last Sunday, I purchased a Futon through Craigslist. On my trip back from picking it up, I lost a piece. A certain plastic part that fits in a wood slot, so it can slide up and down the rail when you change from couch to bed. A part that I would never be able to find in a hardware store. I don’t have any tools for machining such a part, though it would not have been difficult to do so. I opted to goto on of the three machine shops on campus and inquire wether or not I could have such a part made. (Since the futon has 4 of these parts, I provided an example to be replicated). The man in charge of the shop had a policy of not allowing crazy college students to use his machines until after they’d taken his class (a policy made from past experience). Since it is currently summer, the class would not be available until Fall. But, being a really nice guy, and sensing that I would not really want to pay him a full-time rate for making such a small piece, he offered to trade me for it. He’d make the part, I’d clean his shop.

After only a day, he called me back, with a remarkably nice part. (It actually looks better than the 3 other such pieces that have acquired much wear from the previous owner.) He claimed that it took him only about a half hour to make, so I began to clean two of his machines, which didn’t take long. During the process, I noticed one machine, in the corner, that was in dire need of cleaning, and I offered to do that one as well, since I finished the other two so quickly. I convinced him to allow this cleaning, which took an entire hour (and I was hot and sweaty at the end of it). He was actually impressed with the detail of cleaning I did on that machine, and I know it saved him much work, because it was a difficult area to get into (luckily I have a slender body frame).

So, I got a custom piece for my futon, and the machine shop got 1.5 hours of ‘free’ manual labor. I’d consider that a fair and equitable exchange. Capitalism works.

My first week has been rather nice and relaxing. I’ve got much of my paperwork covered with respect to RAship, ID card, finding shops and stuff around the area. My roomates are cool and mellow (and have similar philosophical/religious views). So far, it looks like I’ll be working on Information Flow in SpiderMonkey. The dissertations that I’ve been assigned to read have already given me some ideas.

Object tagging: In order to implement Information Flow each object or data field (henceforth entity) is tagged with a Top Secret/Secret/Sensitive/Unclass label. A body of code (or xml file) then describes a policy that details how each entity is tagged after interacting with other entities. So if A is tagged secret, and B is tagged secret, and C = A+B, a usual default policy is to have C tagged secret. There is, however, no real reason why this means of describing object interaction should remain specific to security policies. I don’t have any examples at hand, but the general ability for programmers to be able to tag objects, and then describe a semantics of tag interaction, would probably have many other uses.

I am finally moved in to my place at UCI. It turns out that I own 1 Toyota Tundra load of books, and 2 Chevy Cavalier loads of miscellaneous crap. Also, I found out that, as a result of stuff expanding to fill available space, it’s impossible to compact the junk from a 2 bedroom apartment into a single room; and that the stuff you own owns you.