Vorgeschlagener Eintrag

Willkommen auf meinem Blog!

Hier veröffentliche ich unregelmäßig Artikel über Dinge, mit denen ich mich beschäftige, oder die ich so nützlich finde, dass ich sie später nachschlagen will.

Neuen Besuchern möchte ich eine handvoll Beiträge empfehlen, anstatt chronologisch herunterzuscrollen:

Neuste Einträge

Heimkinoautomatisierung

Ich habe seit langem einen Beamer statt eines Fernsehers, was einige Vorteile mit sich bringt: ein sehr großes Bild, kein im Weg stehender Fernseher und die perfekte Motivation Hausautomatisierung in Angriff zu nehmen. Schließlich ist der Ablauf, bevor ein Film starten kann, durchaus aufwendig:

  1. Die Jalousien werden geschlossen.
  2. Die Leinwand fährt herunter.
  3. Der AV-Receiver wird angeschaltet.
  4. Der Beamer startet.

Tatsächlich hatte ich vor Jahren einen selbstgeschriebenen Python-Server auf einem Raspberry Pi aufgesetzt, der diese Steuerung übernommen hat. Aber vor kurzem habe ich ihn ersetzt durch die Anbindung von einem ESP 8266 mittels ESP Home an Home Assistant. In meinem Setup kommt von Infrarot (IR) Fernbedienung über 433 MHz Funk (RF) und Transistoren, die über Fernbedienungskontakte gelötet sind, bis zu einer seriellen RS232 Schnittstelle alles vor. Es sollte also für jeden Leser etwas dabei sein.

Die Jalousien

Meine Jalousien wurden ursprünglich per Hand mit einem Gurt geöffnet und geschlossen. Der einfachste Weg solche Rollläden weniger manuell zu machen, sind nachrüstbare Gurtwickler, die die Muskelkraft durch einen Servomotor ersetzen. Ich habe mir einen relativ günstigen elektrischen Gurtwickler mit einer 433 MHz Fernbedienung gekauft. Der Plan war eigentlich mit einem 433 MHz Receiver die Signale aufzuzeichnen und danach mit einem Sender wieder zu schicken.

Blöderweise hat sich (unter Verwendung von Audacity als Offline-Oszilloskop) herausgestellt, dass sich das Signal bei jedem Knopfdruck ändert — anscheinend nutzen meine Gurtwickler ein Protokoll mit Schlüssel, was beispielsweise für sicherheitsrelevante Anwendungen wie Garagentore verwendet wird.

Die einfache Lösung dafür ist, die Fernbedienung auseinander zu bauen und die Taster, die normalerweise per Hand ausgelöst werden, mit Transistoren zu überbrücken, die dann über GPIO Pins ausgelöst werden können.

Das ist zwar die Fernbedienung von der Leinwand, aber das Prinzip ist das gleiche und ich habe es versäumt ein Foto von der Jalousien-Fernbedienung zu machen

Und die Konfiguration in ESP Home ist selbsterklärend.

output:
  - platform: gpio
    id: blinds_up_pin
    pin: D7

button:
  - platform: output
    id: blinds_up
    name: Jalusinen hoch
    icon: "mdi:roller-shade"
    output: blinds_up_pin
    duration: 300ms
# skipped blinds down

Die Leinwand

Motorisierte Leinwände haben oft einen Eingang für einen 3,5 mm Klinkenstecker, den man direkt mit dem Beamer verbinden kann. Leider nicht die Leinwand, die ich habe. Aber halb so schlimm, denn sie hat eine Funkfernbedienung und ich habe ja noch die 433 MHz Hardware, die für die Jalousien gedacht waren. Und tatsächlich nutzt meine Leinwand ein simples Protokoll — aber auf 315 Mhz.

Sobald wir also einen 315 MHz Transmitter und Receiver haben, können wir die Codes aufzeichnen und die ESP Home Konfiguration anpassen. Dafür definieren wir einen remote_transmitter für den passenden GPIO Pin und einen switch, der den Code für “herunter fahren” sendet, die passende Zeit wartet und dann den Code für “stopp” sendet. Eine Stolperfalle ist, dass der Code mittels repeat mehrmals gesendet werden muss.

remote_receiver:
  - id: RF315_Recv
    pin:
      number: D5
      inverted: yes
      mode: INPUT_PULLUP
    dump: all

remote_transmitter:
  - id: RF315
    pin: D1
    carrier_duty_percent: 100%

