[C#] geometrie / topologie validatie

[GateKeaper]

De null-situatie

Er zijn twee lijsten, één voor punten en één voor lijnen. Een lijn is niets meer dan een verzameling van punten.

C#:

var points = new List<Point>();
var lines = new List<Line>();

Het Point object:

C#:

public class Point
{
   public double X { get; set; }
   public double Y { get; set; }
}

Het Line object

C#:

public class Line
{
    public Point[] Points { get; set; }
}

Voorwaarden

De eisen aan de constructie zijn eenvoudig. Ieder eerste en laatste punt van een lijn ligt op een punt die geen deel uitmaakt van een (andere) lijn constructie. In code; een lijn is geldig als hij voldoet aan de volgende twee voorwaarden:

C#:

points.Any(p => p.X.Equals(line.Points.First().X) && p.Y.Equals(line.Points.First().Y)) 
points.Any(p => p.X.Equals(line.Points.Last().X) && p.Y.Equals(line.Points.Last().Y))

Validatie

Een lijn is dan ook vrij eenvoudig te valideren. Een simpel foreach loopje en een LINQ query doen wonderen;

C#:

foreach (var line in lines)
{
    if (!points.Any(p => p.X.Equals(line.Points.First().X) && p.Y.Equals(line.Points.First().Y)))
    {
        // eerste vertexpunt ligt niet op een punt object
    }


    if (!points.Any(p => p.X.Equals(line.Points.Last().X) && p.Y.Equals(line.Points.Last().Y)))
    {
        // laatste vertextpunt ligt niet op een punt object
    }
}

Het probleem

Zoals je wellicht inmiddels al vermoed, kan dit proces bij grotere lijsten met punten en lijnen behoorlijk in tijd oplopen. De uitdaging is hier dan ook om dit proces te versnellen.

Mogelijke oplossing

Een oplossing die ik zelf al bedacht heb ik om de puntenlijst in delen op te splitsen. Coördinaten lopen uiteen van 155.000,000 tot 300.000,000 meter in de X en van 463.000,000 tot 600.000,000 meter in de Y.

Mijn idee was om de puntenlijst op te splitsen in stukken van 50.000 meter, vervolgens te kijken in welke range het lijn object valt, en dan nog enkel in de juiste puntenlijst kijken met behulp van bovenstaande validatie methode.

Mijn vraag

Aangezien ik er al aardig over nagedacht heb, maar hierdoor de kans heb dat ik vast zit in mijn eigen denkwijze, aan jullie de vraag of jullie een andere / betere methode hebben om mijn lijnconstructies te valideren.

[Grijze Vos]

Allereerst zou ik denken dat een Line een Tuple is van punten, geen verzameling. Dat noemt men doorgaans een Multiline oid.

Om dit probleem efficient op te lossen moet je je datastructuur aanpassen, zodat de validatie makkelijker gaat. Sla je punten set op in een of andere tree structure. Wellicht een quad tree. Op die manier kun je heel snel inzoomen op de punten waar het om gaat.

[GateKeaper]

Ik ben bekend met de quadtrees. Maar hoe dit in code verwerkt moet worden?

Dat is dan toch zoals mijn voorstel? Opsplitsen in delen, zeg vlakken van 50.000 meter in het vierkant. Kijken in welk vlak de lijn valt, en de bijhorende collectie controleren op relevante items?

*edit, Tuple / collectie is vrijwel hetzelfde. Jij doelt volgens mij op Multipoint (niet multiline) en dat is het inderdaad niet. Van mij mag je het zien als een Tuple :-) Eén lijn die bestaat uit meerdere verbonden punten. Al zie je in de collectie de verbinding niet. Maar Point[1] is verbonden met Point[0]. Al is dit niet relevant voor de geometrie validatie.

[ Voor 37% gewijzigd door GateKeaper op 12-09-2011 11:50 ]

[Phyxion]

