Zim

Wie eventuell aus dem Countdown zur Veröffentlichung von Fedora 13 im rechten Rand zu schließen war, ist momentan Linux das Desktop und Laptop Betriebssystem meiner Wahl. Ohne weiter ausholen zu wollen, möchte ich nur anmerken, dass diese Wahl nicht aus ideologischen sondern aus technischen Überlegungen resultiert. Die Hardwareanforderungen aktueller Windows Versionen haben sich zu weit von den mir zur Verfügung stehenden Tatsachen entfernt als dass ein vernünftiger Betrieb möglich wäre. Andererseits ist eine Weiterverwendung veralteter Windows Versionen mit zu vielen, nicht zuletzt sicherheitstechnischen, Nachteilen verbunden.

Die eigentliche Herausforderung, wenn man Windows gänzlich den Rücken kehren möchte, besteht kaum mehr in Inkompatibilitäten wie es scheint, sondern vor allem im Bruch mit Gewohntem. Damit meine ich nicht das Betriebssystem, denn damit hat man als Benutzer kaum Kontakt, sondern die Anwendungen. Ich kann mir gut vorstellen, dass in manchen Bereichen für Linux keine adäquaten Entsprechungen für tausende Euro teure kommerzielle Software zu finden ist. Dennoch möchte ein Beispiel für (m)einen Fall bringen, wo eine Anwendung trotz kleinerem Funktionsumfang eine andere ersetzen kann.

Zim

Eine meiner Lieblingsanwendungen unter Windows ist OneNote. Als Notiz- und Logbuch hat sich dieses Programm als sehr nützlich erwiesen. Die Hauptvorteile gegenüber einem Papierblock sind für mich die Suchfunktion, der Umgang mit Markierungen (Schlagworten) und nicht zuletzt die Möglichkeit, schnell und einfach Bildschirmausschnitte in den Text einzufügen. Da ich beinahe sämtliche Information über den Bildschirm verarbeite, ist das Speichern von Bildschirmausschnitten das allgemeinste Interface. Als Naturwissenschaftler verwende ich diese Technik sehr oft, um Diagramme, die von einem beliebigen Programm erzeugt wurden, in das elektronische Notizbuch zu „kleben“.

Jene Linux Anwendung, die OneNote im Funktionsumfang am nächsten kommt ist vermutlich BasKet. Trotzdem schreibe ich diesen Artikel, weil ich für mich Zim als geeignetste Anwendung befunden habe. Zim wird vom Autor als „Desktop Wiki“ bezeichnet. Was die Textverarbeitung betrifft, wird damit das meiste bereits erklärt. Wer jemals einen Wiki Artikel geschrieben hat, kennt das Prinzip.

Was Zim für mich aber perfekt macht, denn es ist beileibe nicht das einzige Desktop Wiki, sind drei Plugins, die folgende Funktionen zur grundlegenden Wiki Funktionalität hinzufügen:

  • Es ist möglich Schnappschüsse vom ganzen Bildschirm, einzelnen Fenstern und frei wählbaren Ausschnitten zu machen.
  • Es ist möglich, Formeln einzufügen, die man in einem separaten Dialog per LaTeX Syntax formulieren kann.
  • Eine Versionsverwaltung kann verwendet werden, um Änderungen an den Notizen zu verfolgen.

Zur absoluten Perfektion fehlen meiner Meinung nach nur zwei Features:

  • Schlagworte (Tags) – ein für die Zukunft geplantes Feature
  • Versionsverwaltung mit Git (statt Bazaar oder Subversion) – Gewohnheit

Zim in Fedora

Leider enthält Fedora, selbst in der noch nicht freigegebenen Version 13, nicht die aktuelle Version von Zim. Man findet aber in Bugzilla den Bug 563844, der neben einer aufschlussreichen Diskussion auch einen Link auf eine aktuelle SRPM enthält. Wie man daraus eine installierbare RPM baut erfährt man (neben sicherlich unzähligen anderen Stellen) im Fedora Wiki.

Virtuelle Übersiedlung

Die vergangene Woche hat ein paar virtuelle Neuerungen gebracht. Ich habe meinen privaten Server auf eine neue Hardware umgezogen. Tatsächlich geht es zwar genau genommen um virtualisierte Hardware, aber mit dem Umzug haben sich die diversen Ressourcenlimitierungen nach oben verschoben, sprich mehr Speicher und mehr Leistung.

Redmine

Der Grund für die doch etwas aufwendige Aktion war ein mehr oder weniger fehlgeschlagener Versuch, die das Projektmanagement-Tool Redmine als Ersatz für das bisher eingesetzte Trac auszuprobieren. Leider stieß mein alter Server dabei an seine Grenzen und verweigerte für kurze Zeit sogar die Annahme von E-Mails.