switch:
  - platform: template
    name: Screen
    icon: "mdi:projector-screen"
    optimistic: true
    turn_on_action:
      - remote_transmitter.transmit_rc_switch_raw:
          transmitter_id: RF315
          code: '000110110111100111000100'
          protocol: 1
          repeat:
            times: 10
            wait_time: 0s
      - delay: 39.0s
      - remote_transmitter.transmit_rc_switch_raw:
          transmitter_id: RF315
          code: '000110110111100111001000'
          protocol: 1
          repeat:
            times: 10
            wait_time: 0s
    # turn_off_action skipped

Der AV-Receiver

Dies ist die erste Komponente, die nach Plan läuft: Der AV-Receiver hat eine IR Fernbedienung und der Hersteller veröffentlicht die Codes sogar selbst, sodass ich mir das Aufzeichnen sparen kann. Falls man diesen Luxus nicht that, kann man an den ESP einen IR Receiver wie einen TSOP 4838 anschließen und mit dem remote_receiver auswerten.

Um die Signale zu senden, reicht eine Infrarotdiode, die ich über einen Transistor schalte.

Infrarot Sender

Für ESP Home müssen wir einen weiteren remote_transmitter definieren. Damit die Codes über die IR Diode und nicht über den RF Sender verschickt werden, müssen wir dem Transmitter eine Id zuweisen und diese später mit transmitter_id referenzieren.

remote_transmitter:
  - id: IR
    pin: D2
    carrier_duty_percent: 50%

button:
  - platform: template
    id: av_on
    name: AV on
    icon: "mdi:audio-video"
    on_press:
      - remote_transmitter.transmit_pioneer:
          transmitter_id: IR
          rc_code_1: 0xA51A
          repeat:
            times: 2
# skipped other buttons

Der Beamer

Den Beamer könnte man natürlich auch per IR steuern, aber mein Modell, der BenQ W1070, hat eine RS232 Schnittstelle, die nicht nur etwas zuverlässiger als die Infrarotschnittstelle ist, sondern es auch erlaubt den aktuellen Zustand auszulesen. Dazu können wir bspw. einen MAX3232 an die UART Pins anschließen und die Beispielkonfiguration für den custom text_sensor aus der ESP Home Dokumentation kopieren.

logger:
  # disable logging over uart
  baud_rate: 0

uart:
  id: uart_bus
  tx_pin: 1
  rx_pin: 3
  # choose same value set in the projector settings
  baud_rate: 9600

text_sensor:
  # this needs the .h file from https://esphome.io/cookbook/uart_text_sensor.html
  - platform: custom
    lambda: |-
      auto my_custom_sensor = new UartReadLineSensor(id(uart_bus));
      App.register_component(my_custom_sensor);
      return {my_custom_sensor};
    text_sensors:
      id: "uart_readline"

switch:
  - platform: template
    name: "Projector Power"
    icon: "mdi:projector"
    lambda: |-
      if (id(uart_readline).state == "*POW=ON#") {
        return true;
      } else if(id(uart_readline).state == "*POW=OFF#") {
        return false;
      } else {
        return {};
      }
    turn_on_action:
      - uart.write: "\r*pow=on#\r"
    turn_off_action:
      - uart.write: "\r*pow=off#\r"

Fazit

Da dies doch eine ganze Menge Komponenten sind, die ich per Jumper-Kabel an den ESP geschlossen habe, ist noch ein Gehäuse nötig. Dazu nutze ich die beste Alternative zu einem 3D-Drucker: Lego!

Alle Komponenten mittels Lego an der Beamerhalterung befestigt

Die Aufhängung des Beamers bietet dabei den optimalen Ort für eine provisorische Befestigung, die nahe am RS232-Eingang des Beamers ist und einen guten Blick auf den IR-Empfänger des AV-Receivers hat.

Die gesamte EPS-Home-Konfigurationsdatei steht auch als GitHub Gist bereit.

Das ganze Setup wird abgerundet von einem selbstgebauten Schalter (mit Cherry Blue Switches), um den Kinomodus zu starten und zu beenden, sowie Home-Assistant-Automatisierungen, die das Licht kontrollieren: Licht aus wenn der Film startet, Licht gedimmt, wenn er pausiert.

git subtree

Wir alle kennen die Situation: Eine neue Idee, mit der wir unser bestehendes Projekt mit dem Namen alt erweitern, sodass wir sogleich im zugehörigen Repository ein Unterverzeichnis neueIdee anlegen. Die Idee stellt sich dann als so gut heraus, dass sie auch außerhalb des Projektes alt nützlich wäre. Es wäre also sehr sinnvoll ein neues Repository neu anzulegen, das nur den Inhalt des Unterverzeichnisses neueIdee enthalten soll. Tatsächlich scheint dieses Problem wohl so oft vorzukommen, dass es seit 2012 ein extra git Subcommand für diesen Zweck (und etwas kompliziertere Fälle) gibt: git subtree

