Kreisschnitte und Kreisvereinigungen

Inspiration

Meistens gibt es in der Twitter-Timeline von Dr. Immy Smith a.k.a. `Moths in a human suit` Zeichnungen aus der Entomologie-Ecke zu sehen. Als sie neulich aber einen Tweet zum UK-Lammy-Review (2017) veröffentlichten, war auch dieser mit eigenen, spannenden Zeichnungen illustriert. Die Grundidee ist laut Smith, die Daten aus dem Review irgendwie zu visualisieren: jedes Kapitel hatten sie als Kugeln dargestellt und beziehende Kapitel als umgebende Kugeln darum. Kernaussagen der Kapitel liegen als Morse-Code in konzentrischen Kreise aufgetragen um die Kapitelkreise. Was mir besonders gefiel: die Kreise durchdringen sich zum Teil, aber die entstandenen Pfade waren geschlossen und durchdringungsfrei.

Tweet von Dr Immy Smith

 

Ziel

Auf Grundlage dieser Zeichnung wollte ich nun eine ähnliche Grafikspielerei nachbauen, allerdings nicht mit dem Zeichenstift, sondern mit TypeScript.

Es sollte eine Routine entstehen: eine, die Flächen – aus mehreren sich überschneidenden Kreisen bestehend – füllen und bei Bedarf eine Umrahmung um die gefüllte Fläche zeichnen könnte. Auf die Umrahmung könnte ich dann irgendwann irgendwelche Codes zeichnen. Desweiteren sollte die Grafik als SVG exportierbar sein, also mussten die Formen unbedingt als Vektor-Pfade beschrieben werden können.

Eine schnelle Recherche ergab, dass das Problem zweier sich schneidener Kreise nicht schwierig ist. Zwar hat meine übliche erste Anlaufstelle noch keine Implementierungen des Problems in ihr Archiv übernommen, aber Wolfram-Mathworld hatte schon längst alle wichtige Theorie zusammengefasst.

Theorie

Für zwei nicht konzentrische Kreise findet sich immer die sogenannte Potenzlinie (Chordale, »radical line« für die englischsprachige Suche). Wenn sich beide Kreise schneiden, dann liegt die Potenzline exakt auf den beiden Schnittpunkten der Kreise. Und hier kommt das erste zu lösende Problem: die Zeichenroutinen von Javascript erwarten für die Darstellung von Kreisbögen zusätzlich zum Kreismittelpunkt außerdem einen Start- und einen Endwinkel. Aber mithilfe der Arkustangens-Funktion(en) lassen sich die Winkel dieser vier Geraden berechnen:

  • (C0,a) für α0
  • (C0,b) für α1
  • (C1,a) für β0
  • (C1,b) für β1

α := α1-α0
β := β1-β0

Einen interaktiven Demo-Test für zwei Kreise und deren Potenzlinien gibt es hier. Einfach die Punkte hin und her schieben.

Potenzlinie zweier sich überschneidender Kreise
Potenzlinie und Innenwinkel

Schnitte mit n > 2

Herausfordernder wird dies bei Überschneidungen mit mehr als zwei Kreisen: n Kreise können nach Gauss im Extremfall Σ(n-1)=(n-1)*n/2 Kreisschnitte ergeben (jeder Kreis schneidet alle anderen). Folglich kann jeder Kreis in (n-1) Sektoren zefallen, und diese Sektoren müssen nicht zwangsläufig disjunkt sein.

Die eigentliche Aufgabe besteht also darin, eine Funktion zu programmieren, die aus einem Kreis nach und nach Sektoren herausschneiden und die Ergebnisse irgndwie in einer Datenstruktur abbilden kann.

Datenstruktur für ringförmige Intervalle

Das Ziel ist, am Ende die Kreissektionen außerhalb der gemeinsamen Schnittmengen darzustellen. Denn gezeichnet werden sollen nicht die Sektoren innerhalb der Kreisschnitte, sondern die Außengrenzen, die in keinem anderen Kreis liegen. Als Grundidee dient ein ringförmiges Intervall von 0 bis 2*π (in Radianten; entsprechend 0° bis 360° in Grad), das nach und nach mit weiteren Intervallen geschnitten wird und so in eine Reihe von disjunkten Teilintervallen zerfällt; jedes Teilintervall repräsentiert einen Sektor (Start- und Endwinkel) des ursprünglichen Kreises. Eine solche Sequenz von Teilintervallen wird für jeden gegebenen Kreis mitgeführt..

Die Implementierung dazu ist übersichtlich, es müssen aber die Extremfälle an den Rändern berücksichtige werden. Zum Beispiel ist [336°,50°] ein gültiges Teilintervall, das über das geschlossene Ende des Ringes bei 360° hinausläuft.

Mehrfache Kreisschnitte mit n > 2
Ringförmige Intervallstruktur

 

Verbundene Pfade und SVG-Arcs

Eine weitere Herausforderung ist das Erkennen und Finden zusammenhängender Pfadsegmente, sobald die Kreise in dusjunkte Sektionen zerlegt wurden. Meine Implementierung nutzt dafür einfach einen isCloseTo(Startpunkt,Endpunkt)-Test mit kleinem Epsilon:

  1. wähle ein zufälliges Pfadsegment S und markiere es als besucht
  2. betrachte den Endpunkt (x,y) (einer der beiden Punkte aus der Potenzlinie)
  3. finde aus der Menge der noch unbesuchten Segmente D jenes, dessen Startpunkt bei (x,y) liegt
    (hierfür Epsilon-Umgebung verwenden)
  4. markiere D als besucht
  5. fahre solange fort, bis der Endpunkt von D beim Startunkt von S liegt
    (hier wurde ein vollständiger geschlossener und zusammenhängender Pfad gefunden)
  6. markiere S als besucht
  7. wiederhole Punkt 1., wenn noch unbesuchte Pfadsegmente vorhanden sin

