Ausgehend von einem Koordinatensystem einer Fläche, bei der der Nullpunkt links unten im Bild ist und der Mittelpunkt X,Y bei d=r/2 soll ein Gebiet in Kreise eingeteilt werden. Es muss entschieden werden, zu welchem Kreis eine Koordinate gehört. Ausgegeben soll der relative Wert gegenüber dessen Mittelpunkt. Der Wert rangiert also wieder zwischen -r und r. Um das zu berechnen, bräuchte ich aber erst die Mittelpunkte des getroffenen Kreises und die Abfrage ist nicht so trivial. Bei Quadraten würde ich einfach eine Integer-Rechnung benutzen mit NummerX = (X / D). Das geht bei Kreisen nicht, weil sich die möglichen Koordinaten überschneiden. Wie formuliere ich möglichst einfach eine Formel, die mir die Mittelpunktkoordniaten des Kreises angibt?
Angehängte Dateien:
-
kreisdiagramm.gif
14 KB
Die Mittelpunkte liegen alle auf gleichseitigen Dreiecken. Der Rest ist einfache Geometrie. Wie sieht Dein Ansatz bisher aus?
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 :-)
Angehängte Dateien:
-
Koordinantensystem.png
16 KB
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.
Angehängte Dateien:
-
kreise1.png
25 KB -
kreise2.png
30 KB -
kreise3.png
29 KB
Dabei ist (x,y) der zu untersuchende Punkt, (x_c,y_c) der nächstliegende Kreismittelpunkt, r der Kreisradius und s_c der Abstand des Punktes zum Kreismittelpunkt. Mir war nicht ganz klar, was mit "Nullpunkt links unten im Bild" gemeint ist. Ich habe ihn mal ins Zentrum des links unten liegenden Kreises gelegt. Sollte er woanders liegen, ist das ja nur eine Translation. Ich habe die Ergebnisse im angehängten Bild (kreise1.png) visualisiert. Das grüne Kreuz ist der angenommenen Koordinatenursprung, die Kreise haben einen Radius von 100 Pixel. Die Helligkeit der in den Kreisen liegenden Pixel zeigen den berechneten Abstand zum zugehörigen Kreismittelpunkt an: schwarz=0, weiß=r. Pixel, die in keinem Kreis liegen, sind rot gezeichnet. 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. Mit den obigen Formeln ist der "Einzugsbereich" jedes Kreises ein regelmäßiges Sechseck, das den mittleren Kreise enthält und keine Überlappung mit benachbarten Kreisen aufweist (kreis3.png). Nach erfolgter Zuordnung muss man nur noch über die Distanz zum Mittelpunkt prüfen, ob der Punkt tatsächlich innerhalb des Kreises liegt.
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?
Dr. Sommer schrieb: > rechne eionfach den Abstand deiner Koordinate zu allen > Kreismittelpunken. Und mit einer geschickten Vorauswahl kann man "alle" auf 2 reduzieren (s. Beitrag von Maxe).
Angehängte Dateien:
Das Zauberwort heißt Restklassenbetrachtung. Hier eben einmal mit dem Offset der möglichen Überschneidung, dann gibt es für Y zwei Lösungen Y1 und Y2 Für X gibt es die wiederum, wenn man in Halben rechnet, um jeweils die geraden und ungeraden Reihen als mögliche Lösung zuzulassen. X1 und X2 sind dann jeweils um R versetzt. Dann muss nur anhand der Kreisgleichung geprüft werden, welche der 4 Kombinationen (X1,Y1), (X1,Y2), (X2,Y1), (X2,Y2) passt. Der kleinste ermittelte lokale Radius gibt an, zu welchem Quadrat der Punkt gehört und ist er kleiner als R liegt er eben drinnen. Damit kann man die Zugehörigkeit bei überlappenden Kreisen ermitteln. In der BV nutze ich das öfters für die Ermittlung von virtuellen RGB-Koordinaten bei kreisförmigen Bildfiltern. Der lokale Radius ist dabei der Gewichtungsfaktor für den Bildpunkt.
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.
Angehängte Dateien:
-
Sechseckkachelung.jpg
26 KB
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.
Angehängte Dateien:
-
Mach_zwei_draus.jpg
100 KB
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.
Egon D. schrieb: > Ich hätte das Raster um (r/2) in X-Richtung verschoben. > Dann verschwinden nämlich die roten Doppellinien. Hm, zunächst noch nicht, denke ich. Dazu müsste auch Y verschoben werden, es ist aber nicht eindeutig, um wieviel. Es gibt 2 Möglichkeiten. Es hängt davon ab, ob ein Kreis auf einer der vollen oder der halben gelben Linien getroffen wird. Es bleibt also bei 2 Abfragen, ob der Zielpunkt in einem Kreis liegt. Da man diese Rechnung ohnehin machen muss, um zu prüfen, ob man innerhalb oder in einem Freibereich ist, kann man es auch direkt tun. Es gibt übrigens Punkte, mit 2 Lösungen, weil die Kreise sich ja an einem Punkt berühren. Schlaumaier schrieb: > 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. Und woher weiss der TE, welchen Kreis er prüfen soll? Dazu braucht er dessen Mittelpunkt und wegen der Dualität der Lösungsmenge muss er mehrere Prüfungen machen. Darum dreht sich ja die Diskussion. Wenn die Kordinate ganzzahlig zu "gelb" passt, dann weiß man, dass man nur 1 von 2 Berührungspunkten suchen muss, was eine Verinfachung wäre, aber auch dazu muss zunächst diese Bedingung wieder abgefragt werden. Ohne 2 Abfragen geht es nicht. Das ist mal sicher. Es sind jeweils 2 von 4 theoretischen Fällen, die man vorauswählen kann. Ich halte dies für die einfachst zu prüfene Variante, ohne Vorrechnung. Eine Koordinatentransformation kann dann sinnvoll sein, wenn man ein unbekanntes System hat, dass noch schräger verschoben, oder variabel ist. LostInMusic schrieb: > Der Algorithmus ist klar: Suche zunächst im HG. Falls ohne Erfolg, suche > im NG. Super gut, nur: Du brauchst so sogar noch gfs mehr Abprüfungen, weil du erst einmal blind suchst, statt strategisch zu prüfen. Über die Restklassen kriegt man aber direkt die 4 Kombinationen raus, und über die UND-Verknüpfung die beiden die alternierend infrage kommen. Es kann natürlich sein, dass die Restklassenberechnung auf einem PC nicht zu effektiv ist. In meinem Fall verwende ich ein Oversampling von 3x3 je Senosrpixel und kann binär rechnen. Wenn man das Gitter hier einmal vorskaliert, müsste das auch gehen.
Angehängte Dateien:
-
KleinesGitter.jpg
34 KB
>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.
Beitrag #6353609 wurde von einem Moderator gelöscht.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.