Neues Repository aus einem Unterverzeichnis

alt/
├─ neueIdee/
│  ├─ lib.rs
├─ main.rs

Wir wechseln also in das Repository alt führen dort folgendes Kommando aus:

git subtree split --prefix=neueIdee/ --branch=nurNeueIdeeBranch

Dies erzeugt in diesem Repository zunächst einen neuen Branch nurNeueIdeeBranch, der nur den Inhalt von neueIdee hat — also ein anderes Wurzelverzeichnis. Dieser Branch enthält also eine neu geschriebene History, die nur aus Commits besteht, die (auch) Einfluss auf Dateien unterhalb von neueIdee hatten.

Nun können wir unser neues Repository neu anlegen und den soeben erzeugten Branch pullen.

cd .. ; mkdir neu ; cd neu
git init
git pull ../alt nurNeueIdeeBranch

Und schon haben wir ein neues Repository, das nur den gewünschten Inhalt hat.

alt/
├─ main.rs
neu/
├─ lib.rs

Möglicherweise wollen wir noch einen Commit im alten Repository tätigen, der das neueIdee Unterverzeichnis löscht. Möglicherweise müssen wir im neuen Repository noch Änderungen am Infrastrukturcode vornehmen.

Verschieben eines Unterverzeichnisses in ein bestehendes Repository

Womöglich fällt uns aber auch auf, dass der Code besser in ein anderes Repository statt eines Neuen passt? Vielleicht weil wir gerade dabei sind unseren Code in einem Monorepo zu sammeln? Auch kein Problem!

alt/
├─ neueIdee/
│  ├─ lib.rs
├─ main.rs
monorepo/
├─ project1/
├─ project2/

Wir haben oben bereits den nurNeueIdeeBranch erstellt, den wir nun in das Unterverzeichnis guteIdeedes Repositorys monorepo einfügen wollen. Auch hier hilft uns wieder git subtree weiter:

cd monorepo
git branch mitGuterIdeeBranch
git checkout mitGuterIdeeBranch
git subtree add --prefix=guteIdee/ ../alt nurNeueIdeeBranch

Sobald wir uns in dem neuen Branch mitGuterIdeeBranch überzeugt haben, dass alles zu unserer Zufriedenheit geklappt hat und wir möglicherweise noch Infrastrukturcode angepasst haben, können wir den Branch nach main mergen und sind fertig.

alt/
├─ neueIdee/
│  ├─ lib.rs
├─ main.rs
monorepo/
├─ project1/
├─ project2/
├─ guteIdee/
│  ├─ lib.rs

Convex hulls of random walks in higher dimensions: A large deviation study

Die Frage wie groß das Revier eines Tieres ist, ist in konkreten Fällen für Biologen interessant und dank GPS-Sendern kann man es heutzutage sogar empirisch untersuchen. Aus der Punktwolke der besuchten Orte kann man eine Fläche abschätzen — im einfachsten Fall indem man die konvexe Hülle um alle besuchten Orte zeichnet.

Als Physiker sind mir echte Tiere zu kompliziert, sodass ich stattdessen annehme, dass sie punktförmig sind und ihre Bewegung ein Random Walk in einer isotropen Umgebung ist. Also springen meine idealisierten Tiere unabhängig von ihren bisherigen Handlungen zu ihrem nächsten Aufenthaltsort — der Abstand vom aktuellen Punkt ist dabei in jeder Dimension unabhängig und normalverteilt.

In jeder Dimension? Ja, genau! Wir wollen schließlich auch das Revierverhalten von vierdimensionalen Space Whales untersuchen.

Möbius Dick, Futurama Möbius Dick, Futurama (2011)

Spaß beiseite, in dieser Veröffentlichung geht es natürlich eher um fundamentale Eigenschaften von Random Walks — einer der einfachsten und deshalb am besten untersuchten Markow-Prozesse. Und zwar im Hinblick auf Large Deviations, die extrem unwahrscheinlichen Ereignisse, die weit jenseits der Möglichkeiten von konventionellen Sampling-Methoden liegen. Details hierzu sind am besten direkt im Artikel oder mit einer Menge Hintergrundinformationen und ausführlicher als für ein Blog angemessen in dem entsprechenden Kapitel und Anhang meiner Dissertation nachzulesen. Insbesondere ist dort auch beschrieben wie die geometrischen Unterprobleme effizient gelöst werden können, auf die wir im Verlauf dieses Blogposts stoßen werden.