Weil ich einen Umstieg schon seit einem Jahr immer wieder überlegte, nahm ich die Situation zum Anlass um mit meinem Provider die Optionen zu besprechen. Mir wurde ein Upgrade angeboten, das sich heute leider als ungültig erwiesen hat. Letztendlich ist der einzige Unterschied eine Monatsmiete, weil ich beide Verträge nur mit einmonatiger Bindung abgeschlossen habe.

Den für Redmine notwendigen Ruby Stack habe ich aus den aktuellen Quellen selbst kompiliert, weil die Versionen in den CentOS Repositories für diese junge Software stark veraltet sind. Ruby stellt mit den gut unterstützen Gems eine gute eigene Paketverwaltung bereit.

CentOS

Weil ich auf meinem Laptop seit einiger Zeit auf die Linux Distribution Fedora setze, habe ich meine Distributionswahl am Server überdacht und statt Debian auf das Fedora-ähnliche aber auf den Servereinsatz aufgelegte CentOS gesetzt. Vom Geist der Revolution beflügelt, habe ich mich auch gleich versuchsweise von Apache als Webserver verabschiedet und auf Nginx umgestellt. Die gerade angezeigte WordPress wird entsprechend von PHP-FPM ausgeführt.

Für die Mailserver Infrastruktur verlasse ich mich weiterhin auf das bewährte Gespann von Dovecot und Exim. Weil mein Server meine zentrale Sammelstelle für alle E-Mail Konten ist (per Fetchmail), wollte ich hier nichts riskieren und sah auch wirklich keinen einzigen Grund für eine Veränderung.

VCS

Meine alten Subversion Repositories habe ich natürlich unverändert kopiert. Daneben habe ich mit Hilfe von Gitosis eine für meine Zwecke perfekte Git Verwahltung eingerichtet, die (wie svn+ssh) unter einem einzelnen Systemaccount und einer Sammlung von autorisierten öffentlichen Schlüsseln beliebig viele Git Repositories mit getrennt einstellbaren Zugriffsrechten zur Verfügung stellt. Nebenbei war die Unterstützung von Git und Subversion einer der Mitgründe für den Umstieg von Trac auf Redmine.

Fertig

Also genug Fachjargon. Fazit: Ich habe einige glückliche Stunden mit meiner virtuellen „Immobilie“ verbracht. Nur damit die Änderungen nach außen hin nicht völlig unbemerkt bleiben habe ich auch gleich das WordPress Motiv geändert.

Enabling the suspend hotkey in KDE4

There are several reports of problems with the suspend hotkey on KDE4 [1] [2]. And there is even a bug report on that issue. Naturally, I wouldn’t write about this if I hadn’t experienced the same problem myself. I solved it by slightly modifiying the approach described at Linux Basement, avoiding the need to create a dedicated shell script somewhere.

This might not have been possible in KDE 4.2 (I haven’t verified), but it is in KDE SC 4.4. The Input Actions dialog (under System Settings) allows for the configuration of DBus calls from hotkeys. This was configured fast and works painless. I have exported the hotkey group and pasted the content below. To use it, save this as PowerManagement.khotkeys and import it in the Input Actions dialog.

[Data]
DataCount=1

[Data_1]
Comment=Power management mappings of XF86 events
DataCount=1
Enabled=true
Name=Power Management
SystemGroup=0
Type=ACTION_DATA_GROUP

[Data_1Conditions]
Comment=
ConditionsCount=0

[Data_1_1]
Comment=Enables suspend hotkey
Enabled=true
Name=Suspend
Type=SIMPLE_ACTION_DATA

[Data_1_1Actions]
ActionsCount=1

[Data_1_1Actions0]
Arguments=
Call=org.freedesktop.PowerManagement.Suspend
RemoteApp=org.freedesktop.PowerManagement
RemoteObj=/org/freedesktop/PowerManagement
Type=DBUS

[Data_1_1Conditions]
Comment=
ConditionsCount=0

[Data_1_1Triggers]
Comment=Simple_action
TriggersCount=1

[Data_1_1Triggers0]
Key=Sleep
Type=SHORTCUT
Uuid={c1706a53-bde8-4364-b0af-71e9c1be6b3f}

[Main]
AllowMerge=true
ImportId=Power Management
Version=2

WebDAV on Windows Vista & Windows 7

There are quite a number of tales of woe around that topic. I had to find that out when I experienced some trouble myself today. If you’re in the same situation skip right down to the last two lines of this posting, the stuff in between just details the problem to associate the solution to the problem for the search engines.

