Kacheln einer Karte von der Mitte aus iterieren

[PatkIllA]

Ich habe eine Karte die aus gleichen rechteckigen Kacheln in eriner Art Schachbrettmuster besteht.
Nun möchte für einen rechteckigen Ausschnitt die notwendigen Kacheln iterieren. Der Ausschnitt beginnt endet nicht notwendigerweise an den Kachelgrenzen
Allerdings will ich das zeilen/spaltenweise sondern von der Mitte ausgehend machen, weil das den Nutzer am ehsten interessiert.

Für jede Kachel ein DummyObject erstellen und dann nach Abstand zur Mitte sortieren geht in 10 Zeilen.
aber das muss doch auch mit ein paar schicken Schleifen gehen.

[Kennung Eins]

Jede Kachel bei ihrer Erzeugung (ich nehme an es sind Objekte) direkt ihren Abstand zur Mitte in x und y und diagonal berechnen lassen? Kommt halt auf deine Struktur an...

[Monger]

Also... Du hast ne einfache Lösung für dein Problem, aber sie gefällt dir nicht? Warum denn nicht?

[PatkIllA]

Ich will die Kachel ja direkt in der richtigen Reihenfolge erstellen, Daten laden und auf dem Bildschirm darstellen und dann wieder vergessen.

Also... Du hast ne einfache Lösung für dein Problem, aber sie gefällt dir nicht? Warum denn nicht?
Bei der naiven Möglichkeit schon mal alle zum erstellen passiert erstmal einige Zeit gar nicht oder es ist mir früher auch schon mal aus Speichermangel abgesürzt.
Z.B. ganz Deutschland mit 100m Kacheln gibt zig Millionen Objekte und nur die Referenzen in einer Liste brauchen schon hunderte MB Speicher am Stück. Bei 32Bit ging das nicht.
So ein Bildaufbau würde wahrscheinlich eh abgebrochen werden aber Abstürz geht gar nicht und so Zeit wo gefühlt nichts passiert sind unschön.

Im Moment gibt es einen Abbruch wenn es mehr als x Kacheln sind. Ich bin aber aus anderen Gründen eh an der Stelle dran.

[Monger]

Schon aus Neugier heraus: was für ne API benutzst du denn?
Nach welchen Kriterien kannst du denn ne Kachel aussuchen? Sind die nummeriert?

Aber ich würde vermuten, du kommst irgendwie an die Koordinaten der Kacheln heran ohne die ganze Kachel zu laden

[PatkIllA]

Schon aus Neugier heraus: was für ne API benutzst du denn?
Nach welchen Kriterien kannst du denn ne Kachel aussuchen? Sind die nummeriert?

Aber ich würde vermuten, du kommst irgendwie an die Koordinaten der Kacheln heran ohne die ganze Kachel zu laden
Das ist in C#.
Ich weiss halt Kacheln sind x Meter breit und y Meter hoch und fangen auch immer bei einem Vielfachen davon an. Aus x und y kann ich also einfach durch die Breite/Höhe teilen und finde aus dem x/y Index die nötigen Daten. Im einfachsten Fall ist das eine Datei 1234_5678.png

Ich muss die Daten bei meienm Problem noch gar nicht laden. Nur das Erzeugen und sortieren von zig Millionen Objekte sprengt Laufzeit und Speicher.

Ich möchte die Objekte von der Mitte aus aufzählen ohne alle vorher erzeugen zu müssen.
Mit yield return oder eigenen Enumerator implementieruingen kann man das ja alles schön lazy machen.

[Monger]

Ne, ich meine: wo kriegst du deine Daten her? Hast ja bestimmt irgend nen Kartendienst angebunden, oder?

[PatkIllA]

In dem Fall sind die aus Fremdsystemen (GIS) ausgespielt. Das Formt kann ich auch nicht so ändern.
Kartendienst geht auch aber darum geht es nicht.
Normalerweise wird da auch automatisch im Detailgrad umgeschaltet.
Der Anwender kann aber auch einen Detailgrad forcieren und dann rauszoomen.

[Tesseract]

wenn du "spiralförmig" von der mitte nach außen gehen willst kannst du das konzeptionell mit einer for-schleife mit dem statement
{
move(i);
turnRight();
move(i);
turnRight();
}

iterieren wobei die richtungen +x, -y, -x, +y sind und mitte bzw. bounds durch den ausschnitt festleget werden. das wäre in etwa das was z.B. cinebench macht. bei einem rechteck muss man die ungleichen x/y dimensionen natürlich speziell berücksichtigen.

