Forum: Digitale Signalverarbeitung / DSP Gebietsunterteilung berechnen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Planer (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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?

von mittelpunkt (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Die Mittelpunkte liegen alle auf gleichseitigen Dreiecken.
Der Rest ist einfache Geometrie.


Wie sieht Dein Ansatz bisher aus?

von mittelpunkt (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nachtrag:  Was soll das sein: "bei d=r/2"?

von MaWin (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Planer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Planer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Planer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Maxe (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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 :-)

von Maxe (Gast)


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

von zoggl (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert

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.

von Dr. Sommer (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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?

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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).

von Jürgen S. (engineer) Benutzerseite


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

von LostInMusic (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Noch eine etwas andere Lösung.

Berechne in einer Schleife i = 0...11 diese Größen:
sx = i;
sy = sqrt(3) * (i mod 2);

dx = x - sx;
dy = y - sy;

u = round(+by*dx - bx*dy);
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) u + v = round(0.5*dx)
(2) u mod 3 = 0
(3) v mod 3 = 0

Darauf testet man also mit "if" und im Trefferfall berechnet man
mx = sx - 8/3*sqrt(3)*(u*ax + v*bx)
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.

von LostInMusic (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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:
  // Gitterindizes des Gitterpunkts M = (mx, my),
  // der am nächsten zum Punkt P = (x, y) liegt
  kx = round(x/GX - Shift);
  ky = round(y/GY - Shift);

  // Koordinaten von M
  mx = GX*(kx + Shift);
  my = GY*(ky + Shift);

  // Orthogonalabstände des Punkts P von M
  dx = mx - x;
  dy = my - y;

  // Quadrat des Abstands zwischen P und M
  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:
  t = 0;
  Calculate(0.0);
  if (d2<1.0) {
      t = 1
  }
  else {
      Calculate(0.5);
      if (d2<1.0) {
          t = 2
      }

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.

von Schlaumaier (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jürgen S. (engineer) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von LostInMusic (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
>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.

von LostInMusic (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.