My intention was to connect to my freshly set up  WebDAV directory served by Apache. The setup on the server side was quite tedious as well, but as expected, there are countless howtos around and one just has to put the pieces together as usual. The real problem however arose, when I starry-eyed tried to connect to that online directory using Vista’s „Map Network Drive …“ dialog. After some steps into the wizard that always gave me the error popup saying „The folder you entered does not appear to be valid“.

Well that soon let me drop to the beloved command line. But using net use W: https://example.com/davroot was answered by „System error 67 has occurred“ and „The network name cannot be found“. Using net use W: \\example.com@SSL\davroot gave no improvement.

I will spare you my other trials and all the different possible solutions that can be found on the net (I even installed a Microsoft patch which didn’t change anything) and write down straight what solved the problem:

  1. Make sure the „WebClient“ service is running! (Type „services.msc“ into the search box in the start menu and hit enter.  Scroll down the WebClient and check.)
  2. Use „\\yourserver@SSL\DavWWWRoot\yourshare“ as the server address in the Folder field of the Map Network Drive dialog box. Do not forget the DavWWWRoot or the @SSL.  

Find overlapping polygons with Python

Yesterday I was confronted with a seemingly simple problem: how can one find out if the rectangles or, more general, polygons on a surface are overlapping or not? Surprisingly, because they have an amazing collection of tools, the matplotlib library used in this context to actually draw the rectangles, doesn’t seem to have this kind of functionality. Of course there are loads of examples on the web for 2D collision detection, but I couldn’t find one written in Python. But nevertheless, I found lecture notes on Robert Pless’s website, which taught me the quadrant method to check if one point lies inside a polygon. Then it is only a small step to find if polygons are intersecting.

After writing a Python module providing the functionality, it naturally turned out to be rather slow on big numbers of polygons to be checked. So I continued to write a function which checks which polygons in a given set are overlapping or touching. To use the resources on my machine efficiently, I made two versions of this later function: one for conservative, serial processing and a second which uses Parallel Python to distribute the workload among the CPUs found in the system.

If someone else needs this kind of functionaltiy as well or simply is interested in how I did it, here is the interesting part. The whole file with unit tests and documentation can be downloaded as well: polygons_overlapping.py

import pylab

class PolygonsTouching( Exception ):
    """ This exception is triggered when two polygons touch at one point.

    This is for internal use only and will be caught before returning.

    """
    def __init__( self, x=0, y=0 ):
        self.x, self.y = x, y
    def __str__( self ):
        return 'The tested polygons at least touch each other at (%f,%f)'\
               % ( self.x, self.y )
    def shift( self, dx, dy ):
        self.x += dx
        self.y += dy

def pair_overlapping( polygon1, polygon2, digits = None ):
    """ Find out if polygons are overlapping or touching.

    The function makes use of the quadrant method to find out if a point is
    inside a given polygon.

    polygon1, polygon2 -- Two arrays of [x,y] pairs where the last and the
        first pair is the same, because the polygon has to be closed.
    digits -- The number of digits relevant for the decision between
        separate and touching or touching and overlapping

    Returns 0 if the given polygons are neither overlapping nor touching,
    returns 1 if they are not overlapping, but touching and
    returns 2 if they are overlapping

    """

    def calc_walk_summand( r1, r2, digits = None ):
        """ Calculates the summand along one edge depending on axis crossings.

        Follows the edge between two points and checks if one or both axes are
        being crossed. If They are crossed in clockwise sense, it returns +1
        otherwise -1. Going through the origin raises the PolygonsTouching
        exception.

        Returns one of -2, -1, 0, +1, +2 or raises PolygonsTouching

        """
        x, y = 0, 1 # indices for better readability
        summand = 0 # the return value
        tx, ty = None, None # on division by zero, set parameters to None
        if r1[x] != r2[x]:
            ty = r1[x] / ( r1[x] - r2[x] ) # where it crosses the y axis
        if r1[y] != r2[y]:
            tx = r1[y] / ( r1[y] - r2[y] ) # where it crosses the x axis
        if tx == None: tx = ty
        if ty == None: ty = tx
        rsign = pylab.sign
        if digits != None:
            rsign = lambda x: pylab.sign( round( x, digits ) )
        sign_x = rsign( r1[x] + tx * ( r2[x] - r1[x] ) )
        sign_y = rsign( r1[y] + ty * ( r2[y] - r1[y] ) )
        if ( tx >= 0 ) and ( tx < 1 ):
            if ( sign_x == 0 ) and ( sign_y == 0 ):
                raise PolygonsTouching()
            summand += sign_x * pylab.sign( r2[y] - r1[y] )
        if ( ty >= 0 ) and ( ty < 1 ):
            if ( sign_x == 0 ) and ( sign_y == 0 ):
                raise PolygonsTouching()
            summand += sign_y * pylab.sign( r1[x] - r2[x] )
        return summand

    def current_and_next( iterable ):
        """ Returns an iterator for each element and its following element.

        """
        iterator = iter( iterable )
        item = iterator.next()
        for next in iterator:
            yield ( item, next )
            item = next

    def point_in_polygon( xy, xyarray, digits = None ):
        """ Checks if a point lies inside a polygon using the quadrant method.

        This moves the given point to the origin and shifts the polygon
        accordingly. Then for each edge of the polygon, calc_walk_summand is
        called. If the sum of all returned values from these calls is +4 or -4,
        the point lies indeed inside the polygon. Otherwise, if a
        PolygonsTouching exception has been caught, the point lies on ond of
        the edges of the polygon.

        Returns the number of nodes of the polygon, if the point lies inside,
        otherwise 1 if the point lies on the polygon and if not, 0.

        """
        moved = xyarray - xy # move currently checked point to the origin (0,0)
        touching = False # this is used only if no overlap is found
        walk_sum = 0
        for cnxy in current_and_next( moved ):
            try:
                walk_sum += calc_walk_summand( cnxy[0], cnxy[1], digits )
            except PolygonsTouching, (e):
                e.shift( *xy )
                touching = True
        if ( abs( walk_sum ) == 4 ):
            return len( xyarray )
        elif touching:
            return 1
        else:
            return 0

    def polygons_overlapping( p1, p2, digits = None ):
        """ Checks if one of the nodes of p1 lies inside p2.

        This repeatedly calls point_in_polygon for each point of polygon p1
        and immediately returns if it is the case, because then the polygons
        are obviously overlapping.

        Returns 2 for overlapping polygons, 1 for touching polygons and 0
        otherwise.

        """
        degree_of_contact = 0
        xyarrays = [ p1, p2 ]
        for xy in xyarrays[0]:
            degree_of_contact += point_in_polygon( xy, xyarrays[1], digits )
            if degree_of_contact >= len( xyarrays[1] ):
                return 2
        if degree_of_contact > 0:
            return 1
        else:
            return 0

    way1 = polygons_overlapping( polygon1, polygon2, digits )
    way2 = 0
    if way1 < 2: # Only if the polygons are not already found to be overlapping
        way2 = polygons_overlapping( polygon2, polygon1, digits )
    return max( way1, way2 )

