Gebietsunterteilung berechnen

Die Mittelpunkte liegen alle auf gleichseitigen Dreiecken.
Der Rest ist einfache Geometrie.


Wie sieht Dein Ansatz bisher aus?

Nachtrag:  Was soll das sein: "bei d=r/2"?

Deine Aufgabe hat keine einfache Lösung, weil es x,y Orte gibt, die in 
eine weisse Fläche fallen, also keinem Kreis zugeordnet sind.
Eigentlich hast du Sechsecke.

Planer schrieb:
> d=r/2

Eigentlich steht d für Durchmesser, r für Radius, und die Formel wäre 
andersrum.

Planer schrieb:
> Ausgegeben soll der relative Wert gegenüber dessen Mittelpunkt. Der Wert
> rangiert also wieder zwischen -r und r.

Eine Entfernung zum Mittelpunkt (des nächstgelegenen Kreises) wäre nie 
negativ, also kann es nur die Lage entlang einer Koordinate sein, 
x-Achse ?

Da teilen die Kreismittelpunkte das Feld in Radiussprünge auf, also 
x-Achse mir 0xr, 1xr, 2xr  ...
Bei geradzahligen Abschnitten liegen die Kreise auf einer unteren Linie, 
bei ungradzahligen auf einer oberen Linie. Bestimmt man den davor und 
den dahinter liegenden Mittelpunkt, kann man zu jedem die Entfernung 
(x-xr)^2+(y-yr)^2 berechnen, und die kleinere gewinnt. Dabei entstehen 
aber Sechsecke.

Planer schrieb:

> Um das zu berechnen, bräuchte ich aber erst die
> Mittelpunkte des getroffenen Kreises und die Abfrage
> ist nicht so trivial.

Naja, aber fast.


> Bei Quadraten würde ich einfach eine Integer-Rechnung
> benutzen mit NummerX = (X / D).

Kein schlechter Ansatz. Mal an (X / r) gedacht?


> Das geht bei Kreisen nicht, weil sich die möglichen
> Koordinaten überschneiden.

Sicher.
Das Überschneiden geschieht aber nicht willkürlich,
sondern folgt einer festen Regel.

Tipp 1: Das Verfahren muss nicht einstufig sein -- zwei
        Stufen tun es vielleicht auch.

Tipp 2: Man kann in Stufe 1 eine FEINERE Parkettierung
        verwenden, als man eigentlich braucht, um dann
        in Stufe 2 die Elementarflächen zu den Zielflächen
        zusammenzusetzen.

MaWin schrieb:
> Eigentlich steht d für Durchmesser, r für Radius, und die Formel wäre
> andersrum.

Ja, natürlich anders herum.


> Eine Entfernung zum Mittelpunkt (des nächstgelegenen Kreises) wäre nie
> negativ, also kann es nur die Lage entlang einer Koordinate sein,
> x-Achse ?

X und y achse. Ich rechne von der Mitte einfach gespiegelt wenn 
gefordert. Es reicht, einzuteilen.

Die bisherige Strategie ist, um die Frage zu beantworten, bis zu den 
Stossstellen der Kreise zu rechnen und gleich zeitig in einer zweiten 
Rechnung durch den Durchmesser zu dividieren, was die X-Achse angeht und 
durch Wurzel (0,75) was Y angeht.

Dann gibt es eine Fallunterscheidung.

Zum anderen Punkt: Ob in in einer Zelle im Kreis oder ausserhalb, also 
in den Zwischenräumen bin, kann ich ja leicht bei der Kreisberechnung 
über den Radius testen. Ich muss nur erst einmal wissen, welchen 
Mittelpunkt ich nehmen soll.

Um es mal konkret zu machen: Wenn y z.B. 0,99 ist, könnte ich in der 
unteren Spalte sein, wenn X klein genug ist, aber auch schon in der mit 
dem Kreis darüber, wenn X passt. Irgendwie habe ich einen Knoten im 
Hirn, das einfach als Baum-Ast-Gleichung hinzuuschreiben. Rechnen soll 
übrigens ein PC, der eine Bewässerung sicherstellen soll. Das 
Wasserviech kann angeblich mit einem Roboter fahren, aber nicht überall 
spritzen. Es gibt Parzellen, die man vorprogrammieren kann, wieviel 
Wasser sie kriegen sollen.

Planer schrieb:

> Um es mal konkret zu machen: Wenn y z.B. 0,99 ist,
> könnte ich in der unteren Spalte sein, wenn X klein
> genug ist, aber auch schon in der mit dem Kreis
> darüber, wenn X passt.

Stimmt. Hatte ich nicht bedacht.

Hmm. Meine Idee lässt sich aber retten...


> Irgendwie habe ich einen Knoten im Hirn, das einfach
> als Baum-Ast-Gleichung hinzuuschreiben.

Vorüberlegung:

1. Jeder Kreis hat sechs Berührungspunkte mit seinen
   Nachbarn.

2. Wir betrachten im weiteren nur die Berühungspunkte,
   die jeder Kreis mit den SCHRÄG oben und unten liegenden
   Kreisen hat, das sind vier Stück; diese vier Punkte
   mögen "wesentliche Berühungspunkte" heißen.
   Die zwei Berührungspunkte, die jeder Kreis mit seinem
   linken und rechten Nachbarn hat, vernachlässigen wir.

3. Alle wesentlichen Berührungspunkte liegen auf einem
   Rechteckgitter der Maschenweite dx = 0.5 und dy = 0.866.


Jetzt gilt:

1. Pro Zeile liegt jeweils die Hälfte aller Gitterzellen
   VOLLSTÄNDIG in einem Kreis. Diese Gitterzellen enthalten
   auch den Mittelpunkt des sie umschließenden Kreises.

2. In der anderen Hälfte aller Gitterzellen liegen jeweils
   vier Kreiskappen.

Ob für einen willkürlich gewählten Punkt Fall 1 oder Fall 2
zutrifft, lässt sich durch einfache Koordinatenrechnung
entscheiden.

Bei Fall 1 ist man fertig; wenn Fall 2 zutrifft, sind
zusätzliche Unterscheidungen notwendig, die ich mir noch
nicht überlegt habe.
U.U. ist es am einfachsten, die vier in Frage kommenden
Kreise durchzuprobieren, ob der euklidische Abstand zum
Mittelpunkt kleiner als r ist.

Setze erstmal um jeden Kreis ein beruehrendes Quadrat und ermittle, in 
welchen Quadraten sich der Punkt befindet. Das sind maximal 3 und die 
sind dann die Kandidaten fuer die weitere Einschraenkung.

Nehme nun die X-Werte des Suchpunktes und berechne fuer die Kandidaten 
die beiden Y-Werte an dieser Stelle. Wenn der Punkt im.Kreis liegt, muss 
der Y-Wert zwischen beiden Kreis-Y-Werten liegen (einfacher Vergleich).
Findet sich keiner der Kandidaten, dann liegt der Punkt auf einem 
weissen Fleck.

Also eigentlich ganz einfach :-)

Maxe schrieb:
> Das sind maximal 3
Nachtrag: 2 nicht 3.

hy,
wenns eine mehrstufiges Programms ein darf und keine "Formel" sein muss:
Schritt 1:
Skalieren dass der Radius 1 ist (erste Matrizenmultiplikation)
Schritt 2:
Koordinatensystem so Transformieren, dass die X und Y Achse durch die 
Kreismittelpunkte läuft (Matrizenaddition und Multiplikation)*
Schritt 3:
auf Ganzzahl Runden => Das ist der Mittelpunt der nächsbesten Raute, die 
deinen Kreis umschließt
Schritt 4:
Rücktransformation des Mittelpunktes in dein altes Koordinatensystem:
Schritt 5:
Test, ob Distanz Punkt Mittelpunkt < Radius ist**

sg
* ja auch das ist ein Koordinatensystem, wenn auch kein rechtwinkeliges
** das kannst du auch im schrägen Koordinatensystem prüfen, da gilt aber 
(a²+b²)=c² nicht wirklich

Alle Kreise können einfach in einem neunen Koordinatensystem
eingefangen werden:
sei v1 = (1,0) und v2(c,s) mit c=cos(pi/3), s=sin(pi/3),
dann sind mit d=Durchmesser doch alle Kreise k(i,j) auf
i*v1+j*v2, i,j aus Z? Mit der Matrix M=(v1,v2) und
(u,v) = M^-1*(x,y) ergibt sich (i,j)=round(u/d,v/d) und
(dx,dy)=(x,y)-d*(i,j).

