[ALG]Waarden in een map interpoleren (pathfinding)

[Verwijderd]

Ik zit er nu al een tijd over te denken maar kan nog geen ideale strategie bedenken (als die er al is) voor het volgende probleem:

In het volgende plaatje is een map te zien met bekende en onbekende waarden (een versimpelde versie). Zoals je ziet zitten er lijnen in die een bepaald gebied afbakenen. Verder is in de hoekpunten van de map altijd een waarde aanwezig (al dan niet van een lijn). Ook kunnen er er lijnen een gebied omtrekken maar ook daarin moet minimaal 1 hoogste/laagste waarde in gezet worden.



Mijn probleem is nu hoe ik nu de ontbrekende data kan invullen op een zo realistisch mogelijk wijze. Het algoritme hoeft niet snel te zijn want de waarden komen in een database waar het echte programma mee kan verder werken.

Een methode die ik bedacht heb is om het volgende te doen:
1-links bovenaan te beginnen (in welke situatie ook)
2-scan verder naar links tot het eerste onbekende vakje
3-pak de bekende waarde van het vorige vakje
4-scan vanaf het vakje met onbekende waarde naar de dichtsbijzijnde vakje met ongelijke waarde (in het geval van gelijke afstanden wordt de laagste gekozen)
5-bereken onbekende vakje met: (hoogste bekende vakje - andere bekende vakje) : aantal stappen = x
Als de start positie hoger is dan: start - (x * aantal stappen) of anders start + x
6-scan verder naar links en herhaal
7-bij het einde van de rij ga naar links + 1 rij

Zelf denk ik dat het redelijke resultaten kan geven en dat het ook nog eens betrekkelijk snel kan zijn (al is dat niet het eerste waar ik naar streef).
Dit is een hydrologische situatie -> grondwaterstanden dus de resultaten moeten wel realistisch blijven.

Het scannen naar de dichtsbijzijnde punten kan ik denk ik het beste met het Dijkstra algoritme doen (al moet ik toegeven dat ik alleen nog maar naar deze en A* heb gekeken).

Lijkt jullie deze methode wat of voorzien jullie problemen of beter nog hebben jullie andere ideeën?

Edit:
Kleine wijziging in berekening + in punt 4

[ Voor 5% gewijzigd door Verwijderd op 12-10-2005 00:51 ]

[MrBucket]

Een bekende methode is om gebruik te maken van een zogenaamd Triangulated Irregular Network (TIN). Het idee is dat elk punt waarvan je de waarde weet, een punt (vertex) wordt in de triangulatie, met de hoogte gelijk aan zijn waarde.
Een speciale triangulatie is de zgn. Delaunay triagulatie, waarbij de driehoeken zo gekozen worden dat alle driehoeken zo compact mogelijk zijn (en niet smal en lang). Dit zorgt ervoor dat je interpolatie in de meeste gevallen wel redelijk goed is.
De waarden van de ontbrekende cellen kan je dan bepalen door te kijken in welke driehoek zo'n cel ligt, en vervolgens de hoogte te interpoleren van de drie vertices van die driehoek.

Kijk o.a. eens op http://www.ian-ko.com/res...ted_irregular_network.htm
Demonstratie van hoe een Delaunay triangulatie eruit ziet: http://cage.ugent.be/~dc/alhtml/Delaunay.html
Algoritme om een Delaunay triangulatie te maken: http://www.cs.wustl.edu/~pless/506/l18.html

[ Voor 26% gewijzigd door MrBucket op 12-10-2005 09:28 ]

[Soultaker]

Een Delaunay-triangulatie maken is fucking veel werk (zeker als je het een beetje efficiënt wil doen, maar anders ook).

Kun je niet iets simpels doen waarbij je voor elk punt het gemiddelde neemt van de punten eromheen, gewogen naar de afstand tot het punt?

[MrBucket]

Soultaker schreef op woensdag 12 oktober 2005 @ 18:01:
Een Delaunay-triangulatie maken is fucking veel werk (zeker als je het een beetje efficiënt wil doen, maar anders ook).

Mwoah, 't valt nog wel mee hoor. De link die ik in mijn vorige post gaf, met de edge-flips, is nog redelijk goed te doen.

En anders kan je altijd nog speciale geometrische libraries gebruiken zoals www.cgal.org, daar zit bijv. standaard een Delaunay_triangulation_2 in. Maar als je niet dagelijks bezig bent met geometrische problemen, zal de leercurve voor CGAL denk ik niet opwegen tegen het resultaat, dan wordt het allemaal een beetje overdreven