Nächstliegendes Pixel ermitteln

[Khabarakh]

In einem Bild von einem anderen Pixel aus das nächstliegende Pixel - z.B. mit einer bestimmten Farbe - finden. Klingt leicht, ist es aber nicht, jedenfalls nicht für mich ^^ .
Man könnte stupide durch das gesamte Bild laufen und den niedrigsten Abstand speichern, aber die Laufzeit will ich gar nicht wissen ;) .

Meine bisherige Idee:
Zuerst einmal vereinfachen wir das Problem auf den ersten Oktanten (das Startpixel sei der Ursprung), wie es zum Bleistift auch der Bresenham-Algorithmus macht.
Als erstes wird der Punkt selbst abgefragt, also (0|0). Der bisher höchste Abstand, also 0, wird gespeichert. Nun beginnt der Algorithmus bei (1|0) und läuft nach oben, solange der Abstand des aktuellen Pixels nicht größer als der vorhin gespeicherte Abstand + 1 ist. Zusätzlich wandert der Algorithmus ein Pixel nach links, falls Gleiches für diesen zutrifft. Nun wird wieder der höchste Abstand für diese "Reihe" (wohl eher Bogen) gespeichert und es geht bei (2|0) wieder los.
Für die ersten Pixel sähe das so aus, wobei Pixel im gleichen Bogen gleich gefärbt sind.

(He, wo bleibt das Alpha-Blending :? ? Klickt einfach einmal auf das Bild)

Der Algorithmus ist zwar nicht ganz korrekt in der Reihenfolge, aber da sich die Abweichung in Grenzen hält, ist das für mein Vorhaben völlig in Ordnung.

Habt ihr Vorschläge oder vielleicht sogar (ich muss fast sagen: hoffentlich ;) ) einen anderen Algorithmus?

[himitsu]

PNG und IE vertragn sich nicht :zwinker:


am einfachsten du gehst in kreisähnlichen Bahnen vom Pixel aus nach außen und das erste Pixel was übereinstimmt ist automatisch das nächste.

z.B.

Code:

.IBH
J837G
C4x2A
K516F
.D9E

[DGL-luke]

Ich würd auch in rechteckigen Spiralen rundrum gehen. Dann ist das erste getroffene Pixel das nächste.

[/Eigenwerbung]

EDIT: mir fällt ein, nicht zwingend... man sollte da nochmal die distanz berechnen, d = sqrt(dx*dx+dy*dy), und noch einmal rundrum gehen. das sollte reichen ;)

[himitsu]

Zitat:

Zitat von DGL-luke

EDIT: mir fällt ein, nicht zwingend... man sollte da nochmal die distanz berechnen, d = sqrt(dx*dx+dy*dy), und noch einmal rundrum gehen. das sollte reichen ;)

einmal muß da nicht reichen ... nimm mal 'nen kreis mit 10 Pixel Durchmesser, da sind es schon mehr als einer Runde.

[add]
Und nochwas ... deine Spiralen sind wohl auch nicht so gut (wenn ich jetzt nichts übersehn hab), denn was passiert, wenn der Punkt nahe am Rand des Bildes ist?

[Khabarakh]

@DGL-luke: Wie gesagt, einmal reicht nicht, sondern Ceil(d - Sqrt(d))-mal. Und das ist einfach zu viel.

@himitsu: Und jetzt verallgemeiner das mal ;) . Dann solltest du auf etwas ziemlich Ähnliches wie ich kommen :zwinker: .
Das Problem sind ja solche Reihenfolgen:

Code:

(Lückenfüller, damit die erste Zeile eingrückt wird -.-) 
                  4



                  2
M                 1 3

Zitat:

Zitat von himitsu

PNG und IE vertragn sich nicht :zwinker:

Argh, was denkst du von mir :stupid: ? Das funktioniert auch bei meinem geliebten FF nicht.

[himitsu]

Zitat:

Zitat von Khabarakh

Argh, was denkst du von mir :stupid: ? Das funktioniert auch bei meinem geliebten FF nicht.

Und warum behauptet ihr dann, daß er FF sooooo toll sei?

Delphi-Quellcode:

MaxW := Max(X, BildBreite - X);
MaxH := Max(Y, BildHöhe - Y);
MaxiamalerRadius := Abstand(X-Y zu MaxW-MaxH);
GefundenX := -1;  //irgendeinen Wert für nichts gefunden
For Radius := 1 to MaxiamalerRadius do Begin
  WinkelTeile := 2 * Pi * Radius {Umfang};
  For WinkelTeil := 1 to WinkelTeile do Begin
    PixelX := X + Sin(2 * Pi * WinkelTeile / WinkelTeil);
    PixelY := Y + Sin(2 * Pi * WinkelTeile / WinkelTeil);
    If (PixelX >= 0) and (PixelX < BildBreite) and (PixelY >= 0) and (PixelY < BildHöhe)
      and (Bild.Pixel[PixelX, PixelY] = Farbe) Then Begin
      GefundenX := PixelX;
      GefundenY := PixelY;
      SchleifenVerlassen;
    End;
  End;
End;
If GefundenX <> -1 Then // was gefunden

Optimierungen wären z.B., wenn du sobald du über den Bildrand kommst, den außenliegenden Bereich überspringst.

statt:

Delphi-Quellcode:

PixelX := X + Sin(2 * Pi * WinkelTeile / WinkelTeil);
PixelY := Y + Sin(2 * Pi * WinkelTeile / WinkelTeil);
If (PixelX >= 0) and (PixelX < BildBreite) and (PixelY >= 0) and (PixelY < BildHöhe)
  and (Bild.Pixel[PixelX, PixelY] = Farbe) Then Begin

irgendwie den Wiedereintritt berechnen (irgendwie so ... denk ich ma):

Delphi-Quellcode:

PixelX := X + Sin(2 * Pi * WinkelTeile / WinkelTeil);
PixelY := Y + Sin(2 * Pi * WinkelTeile / WinkelTeil);
If PixelX < 0 Then Begin
  //Seitenkante des Bildes, welche gerade durchbrochen wurde, als Sekante ansehen
  //den anderen Schnittpunkt berechnen
  //Winkel zum anderen Schnittpunkt errechnen

  //Winkel umrechnen (von 2*Pi nach WinkelTeile)
  i := neuerWinkel * WinkelTeile / 2 * Pi;

  //vielleicht solltest du doch lieber While-Schleifen verwenden
  //denn da kannst du ja offiziell den WinkelTeil ändern (also nicht so wie ich das mache ^^)
  If i > WinkelTeil Then PInteger(@WinkelTeil)^ := i;
End;
...
If PixelX < BildBreite Then ...
If PixelY >= 0 Then ...
If PixelY < BildHöhe Then ...
If (PixelX >= 0) and (PixelX < BildBreite) and (PixelY >= 0) and (PixelY < BildHöhe)
  and (Bild.Pixel[PixelX, PixelY] = Farbe) Then Begin