GateKeaper schreef op maandag 12 september 2011 @ 11:48:
Ik ben bekend met de quadtrees. Maar hoe dit in code verwerkt moet worden?

Dat is dan toch zoals mijn voorstel? Opsplitsen in delen, zeg vlakken van 50.000 meter in het vierkant. Kijken in welk vlak de lijn valt, en de bijhorende collectie controleren op relevante items?

*edit, Tuple / collectie is vrijwel hetzelfde. Jij doelt volgens mij op Multipoint (niet multiline) en dat is het inderdaad niet. Van mij mag je het zien als een Tuple :-) Eén lijn die bestaat uit meerdere verbonden punten. Al zie je in de collectie de verbinding niet. Maar Point\[1] is verbonden met Point\[0]. Al is dit niet relevant voor de geometrie validatie.

Tsja, GoT is natuurlijk niet een ik-vraag-en-krijg-kant-en-klare-code website. Er zijn verschillende manieren die je kan toepassen, ik denk dat je een heel eind gaat komen met een sorting algorithm (Wikipedia: Sorting algorithm) mits je het slim indeelt. Elk algoritme heeft voor en nadelen, de ene kan snel zoeken, de andere snel inserten, het is maar net wat je het meeste nodig hebt (ik neem aan dat je niet alleen insert doet, anders heeft het niet veel nut). Oftewel, met de informatie die wij niet hebben en die jij wel hebt kan je vast een afweging maken. Alle algoritmes op Wikipedia zijn eenvoudig te implementeren in C# in ieder geval

[Janoz]

Ja, het is vergelijkbaar met je voorstel. Echter, je deelt het gebied niet op in vaste blokken, maar pas wanneer een deel te vol wordt splits je het weer in 4 quadranten (en wanneer zo'n nieuw deel weer te vol is splits je die weer op in 4 quadranten).

Voor het testen lijkt het me vervolgens wel handiger om juist alle punten in de quadtree te zetten en vervolgens alle start en eind punten bij langs te gaan om te controleren of er een match is.

[Janoz]

GateKeaper schreef op maandag 12 september 2011 @ 11:48:
*edit, Tuple / collectie is vrijwel hetzelfde. Jij doelt volgens mij op Multipoint (niet multiline) en dat is het inderdaad niet. Van mij mag je het zien als een Tuple :-) Eén lijn die bestaat uit meerdere verbonden punten. Al zie je in de collectie de verbinding niet. Maar Point\[1] is verbonden met Point\[0]. Al is dit niet relevant voor de geometrie validatie.

Euhm, wacht even. Dit is wel een redelijk belangrijk punt. Waar het om gaat is of we hier te maken hebben met een lijn, of met een pad. Als jij het over meerdere punten hebt dan denk ik ook aan meer dan 2 punten. En met meer dan 2 punten heb je enkel in uitzonderlijke gevallen nog slechts 1 lijn die daar doorheen gaat.

Kortom, hebben we het hier over een rechte lijn, of over een pad dat door de verschillende punten (>2) loopt?

[GateKeaper]

Phyxion schreef op maandag 12 september 2011 @ 11:54:
[...]

Tsja, GoT is natuurlijk niet een ik-vraag-en-krijg-kant-en-klare-code website....

Ik vraag ook zeker niet om een kant en klare oplossing. Maar als mensen willen meedenken en mij op pad kunnen helpen dan ben ik ze zeer dankbaar. Ik wil je dan ook bedanken voor je link. Deze zal ik straks zeker even goed doornemen!

Inserten hoef ik niet, puur validatie op bestaande objecten.

Janoz schreef op maandag 12 september 2011 @ 11:58:
[...]
Voor het testen lijkt het me vervolgens wel handiger om juist alle punten in de quadtree te zetten en vervolgens alle start en eind punten bij langs te gaan om te controleren of er een match is.