Statt des "schrägen" Koordinatensystems ist natürlich
auch ein orthogonales System möglich, hier sind dann je
eine Zeile ggü der nächsten Zeile nach Oben/nach Unten
verschoben, d.h. man bracht eine Fallunterscheidung.

rechne eionfach den Abstand deiner Koordinate zu allen 
Kreismittelpunken. ist einer kleiner oder gleich r, dann hast du den 
richtigen Kreis. sind zwei =r, dann liegt deine Koordinate auf dem 
Berührungsunkt. Sind alle >r, dann ist deine Koordinate im weißen 
Bereich.
Oder hab ich das Problem irgendwie falsch verstanden?

Yalu X. schrieb:
> Sigi schrieb:
>> Alle Kreise können einfach in einem neunen Koordinatensystem
>> eingefangen werden:
>> sei v1 = (1,0) und v2(c,s) mit c=cos(pi/3), s=sin(pi/3),
>> dann sind mit d=Durchmesser doch alle Kreise k(i,j) auf
>> i*v1+j*v2, i,j aus Z? Mit der Matrix M=(v1,v2) und
>> (u,v) = M^-1*(x,y) ergibt sich (i,j)=round(u/d,v/d) und
>> (dx,dy)=(x,y)-d*(i,j).
>
> So dachte ich auch zuerst, aber leider geht es nicht so einfach. Alle
> Punkte innerhalb des grünen Parallelogramms in kreise2.png würden damit
> dem mittleren Kreis zugeordnet. Es umfasst den mittleren Kreis aber
> nicht vollständig und enthält auch ein paar Abschnitte der benachbarten
> Kreise.

Vielen Dank für den Hinweis, der Fehler findet sich somit
in meinen beiden Vorschlägen.

Mein Ansatz lässt sich aber dank deiner Skizze leicht beheben:
Ist die Koordinate bzgl. meinem schrägen Koordinatensystem zu
weit "über" dem Kreis, dann können nur die beiden Kreise
oberhalb in Frage kommen, für "unter" die beiden Kreise
unterhalb. Je nachdem, ob dx kleiner oder grösser ist, ist es
der jeweils untere oder der obere Kreis.
Insgesamt also eine Transformation, eine Rundung, eine
Restberechnung und 2 Fallunterscheidungen. Geht's noch einfacher?

Jürgen S. schrieb:

> Das Zauberwort heißt Restklassenbetrachtung. [...]

Ich hätte das Raster um (r/2) in X-Richtung verschoben.
Dann verschwinden nämlich die roten Doppellinien.

Noch eine etwas andere Lösung.

Berechne in einer Schleife i = 0...11 diese Größen:

1

sx = i;

2

sy = sqrt(3) * (i mod 2);

3

4

dx = x - sx;

5

dy = y - sy;

6

7

u = round(+by*dx - bx*dy);

8

v = round(-ay*dx + ax*dy);

Darin sind x und y die Koordinaten des fraglichen Punkts, ax = 
-0.25*sqrt(3), ay = -0.25, bx = -0.25*sqrt(3), by = +0.25.

Nun sind in genau einem der zwölf i-Schleifendurchläufe folgende drei 
Bedingungen wahr:

1

(1) u + v = round(0.5*dx)

2

(2) u mod 3 = 0

3

(3) v mod 3 = 0

Darauf testet man also mit "if" und im Trefferfall berechnet man

1

mx = sx - 8/3*sqrt(3)*(u*ax + v*bx)

2

my = sy - 8/3*sqrt(3)*(u*ay + v*by)

(mx, my) ist der Mittelpunkt des Sechsecks in der Wabenparkettierung, in 
welcher der Punkt (x, y) liegt. Wie man als letztes noch feststellen 
kann, ob der Punkt in dem entsprechenden Kreis liegt oder im 
angrenzenden weißen Zwischenraum, ist klar.

Ich bin davon ausgegangen, dass der Koordinatenursprung mit dem 
Mittelpunkt einer der Kreise zusammenfällt. Kreisradius = 1.

Der mathematische Hintergrund dieses Algorithmus, dem man wahrlich nicht 
ansehen kann, warum er funktionieren sollte, sind die sogenannten 
baryzentrischen Koordinaten:
https://de.wikipedia.org/wiki/Baryzentrische_Koordinaten