alternativ vielleicht eine angepasste version von flood fill (https://en.wikipedia.org/wiki/Flood_fill).

[KhanRKerensky]

Denk anstatt Kacheln in Pixel und such dir einen passenden Füllalgorithmus aus der von der Mitte anfängt. Du könntest von deinem Mittelpunkt in einer "square spiral" wandern.

In der Kategorie "aber das muss doch auch mit ein paar schicken Schleifen gehen":
Taxi distance! Das ist einfach nur x+y. Fängst in der mitte an und lädst alle Tiles mit der Distanz 1: (0,1) und (1,0), dann alle mit der Distanz 2: (0, 2), (1, 1), (2,0) usw.
Natürlich in allen vier Quadranten und nicht nur im positiven.

>>> def taxi_diamond(width, height):
print("(0, 0)")
for dist in range(1, width+height):
for x in range(dist):
y = dist-x
for i in range(4): # print all 4 rotations
if abs(x) < width and abs(y) < height:
print("({}, {})".format(x,y), end=" ")
x, y = -y, x # thats a 90° turn
print()


>>> taxi_diamond(4, 6)
(0, 0)
(0, 1) (-1, 0) (0, -1) (1, 0)
(0, 2) (-2, 0) (0, -2) (2, 0) (1, 1) (-1, 1) (-1, -1) (1, -1)
(0, 3) (-3, 0) (0, -3) (3, 0) (1, 2) (-2, 1) (-1, -2) (2, -1) (2, 1) (-1, 2) (-2, -1) (1, -2)
(0, 4) (0, -4) (1, 3) (-3, 1) (-1, -3) (3, -1) (2, 2) (-2, 2) (-2, -2) (2, -2) (3, 1) (-1, 3) (-3, -1) (1, -3)
(0, 5) (0, -5) (1, 4) (-1, -4) (2, 3) (-3, 2) (-2, -3) (3, -2) (3, 2) (-2, 3) (-3, -2) (2, -3) (-1, 4) (1, -4)
(1, 5) (-1, -5) (2, 4) (-2, -4) (3, 3) (-3, 3) (-3, -3) (3, -3) (-2, 4) (2, -4) (-1, 5) (1, -5)
(2, 5) (-2, -5) (3, 4) (-3, -4) (-3, 4) (3, -4) (-2, 5) (2, -5)
(3, 5) (-3, -5) (-3, 5) (3, -5)

/edit: Hätte nicht so lange mit python rumspielen sollen.

[PatkIllA]

Das mit der Spirale klappt so nicht weil die Kacheln nicht unbedingt quadratisch sind.
Selbst mit quadratischen klappt das mal nach links mal nach rechts nicht.
Je nach dem welchen Ausschnitt ich wähle kommen da schon andere Muster bei rum. Der Mittelpunkt liegt in der Regel mitten in einer Kachel.

Die gewünschte Reihenfolge könnte da z.B komplett anders sein.
Wenn der Mittelpunkt der Karte links in der Startkachel ist dann ist sind die nächsten beiden oben und links daneben und die vierte die quer links oben.

Wenn man aber den Mittelpunkt mitten in der Startkachel hat dann kommen erst jeweils die Kacheln links und oben unten wie in einem Kreuz und erst dann die diagonalen.

[Tesseract]

spielt das überhaupt eine rolle? deiner beschreibung nach sind die anforderungen nicht wirklich klar. soll das ganze nun möglichst einfach und schnell oder exakt sein? eine große anzahl an tiles deutet eher auf ersterers hin. wenn du über zig millionen tiles itererst kann es doch nicht entscheidend sein ob exakt nach distanz oder nur grob nach distanz iteriert wird. muss das ganze vollständig sein oder kann sparse gelesen und interpoliert werden bei vielen objekten? um welche daten geht es da? wird das ganze nur visualisiert?

[KhanRKerensky]

Dann halt so:

Du fängst mit deiner Startkachel an und wirfst alle Nachbarkacheln in eine prio-queue (sortiert nach Abstand). Kachel aus der queue nehmen, wegwerfen falls ausserhalb deines Bereichs, ansonsten alle unbesuchten Nachbarn in die queue packen. Wiederholen bis die queue leer ist.

Ob das halbwegs performt hängt davon ab wie schnell die queue die vielen sortierten inserts hinbekommt.

[PatkIllA]

spielt das überhaupt eine rolle? deiner beschreibung nach sind die anforderungen nicht wirklich klar. soll das ganze nun möglichst einfach und schnell oder exakt sein?Im Normalfall sind das vielleicht ein dutzend Kacheln. Da fällt es schon negativ auf wenn regelmäßig Kacheln am Rand eher da sind in der Mitte aber noch ein weißer Fleck ist.
Wegen Multithreading, unterschiedlich komplexen Kacheln, Caching usw kann ich das zwar eh nicht 100% ausschließen aber der Normalfall sollte von der Mitte ausgehen.
Das kreisförmige nachladen sieht optisch auch am ähnlichsten aus, wenn die Karte gedreht wird.

Dann halt so:

Du fängst mit deiner Startkachel an und wirfst alle Nachbarkacheln in eine prio-queue (sortiert nach Abstand). Kachel aus der queue nehmen, wegwerfen falls ausserhalb deines Bereichs, ansonsten alle unbesuchten Nachbarn in die queue packen. Wiederholen bis die queue leer ist.

Ob das halbwegs performt hängt davon ab wie schnell die queue die vielen sortierten inserts hinbekommt.
Die unbesuchten Kacheln werden ja auch immer mehr. Immer noch deutlich weniger als alle aber schon nicht ohne.

[Monger]

Wenn man sich mal etablierte Kartendienste anschaut, dann arbeiten die ja mit unterschiedlich aufgelösten Kacheln. Ergo:

Viewport bestimmen
Die Kachel suchen die den ganzen Viewport bedeckt (meist megamatsch)
Höher aufgelöste Kacheln suchen die den Viewport bedecken und übermalen
Rinse and repeat bis Auflösung zufriedenstellend

Ergo, mehr als ein paar dutzend Kacheln sind da nie im Speicher. Google Maps etc. haben auch nicht den Anspruch, dass das sauber von der Mitte aus passieren muss. Überlappungen sind erlaubt und erwünscht, Kachelgrößen dürfen variieren.

Setzt aber halt voraus, dass alle Daten irgendwo abgelegt sind wo sie effizient gefiltert und abgefragt werden können. So wie du das beschreibst, klingt es so als hättest du ganz viel davon im Speicher.

[Monger]

Hier wie sie sich das bei Bing Maps vorstellen

https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system

Und hier ein Beispiel für nen Aufruf:
https://docs.microsoft.com/en-us/bingmaps/articles/accessing-the-bing-maps-rest-services-using-php#working-with-the-imagery-api

Du rasterst also erstmal dein Feld, und fragst dann für alle Mittelpunkte Kacheln mit der gewünschten Detailstufe an.

[PatkIllA]

@Monger
Im Normalfalls wird das auch umgeschaltet oder Teile weggelassen usw.

Der Benutzer kann das aber bewusst abschalten weil er vielleicht bei 1:2000 auch noch die Detailansicht haben will und nicht die automatische Umschaltung bei 1:1000. Dann aber noch ein paar mal am Mausrad gedreht und schon sieht er statt einem Straßenzug das ganze Bundesland. Da will man nicht für jede Ebene noch mal Grenzen konfigurieren es soll aber eben auch nicht zum Fehler/Absturz kommen.

Das exakt von der Mitte muss eigentlich nur für den Normalfall mit wenigen Kacheln funktionieren.

Ich habe nur die Infos über die Kachelbreite und Höhe und kann dann beim Zeichnen nachschauen ob da eine passende Datei liegt.

Du rasterst also erstmal dein Feld, und fragst dann für alle Mittelpunkte Kacheln mit der gewünschten Detailstufe an.Die Rasterung des Feldes gibt bei dem erzwungenen Detailgrad aber halt evtl 100 Millionen Kacheln. Das ist doch das Problem, dass ich durch die schwrittweise Rasterung von der Mitte ausgehend umgehen will.
Es geht NICHT darum wie das im Normalfall sein sollte. Die jetztige Fehlermeldung mit zuvielen Kacheln kommt immer mal wieder im Support an.

[Tesseract]

Im Normalfall sind das vielleicht ein dutzend Kacheln. Da fällt es schon negativ auf wenn regelmäßig Kacheln am Rand eher da sind in der Mitte aber noch ein weißer Fleck ist.

wenn die spanne so extrem groß ist ist das problem nicht so ohne weiteres "einfach" elegant zu lösen. ist der rechteckige ausschnitt das screencanvas? wenn ja und wenn keine mipmapstufen vorliegen bzw. die tiles nur atomar lesbar sind wäre eine möglichkeit vielleicht eine art radialer adam7 (https://en.wikipedia.org/wiki/Adam7_algorithm) wo für jedes "pixel" das nearest neighbor tile ermittelt und in eine entsprechende 2D-datenstruktur eingetragen wird ähnlich wie beim rendern von polygonen mit einem z-buffer wobei der z-buffer anzeigt welche fläche bereits von tiles abgedeckt ist. wenn die tiles sehr groß sind landen nur wenige tiles in der datenstruktur und die meisten sampleversuche scheitern am "z-buffer" und bei riesigen ausschnitten die millionen von tiles abdecken bekommt man so eine art dithermuster das sich iterativ verbessert und auch dann nach absehbarer zeit etwas halbwegs sinnvolles anzeigt weil nur ein bruchteil der tiles tatsächlich gelesen werden muss.

aber das war jetzt nur ein schnelles brainstorming, gibt sicher noch andere möglichkeiten das zu lösen :D

[KhanRKerensky]

100 Millionen Kacheln

Selbst wenn jede Kachel nur einen Pixel groß wäre... worauf wird das dargestellt? Ab einem Schwellwert sollte man vieleicht nicht versuchen alle Kacheln eines Bereichs zu ermitteln, sondern zu jedem Pixel nur eine Kachel. Und auf Pixelebene würde ich dann eine square spiral mit 8x8 Pixel Blöcken oder so nehmen.

Die unbesuchten Kacheln werden ja auch immer mehr. Immer noch deutlich weniger als alle aber schon nicht ohne.
Der Speicherverbrauch müsste irgentwo bei O(sqrt(n)) liegen. Das erkaufst du dir aber mit erheblich mehr Rechenaufwand. Stürtzt also nicht ab, braucht aber ewig. Wenn das Rendering die GUI nicht lahmlegt und sowieso nur in Sonderfällen vorkommt: Progressbar einbauen!

[PatkIllA]

Selbst wenn jede Kachel nur einen Pixel groß wäre... worauf wird das dargestellt? Ab einem Schwellwert sollte man vieleicht nicht versuchen alle Kacheln eines Bereichs zu ermitteln, sondern zu jedem Pixel nur eine Kachel. Und auf Pixelebene würde ich dann eine square spiral mit 8x8 Pixel Blöcken oder so nehmen.Da beibt nur ein gekriesel über.
Ich hatte halt gehofft es gibt da einen effizienten Algorithmus zum Füllen. Scheint ja nicht so zu sein.
Bei x Kacheln einfach mt einer Meldung direkt abzubrechen war halt der Quickfix gegenüber dem Absturz wegen Speichermangel vorher. Die Standardsortiermethoden in .NET kann man auch nicht abbrechen,

Der Speicherverbrauch müsste irgentwo bei O(sqrt(n)) liegen. Das erkaufst du dir aber mit erheblich mehr Rechenaufwand. Stürtzt also nicht ab, braucht aber ewig. Wenn das Rendering die GUI nicht lahmlegt und sowieso nur in Sonderfällen vorkommt: Progressbar einbauen!
Das würde eh ewig dauern und wird wahrscheinlich auch abgebrochen.

[schleiftier]

Wenn das aus einem GIS kommt, dann bietet es dir garantiert auch irgendwie Kacheln in verschiedenen Auflösungen an. Musst dann halt passend zur Zoomstufe die richtigen anfragen.

Und zum Rendern: Der Ansatz an jede Kachel ein Render-Objekt zu binden ist Quatsch. Du brauchst immer nur so viele Render-Objekte, dass dein Viewport bedeckt ist und musst sie dann wieder verwenden - damit sparst du dir auch Speicher-Management bzw. Garbage Collection.

Wenn der Nutzer den Viewport verschiebt, dann musst du halt die Render-Objekte die auf der einen Seite rausgeschoben werden an die andere Seite des Viewports verschieben und mit den passenden neuen Daten versehen.

[Screemer]

Wenn das aus einem GIS kommt, dann bietet es dir garantiert auch irgendwie Kacheln in verschiedenen Auflösungen an. Musst dann halt passend zur Zoomstufe die richtigen anfragen.

das will er ja nicht. er will volle auflösung in jeder zommstufe, da die user das qualityscaling deaktivieren können. was ich zwar nicht nachvollziehen kann aber ok.

[PatkIllA]

Wenn das aus einem GIS kommt, dann bietet es dir garantiert auch irgendwie Kacheln in verschiedenen Auflösungen an. Musst dann halt passend zur Zoomstufe die richtigen anfragen.Das kann der Benutzer halt bewusst abstellen und ich kann auch nicht sagen ab wann das nicht mehr richtig sein sollen

Und zum Rendern: Der Ansatz an jede Kachel ein Render-Objekt zu binden ist Quatsch. Du brauchst immer nur so viele Render-Objekte, dass dein Viewport bedeckt ist und musst sie dann wieder verwenden - damit sparst du dir auch Speicher-Management bzw. Garbage Collection.
Das ist schon so. Der ViewPort kann aber halt schnell ziemlich gross sein und bei erzwungenen Details wären das sehr viele Kacheln.