Dan ben ik toch weer terug op een aantal vooraf gevulde collecties. Wellicht alleen niet met vaste ranges in meters, maar vaste objectaantallen (met tollerantie).

Janoz schreef op maandag 12 september 2011 @ 12:01:
[...]

Euhm, wacht even. Dit is wel een redelijk belangrijk punt. Waar het om gaat is of we hier te maken hebben met een lijn, of met een pad. Als jij het over meerdere punten hebt dan denk ik ook aan meer dan 2 punten. En met meer dan 2 punten heb je enkel in uitzonderlijke gevallen nog slechts 1 lijn die daar doorheen gaat.

Kortom, hebben we het hier over een rechte lijn, of over een pad dat door de verschillende punten (>2) loopt?

Ja en nee, in mijn geval maakt het niets uit. Ik hoef alleen maar zeker te weten dat het startpunt en eindpunt op een statisch punt (uit de IList<Point>) valt. De tussenpunten zijn voor mij niet van belang.

Er wordt in mijn geval dus niet gecontroleerd of een lijn met een lijn intersect, maar of het beginpunt (line.Points.First()) en eindpunt (line.Points.Last()) van de lijn ( / path / multiline / polyline) exact op een statisch punt (Point) vallen. Denk bij lijnen aan stroomkabels en bij punten aan straatlantaarns. De kabel begint in de stroomkast en eindigt in de straatlantaarns. Waar hij knikt / buigt (tussenpunten) maakt mij niet uit.

[GateKeaper]

Ik heb even wat meer onderzoek gedaan naar de quadtrees, en denk dat dit zeker haalbaar is.

Het wordt eerst even uitzoeken tot hoeveel objecten de performance acceptabel is en daarna de punten in een quadtree laden.

Wel lijkt het mij het beste om alle punten (zoals Janoz ook zei) vooraf in te laden en de validatie op een reeds gevulde boom te draaien en de boom niet dynamisch te laden.

Mensen bedankt voor het meedenken! Ik kende het begrip Quadtree al, maar ben er nooit op gekomen als oplossing voor mijn probleem (dom dom dom).

[Verwijderd]

Als je van je lijst met lijnen nou eens een tweede lijst met punten maakt, dan is je probleem gereduceerd to het vinden van een enkele overeenkomst in twee lijsten met punten. Als je die eerst sorteert O(n log n) kun je daarna in lineaire tijd erdoor heen lopen om overeenkomsten te zoeken.

[Phyxion]

GateKeaper schreef op maandag 12 september 2011 @ 12:52:
Ik heb even wat meer onderzoek gedaan naar de quadtrees, en denk dat dit zeker haalbaar is.

Het wordt eerst even uitzoeken tot hoeveel objecten de performance acceptabel is en daarna de punten in een quadtree laden.

Wel lijkt het mij het beste om alle punten (zoals Janoz ook zei) vooraf in te laden en de validatie op een reeds gevulde boom te draaien en de boom niet dynamisch te laden.

Mensen bedankt voor het meedenken! Ik kende het begrip Quadtree al, maar ben er nooit op gekomen als oplossing voor mijn probleem (dom dom dom).

Het lijkt mij handig om eerst uit te zoeken wat waarschijnlijk de meeste performance winst op gaat leveren in plaats van iets te proberen, veel tijd erin te steken, en er vervolgens achter te komen dat er een betere oplossing bestaat.

Wat wil je nou precies? Je hebt al een kant en klare lijst aan punten en je wilt alleen maar valideren (en dus alle punten doorlopen zoals je nu doet) zonder er verder wat mee te doen? In dat geval kan je het beste een algoritme nemen die een snelle lookup/select heeft.

[GateKeaper]

Verwijderd schreef op maandag 12 september 2011 @ 12:53:
Als je van je lijst met lijnen nou eens een tweede lijst met punten maakt, dan is je probleem gereduceerd to het vinden van een enkele overeenkomst in twee lijsten met punten. Als je die eerst sorteert O(n log n) kun je daarna in lineaire tijd erdoor heen lopen om overeenkomsten te zoeken.