Das Gitter wird hier durch die Punkte (ax, ay) und (bx, by) und (0, 0) 
aufgespannt. Die Bedingung (1) vereinigt bestimmte Dreieckszellen zu den 
benötigten Sechsecken passender Größe. Dann hat man eine unendlich 
ausgedehnte Sechseckparkettierung, die aber nicht lückenlos ist 
(3/4-Bedeckung, siehe Bild) und noch schlimmer: Nur 1/12 dieser 
Sechsecke liegt passgenau auf einem Kreis. Die Bedingungen (2) und (3) 
selektieren diese "brauchbaren" Sechsecke (zweimal "mod 3" bewirkt eine 
Ausdünnung um den Faktor 1/9, das ergibt zusammen mit den 3/4 dann die 
1/12). Für die gewünschte lückenlose Überdeckung muss man sich also 
zwölf passend gegeneinander verschobene Untergitter definieren; das 
geschieht über sx und sy ("shift-x/y"). In den Variaben u und v sind die 
(nicht-normierten) baryzentrischen Koordinaten des Punktes (x, y) 
gespeichert. Auch die dritte Koordinate "w" wird verwendet; sie steckt 
in "round(0.5·dx)".

Wegen der Schleife ist die Lösung leider nicht besonders effizient, aber 
nach meinen Erkenntnissen lässt sich das (bei diesem Ansatz) nicht 
umgehen.

Mir ist eine weitere Lösung eingefallen, die auf einem ebenso einfachen 
wie effektiven Trick basiert. Warum nur kommt man auf so etwas 
Naheliegendes nicht gleich?

Das Bild lässt die Idee sofort erkennen: Man zerlegt das Gitter in zwei 
Untergitter, von mir "Hauptgitter" und "Nebengitter" genannt. In diesen 
Untergittern überlappen sich die Kreise nicht und das ist der 
entscheidende Vorteil. Wie man im Bild sieht (grau getönt hervorgehoben 
ist die (2, 1)-Hauptgitterzelle) liegt jeder Kreis brav mittig in 
"seiner" Zelle. Dazu sind die Untergitter orthogonal, d. h. man muss 
keine schiefen oder baryzentrischen Koordinaten bemühen.

Der Algorithmus ist klar: Suche zunächst im HG. Falls ohne Erfolg, suche 
im NG. Falls auch dort kein Treffer, liegt der Punkt irgendwo im weißen 
Zwischenraum, ansonsten im entsprechenden Gitter. "Suche im Gitter" 
bedeutet dabei, dass man die zum Punkt gehörende Zelle bestimmt, und 
dann testet, ob der Punkt im darin enthaltenen Kreis liegt.

Berechnen muss man für den Punkt (x, y) in einer Routine "Calculate" 
folgende Größen:

1

  // Gitterindizes des Gitterpunkts M = (mx, my),

2

  // der am nächsten zum Punkt P = (x, y) liegt

3

  kx = round(x/GX - Shift);

4

  ky = round(y/GY - Shift);

5

6

  // Koordinaten von M

7

  mx = GX*(kx + Shift);

8

  my = GY*(ky + Shift);

9

10

  // Orthogonalabstände des Punkts P von M

11

  dx = mx - x;

12

  dy = my - y;

13

14

  // Quadrat des Abstands zwischen P und M

15

  d2 = dx*dx + dy*dy

Dabei sind kx und ky Integers, Rest Floats. GX und GY sind Breite bzw. 
Höhe der Gitterzellen: GX = 2 und GY = 2·sqrt(3). Der Parameter Shift 
legt fest, ob die Suche im HG (Shift = 0) oder im NG (Shift = 0.5) 
stattfindet.

Der übergeordnete Testalgorithmus könnte zum Beispiel so codiert werden:

1

  t = 0;

2

  Calculate(0.0);

3

  if (d2<1.0) {

4

      t = 1

5

  }