Das Problem eine konvexe Hülle zu finden ist einerseits einfach zu begreifen, schön geometrisch und sehr gut untersucht. Dadurch sind überraschend viele Algorithmen bekannt, die unterschiedliche Vor- und Nachteile haben.

Im Folgenden möchte ich deshalb ein paar Methoden vorstellen, wie man effizient die konvexe Hülle einer Punktmenge bestimmen kann, und dies mit animierten gifs von Punkten und Strichen visualisieren. Der Code zur Erstellung der Visualisierungen ist übrigens in Rust geschrieben und auf GitHub zu finden.

Andrew’s Monotone Chain

In zwei Dimensionen kann man ausnutzen, dass die konvexe Hülle ein Polygon ist, das man durch die Reihenfolge der Eckpunkte definieren kann. Die grundlegende Idee ist also die Punkte im Uhrzeigersinn zu sortieren, in dieser Reihenfolge, mit dem Punkt ganz links startend, alle zu einem Polygon hinzuzufügen und dabei darauf zu achten, dass die drei neusten Punkte des Polygons ein negativ orientiertes Dreieck bilden, also dass sie im “Uhrzeigersinn drehen”. Wenn das nicht der Fall ist, wird der mittlere Punkt entfernt.

Sechs Schritte von Andrew's Monotone Chain -- oder Graham Scan

Dies ist übrigens die ursprüngliche Variante, der Graham Scan. Andrew verbesserte diesen Algorithmus dadurch, dass nicht im Uhrzeigersinn sortiert werden muss, sondern man lexikographisch nach horizontaler Koordinate (bei Gleichstand entscheidet die vertikale Koordinate) sortiert. Dann bildet dieser Algorithmus die obere Hälfte der Hülle und wenn man ihn rückwärts auf die sortierten Punkte anwendet, die untere Hälfte.

Andrew's Monotone Chain

Die Komplexität für \(n\) Punkte ist somit \(\mathcal{O}(n \ln n)\) limitiert durch das Sortieren.

Jarvis March: Gift Wrapping

Ein Geschenk einzupacken ist ein relativ intuitiver Prozess: Wir bewegen das Papier so lange herunter, bis wir auf einen Punkt des Geschenkes treffen, wo es hängen bleibt Dann wickeln wir weiter, bis wir auf den nächsten Punkt stoßen. Dabei streben wir an die konvexe Hülle zu finden, denn sie ist das Optimum möglichst wenig Papier zu verbrauchen während wir die Punktwolke einhüllen, die wir verschenken wollen. Und offenbar klappt das auch in drei Dimensionen!

In einem Computer ist es allerdings einfacher das Geschenkpapier von innen aus der Punktwolke heraus nach außen zu falten. Für jede Facette testen wir also jeden der \(n\) Punkte in der Punktwolke darauf, ob er links von unserem Stück Geschenkpapier liegt. Wenn ja, falten wir das Papier weiter. Sobald wir alle \(n\) Punkte ausprobiert haben, wissen wir, dass das Geschenkpapier an der richtigen Stelle liegt, sodass anfangen können die nächste Facette mit dem Geschenkpapier zu bilden indem wir von innen alle Punkte durchtesten.

Jarvis March: Gift Wrapping

Interessanterweise müssen wir also für jeden der \(h\) Punkte, die zur Hülle gehören \(\mathcal{O}(n)\) Punkte prüfen, sodass die Komplexität abhängig ist vom Ergebnis: \(\mathcal{O}(n h)\)

Chan’s Algorithm

Wir haben also einen \(\mathcal{O}(n \ln n)\) und einen \(\mathcal{O}(n h)\) Algorithmus kennen gelernt, aber können wir noch besser werden? Ja! \(\mathcal{O}(n \ln h)\) ist die theoretische untere Komplexitätsgrenze für 2D konvexe Hüllen. Beispielsweise Chans Algorithmus erreicht diese Komplexität mit einem trickreichen zweistufigen Prozess.

Zuerst teilt man die Punktwolke in zufällige Untermengen mit jeweils etwa \(m\) Punkten ein. Für jede berechnet man die konvexe Hülle, bspw. mit Andrews Algorithmus. Dann benutzt man Jarvis March, um die Hülle zu konstruieren, dabei muss man allerdings nicht mehr alle Punkte durchprobieren, sondern nur noch die Tangenten, die in der Animation mit grünen Strichen gekennzeichnet sind. Die Tangenten kann man für jede der \(k = \lceil \frac{n}{m} \rceil\) Sub-Hüllen effizient in \(\mathcal{O}(m)\) bestimmen. Dazu benutzt man einem Algorithmus, der an eine Binärsuche erinnert. Zusammen hat dies also eine Komplexität von \(\mathcal{O}((n+kh) \ln m)\).

