[C# / ALG] Comparen van 2D coordinaten

[Not Pingu]

In .NET heb je de IComparable interface, die een method CompareTo(object) implementeert. Het integer resultaat hiervan geeft aan of het opgegeven object minder (negatief getal), gelijk aan (nul) of groter (positief getal) is dan de parent van de method. De hoogte van het positieve of negatieve getal geeft aan hoeveel kleiner/groter het object is.

Als je online kijkt naar voorbeeldimplementaties van CompareTo, dan wordt altijd 1 veld (bijv. achternaam, ID, leeftijd) betrokken bij de vergelijking.

Echter werk ik voor het testen van pathfinding algorithmen met een 2D coordinatenstelsel. Hierin wil ik 2 instances van het type Coord2D met elkaar kunnen vergelijken:

(code is versimpeld voor het leesgemak, aub niet letten op access modifiers en de argument type van CompareTo)

C#:

struct Coord2D : IComparable
{
  int X;
  int Y;

  int CompareTo(Coord2D comparecoord)
  {
    return (X.CompareTo(comparecoord.X) + Y.CompareTo(comparecoord.Y))
  }
}

Zoals je al snapt kan dit false positives geven, want een vergelijking tussen (2, 10) en (6, 6) heeft 0 als uitkomst.

Hoe kan ik dit oplossen? Kan je in een coordinatenstelsel spreken van een gekwantificeerd groter dan/kleiner dan, of is er alleen maar gelijk/ongelijk?

[windancer]

Wiskundig gezien is het te bewijzen dat zo'n vergelijking niet bestaat. Het beste wat je kunt doen
is gelijk/ongelijk.

Not Pingu schreef op zaterdag 12 augustus 2006 @ 23:59:
In .NET heb je de IComparable interface, die een method CompareTo(object) implementeert. Het integer resultaat hiervan geeft aan of het opgegeven object minder (negatief getal), gelijk aan (nul) of groter (positief getal) is dan de parent van de method. De hoogte van het positieve of negatieve getal geeft aan hoeveel kleiner/groter het object is.

Als je online kijkt naar voorbeeldimplementaties van CompareTo, dan wordt altijd 1 veld (bijv. achternaam, ID, leeftijd) betrokken bij de vergelijking.

Echter werk ik voor het testen van pathfinding algorithmen met een 2D coordinatenstelsel. Hierin wil ik 2 instances van het type Coord2D met elkaar kunnen vergelijken:

(code is versimpeld voor het leesgemak, aub niet letten op access modifiers en de argument type van CompareTo)

C#:

struct Coord2D : IComparable
{
  int X;
  int Y;

  int CompareTo(Coord2D comparecoord)
  {
    return (X.CompareTo(comparecoord.X) + Y.CompareTo(comparecoord.Y))
  }
}

Zoals je al snapt kan dit false positives geven, want een vergelijking tussen (2, 10) en (6, 6) heeft 0 als uitkomst.

Hoe kan ik dit oplossen? Kan je in een coordinatenstelsel spreken van een gekwantificeerd groter dan/kleiner dan, of is er alleen maar gelijk/ongelijk?

[whoami]

Waarom zou je hier een IComparable interface implementeren ? Waarom zou je 2 coördinaten met elkaar willen gaan vergelijken ? Ik heb eigenlijk nog nooit gezien dat coordinaten met elkaar vergeleken werden, in de zin van (X, Y) is groter of kleiner dan (X2, Y2)...
windancer heeft imho gelijk als hij zegt dat je je beter beperkt tot gelijk/niet gelijk, en hiervoor heb je IComparable helemaal niet nodig, de Equals en GetHashCode method overriden is hier imho voldoende.

[Coca-Cola]

Wat wil je precies bereiken? Als je wilt weten hoe veel 'groter' een 2d coordinaat is ten opzichte van een ander, wil je dan niet gewoon de afstand weten? Het lijkt me echter niet heel netjes om daar IComparable voor te gebruiken

[prototype]

Ik denk dat iedereen hier nu zit (ik iig wel ) met wat jij verstaat onder het 'groter', 'gelijk' of 'kleiner' zijn van een coordinaat met respect tot een ander coordinaat. Misschien kun je dat verduidelijken, ipv verhullend iets aandragen dat meteen met een bepaalde techniek volgens jou gedaan moet worden; je weet maar nooit of het wel echt een geschikte methode is, en als je de reacties hierboven leest moet je denk ik nu wel een beetje een vermoeden daarover hebben

[EfBe]

Not Pingu schreef op zaterdag 12 augustus 2006 @ 23:59:
In .NET heb je de IComparable interface, die een method CompareTo(object) implementeert. Het integer resultaat hiervan geeft aan of het opgegeven object minder (negatief getal), gelijk aan (nul) of groter (positief getal) is dan de parent van de method. De hoogte van het positieve of negatieve getal geeft aan hoeveel kleiner/groter het object is.

Nee, IComparable.CompareTo is niet zo gedefinieerd. De method kan 3 soorten values teruggeven:
int x = A.CompareTo(B):
x<0 : A < B
x==0: A == B
x>0: A > B

That's it. En dan nu de hamvraag: wat houdt A > B in? Dat is per type verschillend. In het geval van coordinaten is dat dus niet te zeggen. Het komt er dan dus op neer dat je IComparable.CompareTo alleen kunt gebruiken voor het testen of 2 coordinaten hetzelfde zijn of niet, maar niet voor bv sortalgo's.

[Not Pingu]

EfBe schreef op zondag 13 augustus 2006 @ 11:41:
Nee, IComparable.CompareTo is niet zo gedefinieerd. De method kan 3 soorten values teruggeven:
int x = A.CompareTo(B):
x<0 : A < B
x==0: A == B
x>0: A > B

Ja, dat zeg ik toch?

Het komt er dan dus op neer dat je IComparable.CompareTo alleen kunt gebruiken voor het testen of 2 coordinaten hetzelfde zijn of niet, maar niet voor bv sortalgo's.

De reden waarvoor ik 2 coordinaten wou vergelijken was idd met het oog op sorting in collecties en key/value collecties (bijv. een collectie gouden muntjes, waar je met Coord2D als key snel kan opzoeken of op een bepaald coordinaat een muntje ligt).
Maar ook het gebruik van operator overloading zodat ik makkelijker met coordinaten kan werken
In System.Drawing heb je de struct Point die in principe doet wat ik wil, maar geen IComparable implementeert en dus niet als key kan worden gebruikt in bijv. een SortedList<>..

Maar nu ik er eens over nadenk is sorting op waarde ook niet te doen met coordinaten. Ik ga het nu gewoon als gelijk/ongelijk implementeren.

Thx all.

[Verwijderd]

Wat je wilt is heel goed mogelijk, en wel op meerdere manieren:

1) Wanneer je weet dat X/Y zich binnen een bepaald bereik bevinden, bijvoorbeeld 0-1000, dan kun je een waarde V = X + Y * 1000 berekenen en daarmee vergelijken:

