[C#] Datentyp, um Koordinatensystem darzustellen?

...komplette Frage anzeigen

5 Antworten

Erstelle eine eigene Klasse / ein Struct, welches die Werte der 3 Koordinatenachsen abbildet. Zur einfachen Suche könntest du überlegen, ob du einer Koordinate eine ID zuordnen könntest, die sich bspw. wie ein Hashcode berechnen lässt (aber eindeutig).

Crysali 03.07.2017, 23:57

Danke für deine Antwort, da lande ich gedanklich hier:

public struct Vector3 {
public int X {get;}
public int Y {get;}
public int Z {get;}
}
// irgendwie eine (eindeutige) ID ermitteln,
als Schlüssel für das Dictionary
public Dictionary<int, object> meineObjekte

War das so von dir gedacht ?

Hättest du noch einen heißen Tipp bezüglich der Berechnung der ID ? Mir würde beispielsweise so etwas einfallen wie den Schlüssel des Dictionary als string zu nutzen und zu jeder Koordinate den entsprechenden ASCII-Charakter zu ermitteln und dann die drei zusammen als Key zu nutzen. Hab aber so das Bauchgefühl, das das eher ineffizient ist.

0
regex9 04.07.2017, 00:19
@Crysali

Fast. Der Bezeichner Vector3 muss zusammengeschrieben werden und es fehlt noch ein Konstruktor, der die Werte der Koordinaten festlegt.

(...) und zu jeder Koordinate den entsprechenden ASCII-Charakter zu ermitteln (...)

Das hört sich viel zu kompliziert an. Entweder du findest tatsächlich eine Formel, die eine breite Verteilung ermöglicht, z.B.:

f = 4x + 2y + z

Tests: (es müssten aber noch weitere gemacht werden)
V1(1/1/0) = 4 + 2 + 0 = 6 V2(1/0/1) = 4 + 0 + 1 = 5 V3(0/1/1) = 0 + 2 + 1 = 3

oder du konkatenierst die Werte zu einem String:

$"{x}-{y}-{z}"
2
Isendrak 04.07.2017, 00:57
@regex9

Jep, nicht unerheblich besser als meine beiden Ideen.

Allerdings bedingt durch die potentiell unendliche Größe des "Raumes" (naja, bis zur Überschreitung von Int32.MaxValue ;), hätte man bei der Id-aus-Hash-Methode nur eine "relativ" begrenzte Menge an kollisionsfreien Koordinaten. Zumindest, wenn für die Koordinaten Int32 verwendet wird... Bei BigInteger sieht die Sache schon besser, wenn auch "lustiger" aus.

0
Crysali 04.07.2017, 01:12
@regex9

Danke,
habe ich korrigiert, Konstruktor habe ich mir hier gespart, ist ja offensichtlich, wie der auszusehen hat, war da gerade einfach etwas zu faul zum Tippen.

Das mit der mathematischen Funktion wird aber vermutlich immer Kollisionen verursachen, da sich zwangsläufig immer was überschneidet. Ich wüsste in meinem Fall nicht, wie ich diese dann richtig auflösen sollte, das wäre dann ein großes Problem.

Das mit dem konkatenieren ist ein großartiger Vorschlag, das werde ich übernehmen, vielen Dank!

0
regex9 04.07.2017, 01:19
@Isendrak

Einen String als Key zu verwenden, würde ich von daher bevorzugen.

Noch eine Alternative könnte eine Map sein, die Kollisionen zulässt. Inwiefern sich das auf die Performance auswirkt, ist insgesamt eh von der Größe des Koordinatensystems und seinen Maßeinheiten abhängig.

0
regex9 04.07.2017, 01:40
@Crysali

Eine <int, IList<Vector3>> Beziehung wäre eine Möglichkeit. Wenn du einen Index gesucht hast, müsste das Ergebnis (eine Liste) nochmal durchlaufen werden, um den gesuchten Koordinatenpunkt zu bestimmen. Noch etwas geeigneter wäre in diesem Fall aber wohl eine Struktur, die Vektor und Datenobjekt verbindet:

struct Data { Vector3 Point { get; } object Value { get; } };

Insgesamt geht dies allerdings in eine unschöne, umständliche Richtung. Der String-Key ist m.E. die beste Wahl, denn er ist schnell und einfach implementiert.

0

Auf der einen Seite würde sich der Typ System.Windows.Media.Media3D.Point3D anbieten - zusammen mit Vector3D und Matrix3D hat der gleich so ziemlich alles mitgeliefert, was man für Punkte und ihre Darstellungen im 3D braucht.

Auf der anderen Seite hat dieser Typ aber Komponenten vom Typ Double statt Int32.

Immerhin ist Point3D eine struct statt einer class und erfordert von daher kein zusätzliches Objekt bei der Konstruktion. Wenn dir der Overhead und die ständigen Konvertierungen zwischen Double und Int32 nicht behagen, musst du wohl eine eigene struct definieren. (Die Elementen von System.Numerics sind - bis auf BigInteger - nicht wirklich für Integer-Operationen entworfen worden.)

Crysali 04.07.2017, 00:06

Danke, ich werde mal schauen, ob ich das verwerten kann, sieht gut aus.

0

Du könntest was in der Art verwenden:

using System;
using System.Collections.Generic;
public class Data3D{
private Dictionary<Int32, Dictionary<Int32, Dictionary<Int32, object>>> root;
public Data3D(){
root = new Dictionary<Int32, Dictionary<Int32, Dictionary<Int32, object>>>();
}
public void Put(Int32 x, Int32 y, Int32 z, object value){
if(!root.ContainsKey(x))
root[x] = new Dictionary<Int32, Dictionary<Int32, object>>();
if(!root[x].ContainsKey(y))
root[x][y] = new Dictionary<Int32, object>();
root[x][y][z] = value;
}
public object Get(Int32 x, Int32 y, Int32 z){
if(!root.ContainsKey(x))
return null;
if(!root[x].ContainsKey(y))
return null;
if(!root[x][y].ContainsKey(z))
return null;
return root[x][y][z];
}
}

class Test{
public static void Main(string[] args){
Data3D d = new Data3D();
d.Put(2,3,4,"foo.bar");
object v;
v = d.Get(2,3,5);
Console.WriteLine(v==null?"(NULL)":v.ToString());
v = d.Get(2,3,4);
Console.WriteLine(v==null?"(NULL)":v.ToString());
}
}

oder auch sowas:

using System;
using System.Collections.Generic;
using System.Linq;

struct DataObject{
public int X,Y,Z;
public object Data;
}

class Test{
public static void Main(string[] args){
ListData<Object> objects = new ListData<Object>();
objects.Add(new DataObject(){X=2,Y=3,Z=4,Data="foo.bar"});
object v;
v = objects.Where(o => o.X == 2 && o.Y == 3 && o.Z == 5).FirstOrDefault();
Console.WriteLine(((DataObject)v).Data==null?"(NULL)":((DataObject)v).Data.ToString());
v = objects.Where(o => o.X == 2 && o.Y == 3 && o.Z == 4).FirstOrDefault();
Console.WriteLine(((DataObject)v).Data==null?"(NULL)":((DataObject)v).Data.ToString());
}
}

P.S.: Die zweite Variante könntest du z.B. noch in ne "Wrapper"-Klasse packen.

Crysali 04.07.2017, 00:15

Danke für deine Antwort,
die erste Variante ist mir auch schon unter die Nase gekommen. Mich stört an dieser Variante, dass man dann ziemlich viele Objekte in der Gegend rumfliegen hat, weil man für jeden Eintrag drei Dictionaries benötigt, wenn ich das richtig verstanden habe ( unter jedem x muss man eines für alle y erstellen und für jedes y muss man eines für alle z erstellen).

Bei deiner zweiten Variante, was ist dieses ListData ? Ich glaube, die zweite Variante ist mir etwas zu hoch, Linq hatte ich noch nicht. Ich werde mal schauen, ob ich mir das erarbeiten kann.

0
Isendrak 04.07.2017, 00:44
@Crysali

Whoops...

Das sollte eigentlich nicht "ListData<Object>" sondern "List<DataObject>" heissen... Musste die öffnende Dreicksklammer entfernen, weil dieser Bugware Editor sonst beim Einfügen den gesamten Code "gefressen" hätte und hab dann wohl versehentlich die Position verwechselt...

Hier nochmal funktionsfähig und noch etwas erweitert:

using System;
using System.Collections.Generic;
using System.Linq;

class Data3D{
private struct DataObject{
public int X,Y,Z;
public object Data;
}
private List<DataObject> data;
public Data3D(){
data = new List<DataObject>();
}
public void Put(int x, int y, int z, object value){
DataObject oldvalue = (DataObject)data.Where(o => o.X == x && o.Y == y && o.Z == z).FirstOrDefault();
if(oldvalue.Data == null){
data.Add(new DataObject(){X=x,Y=y,Z=z,Data=value});
}
else{
data.Remove(oldvalue);
data.Add(new DataObject(){X=x,Y=y,Z=z,Data=value});
}
}
public object Get(int x, int y, int z){
DataObject value = (DataObject)data.Where(o => o.X == x && o.Y == y && o.Z == z).FirstOrDefault();
return value.Data;
}
}

In der Fassung brauchst du nicht mal zu wissen, was Linq ist, da es nur im "Backend" arbeitet. Also einfach mit "Put(x,y,z,object)" Daten hinzufügen und mit "Get(x,y,z)" Daten abfragen.

P.S.: Um ein Feld zu "löschen", kannst du einfach "Put(x,y,z,null)" benutzen, das "Objekt" bleibt zwar da, wird aber, da es "null" beinhaltet als leer betrachtet. (zugegeben nicht ganz optimal, aber mit n bissl Übung bzgl. Linq kannst dir auch ne eigene "Remove" bzw. "Delete" Methode dazuschrauben ;)

2
Crysali 04.07.2017, 01:09
@Isendrak

Ah, verstehe, danke!
Wenn ich das richtig interpretiere, dann hole ich mir ein Objekt mit der Methode Get, indem ich das erste Objekt (FirstOrDefault) zurückgebe, welches die (Where) die Bedingung erfüllt ? Dann wären wir aber wieder bei sequentieller Suche, das ist nichts anderes als durch eine Liste zu iterieren, oder ?
Behagt mir persönlich nicht so ganz, da ich die Anzahl der Objekte nicht kenne. Wenn da jetzt 10.000 Objekte drinnen sind, dann jedes Mal darüber zu iteriern...

Das Linq schaue ich mir aber glaub mal genauer an, da kann man Sachen ja deutlich abkürzen, ich weiß schon ein paar Stellen, wo ich das gut hätte gebrauchen können!

0
regex9 04.07.2017, 02:11
@Crysali

Ja, so läuft es ab.

Die Intention von Linq ist es, Aggregate (Listen u.ä.) mit SQL-ähnlichen Ausdrücken zu filtern oder zu bearbeiten. So werden diese tatsächlich auch wie SQL-Anweisungen formuliert:

from ... select ... where ...

(s. https://docs.microsoft.com/de-de/dotnet/csharp/programming-guide/concepts/linq/basic-linq-query-operations)

Die Ausdrücke können aber ebenso im funktionalen Stil angewandt werden, so bspw. FirstOrDefault.

data.FirstOrDefault(o => o.X == x && o.Y == y && o.Z == z);

Diese erwarten eine Methode, die einem bestimmten Delegat entspricht. Du kannst eigene Methoden, die du bereits definiert hast, verwenden oder anonyme Methoden (Lambdas). Letztere sehen zwar befremdlich aus, dies liegt aber nur an der Kurzschreibweise.

Hier eine stückweise Herleitung:

Rückgabetyp Methodenname(Parameterliste) { Methodenkörper }
bool        Methodenname(Parameterliste) { return Bedingung; }
                        (o) =>           { return o.X == x && o.Y == y && o.Z == z; }
                        (o) =>                    o.X == x && o.Y == y && o.Z == z
                         o  =>                    o.X == x && o.Y == y && o.Z == z

Das Delegate erwartet eine Funktion, die zum einen einen boolschen Typ zurückgibt und zum anderen ein Argument annimmt, welches von dem Typ ist, den ein Listenelement annimmt (bei einer Liste an Strings wäre dies also ein String, bei einer Liste an Autos ein Auto). Daher wird weder der Rückgabetyp noch der Parametertyp erwähnt.

Die übergebene Methode wird im Filter mehrmals aufgerufen, es handelt sich um einen Callback. Das könnte ungefähr so aussehen (nur zur Vorstellung):

public static bool FirstOrDefault<T>(this IList<T> list, Func<T, bool>  callback){
  foreach(T item in list){
    if(callback(item)){
      return item;
    }
  }

return default(T);
}


2
Isendrak 04.07.2017, 02:13
@Crysali

Jep, das "Zeug" sucht sequentiell...

Und wo ich so drüber nachdenk, kommts noch schlimmer: Mit meinem Vorschlag werden IMMER ALLE Objekte durchiteriert, das ganze hat also eine Laufzeit von O(n)...

Da wäre ne "foreach" Schleife mit Abbruch sobald das Objekt gefunden wurde noch besser... ^^;;;;;

Aber Tatsache ist: Linq ist manchmal wirklich ziemlich praktisch, nur manchmal eben ganz und gar nicht...

0
PWolff 05.07.2017, 01:38
@Isendrak

Ist hier nicht List<DataObject> data immer noch eine unsortierte Liste? Linq sortiert die ja nicht von allein nach Indizes.

SortedList gibt's leider nicht als nur von einem generischen Typ abgeleitet (braucht bisher immer TKey und TValue - es ist ja u. a. ein IDictionary&lt;TKey, TValue&gt;). Wär' schön, wenn's SortedList<T> auch mit IComparer<T> gäbe, oder auch mit Comparison<T>.

0
regex9 04.07.2017, 00:28

Variante 1 verschachtelt Dictionarys? Das ist nicht schön, da könnte der FS auch gleich mehrdimensionale Arrays verwenden.


Variante 2 nutzt genau das, was der FS nicht haben möchte: Eine Iteration über jedes Element, um die Daten linear zu suchen.

Die Where-Klausel würde ich im Übrigen rauslassen und den Lambda-Ausdruck stattdessen gleich in FirstOrDefault packen.
1

Warum machst du nicht eine Liste von Objekten und vergleichst mit der jedes Objekt ob es diese Koordinaten besitzt?

Geht es hier eigentlich direkt mehr um das Objekt oder die Position des Objekts? Denn wenn du ein Dictionary erstellst musst du für den Objektzugriff immer dessen Position wissen, wenn du also sagen willst der PIN auf der Map namens Zuhause soll jetzt Grün sein, musst du die Koordinaten ganz genau wissen...

Edit: Was ich meine mit ob es hier mehr ums Objekt oder Poition geht ist, wie das im Gesamt Projekt ausschaut...

T0RM0D 03.07.2017, 22:34

Du könntest dann ein 3 Dimensionales Array erstellen mit dem Datentyp des Objekts und weißt dort das Objekt mit dessen Koordinaten zu...

Wenn du dann die Koordinaten in diesem Array abrufst, bekommst du das passende Objekt zurück geliefert...

Speichertechnisch natürlich ein Horror! Allerdings sicher schnell!

0
Crysali 04.07.2017, 00:04

Ich benötige beides, ich muss in der Lage sein, über eine Position die Existenz (irgend)eines Objektes an der Position zu überprüfen und ich benötige auch Zugriff auf das Objekt selber, als Adresse, wie du so schön sagst.

Würde ich eine Liste benutzen, wäre Suchen ein Horror, weil ich sehr viele Objekte habe und dann meine Komplexität O(n) wäre, wobei n die Anzahl der Elemente ist. Ich möchte sequentielle Suche vermeiden.
Den dreidimensionalen Array benutze ich, wie du auch angemerkt hast, wegen dem horrenden Speicherplatz nicht. Ich benötige einen Datentyp, mit dem ich an meine Objekte komme. Objekte, die nicht existieren, also leere Positionen, interessieren mich gar nicht.

Das Dictionary schien mir eine gute Wahl zu sein, weil ich sowohl einfach alle Objekte in dem Dictionary durchlaufen, wenn die Objekte wichtig sind, als auch bestimmte Positionen, wenn die Positionen wichtig sind, überprüfen kann.

0
T0RM0D 04.07.2017, 02:07
@Crysali

Du könntest die Suche Beschleunigen in dem du in einer sortierten Liste immer in die Mitte schaust... (Binäre Suche heißt das meines Wissens nach)

Also Quasi: du hast die selbe Liste nochmal nur in allen X Koordinaten sortiert, suchst du jetzt zum Beispiel eine gewisse Koordinate greifst du einmal in die Mitte und schaust nach: ist der Wert größer oder kleiner? Wenn kleiner greife ich auf die Mitte von den geringeren werten und das ganze Spielchen Sollang, bis der Wert gefunden wurde... Dann untersuchst du welche von Objekten haben den selben x Wert und kontrollierst die spezifisch genau... Sollte schneller laufen, jedoch auch auch noch nicht ideal... 

Wichtig neue Werte müssen hier in der sortierten Liste nochmal Richtig eingeordnet werden...

Mit Dictionaries in C# habe ich jetzt leider nicht soviel Erfahrungen(dafür allerdings in Swift)... Jedoch könntest du auch sicher in C# einen String aus den 3 Koordinaten erstellen("10/30/500"), diesen zur Identifikation Wählen und so die einzelnen Objekte ausgeben lassen vom Dictionary... Sollte ein String für dich zu viel Speicherplatz brauchen, kommt es auf deine Limitierung im Koordinaten System an(wenn du einen Integer dafür verwenden willst): angenommen du brauchst maximal 8 Bit für x, 8 für y, und ebenso für z so könntest du dir einen Eindeutigen Wert berechnen lassen, der die Position bestimmt(du bräuchtest hier mindestens 24Bit). Als Beispiel: 

X beginnt bei Bit 0 -> x*2^0->x

Y beginnt bei Bit 8 -> y*2^8 -> y*256

Z beginnt bei Bit 16 -> z*2^16 -> z*65536

x/y/z = 10/30/5

value = x+y*256+z*65536

value = 10+ 7680 + 327680

Value = 335370

Mag als Dezimal Zahl zwar etwas komisch aussehen aber wenn du die Zahl binär betrachtest, sind x, y und z klar von einander jeweils um 8Bit voneinander getrennt...

2
T0RM0D 04.07.2017, 02:15
@T0RM0D

Beweis:

10 = 0000 1010

30 = 0001 1110

05 = 0000 0101

335370 = 

0000 0101|0001 1110|0000 1010

0
PWolff 05.07.2017, 01:23
@T0RM0D

Für den eindeutigen Wert würde ich dann vermutlich ein BigInteger nehmen, da passt das Zeug dann sicher rein. Oder ein int[3].

Oder ein Int64 mit

Int64 value = (x & mask21) | ((y & mask21) << 21) | ((z & mask21) << 42);

(dann hat man jeweils 21 Bytes pro Koordinate verfügbar und auch negative Zahlen sind )

Beim Rücktransformieren muss man noch Bit21 auswerten.

Einfacher wird es natürlich mit

Int16 x, y, z;

und

Int64 value = x | (y << 16) | (z << 32);

dann hat man auch mit der Rückkonvertierung keine Probleme.

-----

Aber am sichersten und wenigstens ebenso schnell sind eine eigene struct und int[3].

1
T0RM0D 05.07.2017, 01:30
@PWolff

Die negativen Zahlen hatte ich vorhin gar nicht beachtet gehabt...

Aber wenn man sich damit stärker auseinander setzt, findet man dafür sicher auch eine Lösung(wenn man die 21Bit ausnutzen möchte)...

Hat man aber bei einem Array dann nicht das Problem, dass die Dictionary die Addresse des Arrays und nicht dessen Werte vergleicht? 

0
T0RM0D 05.07.2017, 01:39
@PWolff

Der Schiebeoperrator existiert in C# auch?

0

Für die Speicherung von Punkten im 3-dimensionalen Raum bietet sich ein R-Baum geradezu an (Effiziente und schnelle Suche von mehrdimensionalen Objekten). Allerdings gibt es im .Net Core keine Implementierung davon, du müsstest also auf 3rd Party Bibliotheken zurückgreifen oder selbst Hand anlegen.

Crysali 04.07.2017, 14:37

Danke, das sieht auch sehr interessant aus, ich werde mir das mal genau anschauen, das könnte sich für mich lohnen, die Vorteile eines R-Baumes zu haben.

0
GustavAT 07.07.2017, 14:54
@Crysali

Du musst jedenfalls abwiegen, in wie fern es sich auszahlt, einen R-Baum zu verwenden. Bei nur 100 Punkte ist der vielleicht ein Overkill, da die Suche in z.B. einer linearen Liste nicht wesentlich langsamer ist. Bei mehreren Millionen Objekte ist ein R-Baum aber schon ein enormer Performance-Gewinn (spreche da aus Erfahrung) 

0

Was möchtest Du wissen?