Geen optie, ik moet de lijnen op begin en eindpunt controleren. Indien één van deze twee niet correct is moet ik ergens in loggen dat die lijn afwijkt van zijn gewenste gedrag. Naast coördinaten heeft de lijn attributen die ik nodig heb tijdens het loggen. De lijnen moeten dus intact blijven.

Phyxion schreef op maandag 12 september 2011 @ 13:09:
[...]
in plaats van iets te proberen, veel tijd erin te steken, en er vervolgens achter te komen dat er een betere oplossing bestaat.

Niet lullig bedoeld, maar van jouw krijg ik ook geen hoogte. Eerst zeg je me dat ik zelf onderzoek moet doen en dat GOT "niet een ik-vraag-en-krijg-kant-en-klare-code website" is. En nu moet ik weer niet zomaar dingen proberen.

Niet verkeerd bedoeld hoor, maar ik ben iemand die zeker niet te lui is om zelf onderzoek te doen. Ik plaats hier niet zomaar een vraag wanneer die me te binnen schiet. Zoals je aan mijn topicstart ook kunt zien maak ik er werk van, en leg de situatie waarin ik verkeer zo duidelijk mogelijk uit. Niet het gemiddelde ik-heb-een-vraag-en-wil-de-oplossing-topic.

Tevens zei je ook heel duidelijk: "Alle algoritmes op Wikipedia zijn eenvoudig te implementeren in C# in ieder geval" in dat geval kan er nooit veel tijd verloren gaan toch? Naar mijn idee kan "eenvoudig te implementeren" nooit veel tijd kosten.

Phyxion schreef op maandag 12 september 2011 @ 13:09:Wat wil je nou precies? Je hebt al een kant en klare lijst aan punten en je wilt alleen maar valideren (en dus alle punten doorlopen zoals je nu doet) zonder er verder wat mee te doen? In dat geval kan je het beste een algoritme nemen die een snelle lookup/select heeft.

Ik heb inderdaad al een kant en klare lijst (al gegenereerd / geladen) en ik wil inderdaad alleen maar valideren. Natuurlijk gebeurd er wel wat mee (op de plaatsen van de comments in de loop). Wat er mee gebeurd is echter niet relevant voor mijn probleem stelling hier zoals ik deze in de startpost omschreven heb.

Het probleem dat ik heb is dat het doorlopen van alle punten op iedere lijn te veel tijd in beslag neemt. De oplossing die door Grijze Vos en Janoz wordt aangedragen (gebruik Quadtree) is dus zo gek nog niet.

Wat er nu gebeurd is dat als ik een lijst heb met 60.000 lijnen en een lijst met 140.000 punten, dat er 120.000 (2x 60.000) keer wordt gekeken of één van de 140.000 punten toevallig dezelfde coördinaten heeft als het betreffende punt op de lijn (start of eindpunt). Dit moet sneller / efficiënter kunnen!

Naar mijn idee hebben Grijze Vos en Janoz hier dan ook gelijk, en is Quadtree hier een ideale methode voor. Ik moet dus alleen even uitzoeken hoe ik op efficiënte wijze een Quadtree in C# kan bouwen. Maar ik heb er zin in om deze koe bij de horens te vatten, dus dat gaat vast en zeker goed komen!

[Verwijderd]

Je kunt natuurlijk prima je punten laten verwijzen naar de lijn waar ze origineel deel van uitmaakten. Ik zeg niet dat een Quadtree geen goede oplossing is, alleen denk ik dat het meer is dan nodig. Iets als dit zou al moeten werken:

code:

Sorteer lijst met punten L1 (eerst naar x-coordinaat, bij gelijke x dan naar y)
Maak lijst met punten L2 die onderdeel zijn van lijnen, elk punt heeft een pointer terug naar de originele lijst.
Sorteer lijst L2
i = 0
j = 0
while i < len(L1) and j < len(L2):
  if L1[i] == L2[j]:
    //Probleem met lijst waarvan L2[j] deel van uitmaakt.
  else if L1[i] < L2[j]:
    i++
  else: // L2[j] < L1[i]
    j++

[R4gnax]

GateKeaper schreef op maandag 12 september 2011 @ 11:12:
Voorwaarden

De eisen aan de constructie zijn eenvoudig. Ieder eerste en laatste punt van een lijn ligt op een punt die geen deel uitmaakt van een (andere) lijn constructie. In code; een lijn is geldig als hij voldoet aan de volgende twee voorwaarden:

C#:

points.Any(p => p.X.Equals(line.Points.First().X) && p.Y.Equals(line.Points.First().Y)) 
points.Any(p => p.X.Equals(line.Points.Last().X) && p.Y.Equals(line.Points.Last().Y))

Inderdaad wat Yexo zegt:

Sorteer je lijst losse punten op X-coordinaat, gevolgd door Y-coordinaat. Doe hetzelfde voor de beginpunten en eindpunten van de lijnen. (Zorg er voor dat je in deze lijst een referentie houdt naar de lijn waar het begin- danwel eindpunt bij hoort, als je meta-informatie uit lijnen nog nodig hebt om incorrecte lijnen te rapporteren.)

Vervolgens loop je door de lijst van beginpunten van de lijnen heen en match je deze met de lijst losse punten. Aangezien alles gesorteerd is, is de amortized cost laag te houden: Met elk gematched beginpunt wordt de lijst die je nog moet doorlopen voor de overige punten kleiner. Als ik me goed herinner is dat in totaal een O(n log n) kost. Hierna herhaal je deze match nog een keer voor de lijst eindpunten van lijnen.

De totaal kosten voor je algorithme zijn dan 3 * O(n log n) voor het sorteren v/d lijsten en 2 * O(n log n) voor het matchen. Oftewel; gewoon een O(n log n) runtime.

Voor extreem grote lijsten punten en lijnen die niet in RAM passen is het ook mogelijk om deze met IO-efficiente algoritmes te sorteren en doorzoeken.

[Janoz]

R4gnax schreef op dinsdag 13 september 2011 @ 09:13:
[...]


Inderdaad wat Yexo zegt:

Sorteer je lijst losse punten op X-coordinaat, gevolgd door Y-coordinaat. Doe hetzelfde voor de beginpunten en eindpunten van de lijnen. (Zorg er voor dat je in deze lijst een referentie houdt naar de lijn waar het begin- danwel eindpunt bij hoort, als je meta-informatie uit lijnen nog nodig hebt om incorrecte lijnen te rapporteren.)

Vervolgens loop je door de lijst van beginpunten van de lijnen heen en match je deze met de lijst losse punten. Aangezien alles gesorteerd is, is de amortized cost laag te houden: Met elk gematched beginpunt wordt de lijst die je nog moet doorlopen voor de overige punten kleiner. Als ik me goed herinner is dat in totaal een O(n log n) kost. Hierna herhaal je deze match nog een keer voor de lijst eindpunten van lijnen.

De totaal kosten voor je algorithme zijn dan 3 * O(n log n) voor het sorteren v/d lijsten en 2 * O(n log n) voor het matchen. Oftewel; gewoon een O(n log n) runtime.

Voor extreem grote lijsten punten en lijnen die niet in RAM passen is het ook mogelijk om deze met IO-efficiente algoritmes te sorteren en doorzoeken.

Bij N punten en M lijnen is dat algoritme afaik toch echt O N*M. De quadtree oplossing daarentegen is O (M + N) log N.

[Verwijderd]

Janoz schreef op dinsdag 13 september 2011 @ 09:28:
[...]