Aber ich hatte \(\mathcal{O}(n \ln h)\) versprochen. Nun, um das zu erreichen, müssen wir einfach nur \(m \approx h\) wählen. Aber wie kommen wir an \(h\) bevor wir die Hülle berechnet haben? Der Trick ist, mit einem niedrigen \(m\) zu starten, dann nur \(m\) Schritte des Jarvis-Teils des Algorithmus durchzuführen und wenn die Hülle dann noch nicht fertig ist \(m\) zu erhöhen und es wieder von vorne zu beginnen. Damit dieser iterative Teil des Algorithmus nicht unsere Komplexität erhöht, muss \(m\) schnell genug wachsen, was in der Regel durch Quadrieren des alten Werten erreicht wird.

Chan's Algorithm

QuickHull

Zuletzt möchte ich hier noch QuickHull vorstellen, weil dieser Algorithmus meiner Meinung nach einen sehr hübschen rekursiven divide and conquer Ansatz verfolgt — ein bisschen wie QuickSort. In zwei Dimensionen starten wir mit dem Punkt ganz links \(A\) und ganz rechts \(B\). Dann finden wir den Punkt \(C\) der am weitesten entfernt ist von der Strecke \(\overline{AB}\) und links von der Strecke ist. Diesen Schritt wiederholen wir rekursiv auf den Strecken \(\overline{AC}\) und \(\overline{CB}\) (und \(\overline{BA}\) für die untere Hälfte.)

QuickHull

Mehr Dimensionen

Aber ich hatte Space Whales versprochen, also können wir uns nicht mit 2D zufrieden geben! Tatsächlich müssen wir schon beim Verallgemeinern auf 3D aufpassen. Schließlich konnten wir für 2D die konvexe Hülle als Sequenz von Punkten repräsentieren. Für höhere Dimensionen müssen wir sie allerdings als Menge von Facetten repräsentieren. Glücklicherweise tauchen für noch höhere Dimensionen dann keine weiteren Schwierigkeiten mehr auf — abgesehen von der Grundsätzlichen Schwierigkeit, dass höherdimensionale Gebilde deutlich größere Oberflächen haben und somit die konvexe Hülle aus deutlich mehr Facetten besteht, sodass die untere Schranke für die Komplexität für Dimension \(d\) durch \(\mathcal{O}(n^{\lfloor d / 2 \rfloor})\) gegeben ist.

Bevor ich hier QuickHull für \(d=3\) beschreibe, möchte ich darauf hinweisen, dass es die qhull Implementierung gibt, die sich bspw. auch um die subtilen numerischen Fehler kümmert, die sich bei sehr spitzen Winkeln einschleichen können.

Grundsätzlich bleibt das Vorgehen gleich: Wir starten mit einem \(d\)-dimensionalen Simplex, also für \(d=3\) mit einem Tetraeder, dessen Eckpunkte zur konvexen Hülle gehören. Dann führen wir für jede Facette den rekursiven Schritt durch: Finde den Punkt, der am weitesten vor der Facette (also außerhalb des Tetraeders) ist. Diesen Punkt nennt man Eye-Point. Denn es reicht jetzt im Gegensatz zum 2D Fall nicht mehr einfach neue Facetten aus den Rändern und dem neuen Punkt zu bilden. Stattdessen müssen wir alle Facetten, deren Vorderseite (also Außenseite) wir vom Eye-Point aus sehen können entfernen und neue Facetten mit dem Horizont und dem Eye-Point bilden. In der Animation unten sind der Eye-Point sowie die Facetten, die er sieht, rot dargestellt. Der Horizont ist mit schwarzen Strichen gekennzeichnet.

Wird dieser Schritt rekursiv auf alle neu hinzugefügten Facetten angewendet, resultiert die konvexe Hülle. Und genauso, wenn auch deutlich schwieriger darstellbar, funktioniert es auch für alle höheren Dimensionen.

QuickHull

Eine wichtige Anwendung für 3D konvexe Hüllen ist übrigens die Delaunay-Triangulation einer planaren Punktmenge. Die wiederum kann für eine effiziente Berechnung des Relative-Neighborhood-Graphs aus diesem Post genutzt werden.