6

  else {

7

      Calculate(0.5);

8

      if (d2<1.0) {

9

          t = 2

10

      }

Danach weiß man Bescheid: Wenn t = 0 liegt der Punkt im Zwischenraum, 
sonst im Kreis um (mx, my). Wenn t = 1 ist es ein HG-Kreis und bei t = 2 
ein NG-Kreis.

So würde ich es machen. Man kann sogar mit ziemlich hoher 
Wahrscheinlichkeit voraussagen, ob es im Trefferfall ein HG- oder 
NG-Treffer sein wird: Wenn round(2*y/GY) mod 2 gleich 0 ist, wird es 
wahrscheinlich ein HG-Treffer sein und wenn gleich 1 ein NG-Treffer. 
Dadurch kann man die mittlere Zahl der "Calculate"-Aufrufe verringern - 
wichtig, wenn die Rechenzeit kostbar ist. Den Sinn hinter "round(...) 
mod 2" kann sich der geneigte Leser selbst überlegen.

Vom Startkreis aus, den Winkel berechnen, wo der nächste Kreis sein so. 
In den Bild 45 Grad. Nun einfach vom Startpunkt = Mittelpunkt des 
Kreises, die Koordinaten berechnen. Das ist einfachster Satz den 
Pythagoras.

Habe ich den neuen Mittelpunkt geht das Spiel weiter.

Das kann man per PC mit ein paar schleifen berechnen und Darstellen. 
Oder sogar von Hand.  Ist echt kein Hexenwerk. Wenn man ein paar Dinge 
berücksichtigt (Verhältnis Durchmesser des Kreises zum Winkel des neuen 
Mittelpunkt) kann man sogar Kreisüberschneidungen vermeiden.

>Du brauchst so sogar noch gfs mehr Abprüfungen, weil du
>erst einmal blind suchst, statt strategisch zu prüfen.

Was meinst Du denn mit "blind suchen" bzw. "strategisch prüfen"? Bitte 
um Erklärung.

Ich kann Dir aber noch eine hübsche Lösung präsentieren: Man rastert die 
Fläche in 1 breite und sqrt(3) hohe Zellen, wobei die linke, untere Ecke 
der (0, 0)-Zelle mit dem Ursprung = MP des grünen Kreises zusammenfallen 
soll. Dann definiert man zwei Untergitter, ein helles und ein dunkles, 
just wie die Felder auf einem Schachbrett (siehe Bild). Dann enthält 
jede Zelle genau zwei Kreisviertel, wobei auch die Lage in allen hellen 
Zellen identisch ist, und ebenso in allen dunklen Zellen.

Mit zwei "round" (oder "floor") weiß man, in welcher Zelle ein Testpunkt 
liegt. Ob es eine helle oder dunkle ist, gibt die Summe aus dem 
x-Zellenindex und dem y-Zellenindex an: Ist sie gerade, ist es eine 
helle Zelle, sonst eine dunkle.

Bei einer hellen Zelle prüft man den Kreis mit der linken untere 
Zellenecke als Mittelpunkt, und im Erfolglosigkeitsfall den Kreis mit 
der rechten oberen Zellenecke als Mittelpunkt. Bei einer dunklen Zelle 
entsprechend die rechte untere und linke obere Ecke.

Macht für einen Testpunkt zwei "round"-Aufrufe und im statistischen 
Mittel 1.5 Kreis-Prüfungen (bzw. 2, wenn Du Doppelzugehörigkeiten 
detektieren willst). Wenn das jemand unterbieten kann, bin ich sehr 
gespannt.

>Ohne 2 Abfragen geht es nicht

Wenn Dir das Erkennen von Doppelzugehörigkeiten wichtig ist: Ja. Sonst 
geht es auch mit einer einzigen Kreis-Abfrage. Der Algorithmus von Yalu 
(16.07.2020 13:22) zeigt, dass fünf "floor"-Aufrufe mit den richtigen 
Argumenten genug Information liefern. Eine Lösung, die ganz ohne "if" 
auskommt - auch schick.

Betreffend der Doppelzugehörigkeiten muss ich mich korrigieren: In 
meiner "Schachbrettmuster-Lösung" fällt ein Punkt mit dem Berührpunkt 
zweier Kreise zusammen, wenn er genau in der Mitte einer Zelle liegt. 
Das kann man einfach vorab über (ggf. toleranzbehaftete) 
Koordinatengleichheit prüfen, d. h. dazu ist keine Distanzberechnung 
nötig.

Richtig ist also: "Macht für einen Testpunkt zwei /round/-Aufrufe und im 
statistischen Mittel 1.5 Kreis-Prüfungen.

Davon abgesehen: Diese Doppeldeutigkeiten betreffen nur einen winzigen 
(asymptotisch gegen Null gehenden) Flächenanteil. Da stellt sich dann 
auch die Frage, inwiefern das irgendwo praktisch relevant sein sollte.