Bij N punten en M lijnen is dat algoritme afaik toch echt O N*M. De quadtree oplossing daarentegen is O (M + N) log N.

Nee hoor, R4gnax heeft gelijk. Het sorteren is het punt wat het meeste tijd kost, en dat kan in O(n log n) en O(m log m). De while loop die ik daarna beschreven heb kost maar O(N + M).

[Zoijar]

Je kan ook al je N punten hashen en dan 2*M lookups doen. Ammortized O(N+2M). Maar daar hangt veel van je keuze van hash parameters af. Het is wel heel simpel te implementeren. Zo deed ik een soortgelijk probleem in ieder geval met 100.000 urls, dat ging prima.

(in C# iets als foreach var p in points {hash.add(p);} foreach (var line in lines) {if !hash.contains(line.first) {}}. Hoef je verder niks zelf te implementeren of over na te denken)

In je hash kan je ook nog een parameter zetten of het punt al een keer gebruikt is, want je had het ook nog over unieke punten in je startpost.

(andere optie is het in PostGis dumpen en query draaien )

[ Voor 63% gewijzigd door Zoijar op 13-09-2011 12:55 ]

[Janoz]

Ah, ik had inderdaad even gemist dat beide lijstjes met punten gesorteerd werden.

[Verwijderd]

Zoijar schreef op dinsdag 13 september 2011 @ 12:41:
Je kan ook al je N punten hashen en dan 2*M lookups doen. Ammortized O(N+2M). Maar daar hangt veel van je keuze van hash parameters af. Het is wel heel simpel te implementeren. Zo deed ik een soortgelijk probleem in ieder geval met 100.000 urls, dat ging prima.

Hashen lijkt me lastig worden in dit geval, omdat het om doubles gaat. Tenzij je zeker weet dat je coordinaten exact gelijk zijn en niet 1e-10 van elkaar verschillen gaat dat problemen opleveren. Als dat geen probleem is dan is dit waarschijnlijk de snelste oplossing.

Janoz schreef op dinsdag 13 september 2011 @ 12:48:
Ah, ik had inderdaad even gemist dat beide lijstjes met punten gesorteerd werden.

Ook als je alleen je lijst met punten sorteert en niks doet met de lijnen gaat het al aardig snel. Je komt dan (binary search om te kijken of je een punt al hebt) op een running time van O(M log nN

[Zoijar]

Verwijderd schreef op dinsdag 13 september 2011 @ 13:49:
Hashen lijkt me lastig worden in dit geval, omdat het om doubles gaat. Tenzij je zeker weet dat je coordinaten exact gelijk zijn en niet 1e-10 van elkaar verschillen gaat dat problemen opleveren. Als dat geen probleem is dan is dit waarschijnlijk de snelste oplossing.

Ja daar ging ik wel even vanuit. Als je ranges om punten moet zoeken wordt het sowieso een stuk lastiger. Dan werkt sorteren namelijk ook niet.

Dan moet/kan je nearest neighbour search in een kd-tree doen. (en dan snel en goed zo'n boom bouwen. Dat is wel te doen, maar niet zo simpel zo blijkt uit de raytrace literatuur )

[ Voor 9% gewijzigd door Zoijar op 13-09-2011 13:56 ]

[GateKeaper]

Verwijderd schreef op dinsdag 13 september 2011 @ 13:49:
[...]
Tenzij je zeker weet dat je coordinaten exact gelijk zijn en niet 1e-10 van elkaar verschillen gaat dat problemen opleveren. Als dat geen probleem is dan is dit waarschijnlijk de snelste oplossing.
[...]

Tegen dat probleem ben ik al aangelopen, tijdens het vullen van de lijsten rond ik de coördinaten af op milimeters

Ik zal de gesorteerde lijst methode eens nader onderzoeken. Lijkt interessant te zijn. Wel is het mogelijk dat er twee lijnen zijn die op het zelfde punt eindigen / beginnen. Dus ik moet even kijken hoe de methode daarmee om gaat.

De hashing methode begrijp ik niet helemaal. Die doet uiteindelijk toch precies hetzelfde als mijn huidige situatie? Voor ieder punt moet hij kijken of de hash aanwezig is in een array met ...... hashes.

[Zoijar]

GateKeaper schreef op dinsdag 13 september 2011 @ 14:02:
De hashing methode begrijp ik niet helemaal. Die doet uiteindelijk toch precies hetzelfde als mijn huidige situatie? Voor ieder punt moet hij kijken of de hash aanwezig is in een array met ...... hashes.

Een hash look-up is gemiddeld gezien te doen in constante tijd, dus niet afhangend van de grootte van je array zoals een "for each".

Stel dat je hash functie de coordinaten optelt (domme hash, maar stel):

Insert je (3,2) op plek #5 en 7,8 op plek #15.

Nu vraag je punt (2,2), is hash #4, kijk je op plek 4 (dat kan in een keer) en die is leeg, dus bestaat niet.
(3,2) hash naar #5, kijk op plek 5, bezet, dus bestaat.

[.oisyn]

Maar (2,3) hasht ook naar #5, maar toch bestaat ie niet. Je zult dus ook de entry zelf nog moeten controleren, en een manier moeten verzinnen om meerdere entries met dezelfde hash op te kunnen slaan (met buckets of dmv probing).

Een andere manier is een bloom filter, maar dan zul je wel veel hash functions moeten verzinnen om de kans op false positives te verkleinen.

[ Voor 24% gewijzigd door .oisyn op 14-09-2011 13:35 ]

[GateKeaper]

Dit klinkt bij mij als (even hier getypt, kan fouten bevatten)

C#:

var points = new List<Point>();
points.Add(new Point { X = 123.09, Y = 125.05, PointID = "PuntNr001" });

// ......

var pointArray = new Dictionary<String, Point>();
foreach (var point in points)
    pointArray.Add(point.X + ";" + point.Y, point); // ipv point een pointer / index

// ......

foreach (var line in lines)
    if(!pointArray.Contains(line.Points.First().X + ";" + line.Points.First().Y)
        // eerste vertexpunt van lijn valt niet op punt object in puntenlijst.

Dit lijkt makkelijk en mooi, maar zoals .oisyn ook zegt, mis ik dan wel de punten met dezelfde coördinaten (dubbele hashes).

Wat dat betreft neig ik meer en meer naar de Quadtree. Doordat ik dan vrij snel een beperkte subset van alle aanwezige punten krijg, heb ik weer volledige vrijheid over de data. Het is misschien wat meer werk om het op te zetten, maar hier krijg ik naar mijn idee wel meer vrijheid voor terug.

[.oisyn]

Ik zou zeker geen Dictionary<String,Point> maken. Overload op je Point gewoon een zinnige GetHashCode(), zodat je een HashSet<Point> kunt gebruiken.

[Zoijar]

GateKeaper schreef op woensdag 14 september 2011 @ 15:51:
Dit lijkt makkelijk en mooi, maar zoals .oisyn ook zegt, mis ik dan wel de punten met dezelfde coördinaten (dubbele hashes).

Het kan dat ik me heel erg vergis, maar voor zover ik weet regelt je hashtable class dat allemaal zelf. Ook al is er een hash collission. Ik snap het probleem niet (?) (als er een hash collission is slaat hij ze intern allebei op in een gesorteerde lijst oid. Daarom is het ook niet echt O(1) want soms moet je alsnog zoeken door een (kleine) lijst.)

(niet dat dit de meest geweldige oplossing is hoor, maar het is snel te implementeren, duidelijk, niet complex en behoorlijk efficient)

Je zal in C# toch wel een pair/tuple class hebben die zelf de hash berekening regelt?

[ Voor 33% gewijzigd door Zoijar op 14-09-2011 19:01 ]