def collection_overlapping_serial( polygons, digits = None ):
    """ Similar to the collection_overlapping function, but forces serial
    processing.

    """
    result = []
    pickle_polygons = [p.get_xy() for p in polygons]
    for i in xrange( len( polygons ) ):
        for j in xrange( i+1, len( polygons ) ):
            result.append( ( i, j, \
                pair_overlapping( pickle_polygons[i], pickle_polygons[j], \
                                  digits ) ) )
    return result

def __cop_bigger_job( polygons, index, digits = None ):
    """ This is a helper to efficiently distribute workload among processors.

    """
    result = []
    for j in xrange( index + 1, len( polygons ) ):
        result.append( ( index, j, \
            pair_overlapping( polygons[index], polygons[j], digits ) ) )
    return result

def collection_overlapping_parallel( polygons, digits = None, \
        ncpus = 'autodetect' ):
    """ Like collection_overlapping, but forces parallel processing.

    This function crashes if Parallel Python is not found on the system.

    """
    import pp
    ppservers = ()
    job_server = pp.Server( ncpus, ppservers=ppservers )
    pickle_polygons = [p.get_xy() for p in polygons]
    jobs = []
    for i in xrange( len( polygons ) ):
        job = job_server.submit( __cop_bigger_job, \
                                 ( pickle_polygons, i, digits, ), \
                                 ( pair_overlapping, PolygonsTouching, ), \
                                 ( "pylab", ) )
        jobs.append( job )
    result = []
    for job in jobs:
        result += job()
    #job_server.print_stats()
    return result

def collection_overlapping( polygons, digits = None ):
    """ Look for pair-wise overlaps in a given list of polygons.

    The function makes use of the quadrant method to find out if a point is
    inside a given polygon. It invokes the pair_overlapping function for each
    combination and produces and array of index pairs of these combinations
    together with the overlap number of that pair. The overlap number is 0 for
    no overlap, 1 for touching and 2 for overlapping polygons.

    This function automatically selects between a serial and a parallel
    implementation of the search depending on whether Parallel Python is
    installed and can be imported or not.

    polygons -- A list of arrays of [x,y] pairs where the last and the first
        pair of each array in the list is the same, because the polygons have
        to be closed.
    digits -- The number of digits relevant for the decision between
        separate and touching or touching and overlapping polygons.

    Returns a list of 3-tuples

    """
    try:
        import pp # try if parallel python is installed
    except ImportError:
        return collection_overlapping_serial( polygons, digits )
    else:
        return collection_overlapping_parallel( polygons, digits )