C++:

int Compare(const Point& p1, const Point& p2)
{
    const int V1 = p1.X + p1.Y * 1000;
    const int V2 = p2.X + p2.Y * 1000;
    const int V = V2 - V1;
    return V;
}

2) Wanneer de waardes zich niet binnen een bepaald bereik bevinden kun je X of Y een hogere 'prioriteit' geven en met wat meer compares het zelfde berijken:

C++:

int operator()(const Vector3& v1, const Vector3& v2) const
{

    if (v1.x < v2.x)
        return -1;
    if (v1.x > v2.x)
        return +1;

    if (v1.y < v2.y)
        return -1;
    if (v1.y > v2.y)
        return +1;

    if (v1.z < v2.z)
        return -1;
    if (v1.z > v2.z)
        return +1;

    return 0; // Gelijk.

}

3) De derde methode is om de binaire waarde als integer te interpreteren, bv dmv een union:

C++:

union Point
{
    struct
    {
        int16 X;
        int16 Y;
    };
    int32 V;
}

int Compare(const Point& p1, const Point& p2)
{

    int V = p2.V - p1.V;

    return V;

}

[.oisyn]

1) en 3) zijn in feite hetzelfde als 2), en het voordeel van 2) is dat het met alle types werkt, je geen limieten op hoeft te leggen en geen vage unions hoeft te definieren (in C# heb je overigens geen unions)

[ Voor 19% gewijzigd door .oisyn op 13-08-2006 21:13 ]

[Not Pingu]

Verwijderd schreef op zondag 13 augustus 2006 @ 18:46:
Wat je wilt is heel goed mogelijk, en wel op meerdere manieren:

Maar dat komt in alle gevallen neer op een berekening van de afstand. Een coordinaat geeft dan in vergelijking met meerdere coordinaten dezelfde uitkomst waardoor dit niet in een CompareTo functie thuishoort, meer als aparte functie Coord2D.DistanceTo(Coord2D coord) oid. Sorting is dan sowieso niet meer mogelijk en je kunt dan imho beter niet de indruk wekken dat het wel kan.

[Janoz]

Dat is zeker geen berekening van de afstand. Het enige dat M303 doet is enkel het Y coordinaat gebruiken om te sorteren. Bij gelijke Y waarden wordt vervolgens op X gesorteerd. Een andere manier bestaat gewoon niet zolang je de standaard comparable manier gebruikt. Dit is wiskundig aan te tonen en is het gevolg van het terug brengen van een 2D waarde naar een 1D bereik.

Als je het echt belangrijk vindt om snel in een 2D grid te zoeken zou je kunnen kijken naar zoek algoritmen voor 2D grids. Hierbij valt bijvoorbeeld aan een Quadtree te denken. De gekozen oplossing is echter heel erg afhankelijk van de daadwerkelijke toepassing.