Die Implementierung sieht so aus.

 

Für den SVG-Export muss nun die Folge von Kreisbögen der Form

   arc(Mittelpunkt, Startwinkel, Endwinkel)

in eine Folge von Kreisbögen der Form

   arc(Startpunkt, Radius, ..., Innenbogen_Ja_Nein, ..., Endpunkt)

umgewandelt werden.

Warum diese bizarre Bogendefinition es in den SVG-Standard geschafft hat, offenbart sich auf den zweiten Blick. Zusammengesetzte SVG-Pfade sollen ohne Absetzen zu zeichnen sein. Dazu wird für jedes Pfadsegment (linear, Bézier, Bogen) je ein Start- und ein Endpunkt (x,y) benötigt. Diese liefert bei Kreisbögen genau die Darstellung mit zwei Cordal-Schnittpunkten a und b. Darstellungen mit Start- und Endwinkel hingegen sind hier unbrauchbar.

 

opsb hat auf Stackoverflow beschrieben, wie die Umwandlung von der einen Bogendarstellung in die andere geht und meine Adaption sieht so aus (~￣▽￣)~

 

 

HTML-Canvas

canvas.getContext("2d")
    .arc( centerX, centerY, radius, startAngle, endAngle );

 

SVG-Path-Data

<path d="M startX startY 

    A radiusX radiusY rotation largeArcFlag clockwiseFlag endX endY" />
Arcs mit Canvas oder SVG

Implementierung TypeScript/Javascript

Eine einfache Implementierung in TypeScript habe ich auf Github abgelegt.

In Javascript kann ein gegebenes Array von Kreisen (Mittelnpunkt plus Radius) so zerlegt und die äußeren Pfade berechnet werden:

// Find intersections, radical lines and interval
const innerCircleIndices : Array<number> =
         CircleIntersections.findInnerCircles( circles );

const radicalLineMatrix : Matrix<Line> =
         CircleIntersections.buildRadicalLineMatrix( circles );

const intervalSets : Array<CircularIntervalSet> =
         CircleIntersections.findOuterCircleIntervals( circles, radicalLineMatrix );

// A sequence of paths.
// Each path is a sequence of { circleIndex, intervalIndex }
const pathList : Array<Array<IndexPair>> =
         CircleIntersections.findOuterPartitions( circles, intervalSets );

 

Ergebnis: und so sieht's aus

Live-Demo mit 7 Kreisen

Wie sich zeigte, kann die Theorie einfach sein, die Umsetzung aber schwierig (besonders, wenn viele Randfälle beachtet werden oder ein bestimmtes Ausgabeformaet eingehalten werden soll):

Jetzt kann ich aber Ringpfade überschneidungsfrei als Vektor-Grafik berechnen und exportieren: Grundlage für weiter Spielereien.

Zum Verlgeich zum Anfang: Smiths Morse Code Drawings onRacial inequalities in the UK sehen so aus.

 

Schöne Zeichnungen, ernster Hintergrund

Etwas geht mir während der gesamten Programmierphase nie komplett aus dem Kopf: ich hatte vorher noch nie vom "Lammy Review" gehört oder gelesen und frage mich, ob es in Deutschland einen ähnlichen jährlichen von der Regierung in Auftrag gegebenen oder unterstützten Bericht gibt, der in Zusammenarbeit mit Betroffenenverbänden entsteht. Auffällig und bedauerlich finde ich, dass sich z.B. das Innenministerium mit umfassende Studien zum Thema strukturellem und institutionellem Rassismus schwer zu tun scheint. Eie Suche führte mich lediglich zu den Erhebungen von Statisa und dem Bericht Europäische Kommission gegen Rassismus und Intoleranz von 2019.

Links sind willkommen.

 

Zum Abschluss ein Gedicht

Archimedes

Jaja! Der weise Archimedes
ging stets zu Fuß, ging stets per pedes.
Doch ging er auf besondre Weise:
Er ging hauptsächlich nur im Kreise.

Die Gangart hatte sich nach Wochen
in Syrakus herumgesprochen,
weshalb – es ist gut zu verstehn –
die Menge kam, sich’s anzusehn.
Doch dies gefiel dem Greise nicht!
Er sprach: „Stört meine Kreise nicht!“

Jaja! Der weise Archimedes
ging stets zu Fuß, fuhr nie Mercedes.

– Heinz Erhardt

Nachtrag

17 Januar 2021

Zur Eindämmung der SARS-CoV-2-Epidemie sind derzeit Pläne für Reisebeschränkungen in der Diskussion, die unter anderem auch Berlin betreffen würden. Es soll einen 15km-Reiseradius um Berlin geben. Dieser lässt sich vereinfacht mit Kreispfaden darstellen, was dann so aussieht:

 

 

Ich habe dies live als Demo einprogrammiert.

 

Interesant und auffällig: offenbar gibt es auch in Berlin-Mitte einen Bereich, der mehr als 15km von den Außenrändern entfernt ist.