[ALG] Icon selectie m.b.v. keyboard

[Tjoekbezoer]

Dag allen,

ik zit met een interface probleem. Ik werk aan een applicatie die items weergeeft in google maps. Aangezien het er nogal wat zijn wil ik ze graag o.a. met het toetsenbord kunnen selecteren. Een goede analogie zou zijn het met het toetsenbord selecteren van iconen op de desktop als die niet op 'lock to grid' staat. Google is verrassend stil als het aankomt op zoektermen waarin een combinatie van 'icons', 'selection' en 'algorithm' voorkomt. Hopelijk hebben jullie tips...



In de afbeelding een situatie: de rode punt is het startpunt. De gebruiker drukt op pijl omhoog (op zijn keyboard). Ik probeer nu een goed algorithme te ontwerpen dat zo vaak mogelijk een logische keuze maakt in de selectie van het volgende punt.

In dit voorbeeld lijkt punt 1 mij de meest logische keuze, aangezien die in rechte lijn ligt met het startpunt. Maar wat als punt 2 niet zoveel naar rechts had gelegen, en hij *bijna* in rechte lijn met rood had gelegen? Dan was punt 2 waarschijnlijk logischer geweest om te selecteren. En wat te doen als punt 1 er helemaal niet geweest zou zijn? You get the point (pun intended )

Wat mij te binnen schiet is een combinatie van richtingscoëfficient en afstand, maar ik zie nog niet zo snel een uitwerking hiervan voor me. Hebben jullie goede ideeën?

[H!GHGuY]

Neem X- en Y-as, roteer 45° rondom huidig punt. Bij het indrukken van de pijl, zoek je in het juiste kwadrant naar het dichtstgelegen punt.

Lijkt mij de eenvoudigste oplossing.

[Tjoekbezoer]

Bedankt voor het meedenken highguy, maar het is inderdaad een erg eenvoudige aanpak. Ik ben op zoek naar de aanpak die het beste resultaat levert

Als ik me niet vergis zou op jouw manier in het voorbeeld hierboven punt 3 geselecteerd worden, terwijl ik dat persoonlijk de minst logische vind.

Om mijn vraag nog verder te verduidelijken; ik loop een beetje stuk op het zoeken naar de juiste algorithmes om te gebruiken/combineren om dit probleem te tackelen. Ik hoop uit mijn vraag niet per sé een kant-en-klare oplossing te krijgen (al is dat natuurlijk mooi), meer een goede richting om verder te kunnen zoeken.

Wat voor (soort) algorithmes zijn nuttig in dit verband?

[H!GHGuY]

Let op met het zoeken naar moeilijke methodes. Als je een slechte methode kiest kan het gebeuren dat een user bepaalde punten nooit kan kiezen. Denk aan een repetitief patroon van:

code:

*-----*
|\   /|
|  *  |
|/   \|
*-----*

Je zal nooit of te nimmer in het middelste punt komen.

Ik vermoed dat je mogelijk wel iets kan met delauney triangulatie:
Wikipedia: Delaunay triangulation

Eens je deze hebt moet je elk punt overlopen en verbindingen schrappen tot je er vier over hebt, met 1 voor elke richting. Op deze manier heb je bovenstaand probleem niet, maar kan je afhankelijk van selectie keuzes hebben die iets minder intuitief lijken.

edit:
Misschien beter nog is om selectie met een gerichte multi-graaf te doen waarbij je voor elk punt 4 (of 2/3?) inkomende en 4 uitgaande connecties vereist, hoewel het pad heen niet tegelijk het pad terug hoeft te zijn.
Enkele handige punten dan:
- behandel punten van buiten naar binnen met het naïeve algoritme: neem het punt waarvan de hoek tov de richting zo klein mogelijk is
- fix daarna punten die te weinig inkomende connecties hebben.

edit2:
als je het implementeert en het wordt een monstersuccess zal ik wel een patent moeten nemen, dat versta je toch

[ Voor 28% gewijzigd door H!GHGuY op 15-10-2011 11:56 ]

[Tjoekbezoer]

Het niet kunnen selecteren van punten zat ik ook al mee. Op de macintosh kan dit bijvoorbeeld voor komen als de desktop iconen gridloos zijn gerangschikt.

DT ziet er veelbelovend uit! Wellichtdat deze aanpak performance problemen gaat opleveren met een weergave van gemiddeld 200 iconen en het feit dat het geheel in JavaScript geïmplementeerd moet worden, maar hier ga ik eens mee stoeien. Aangezien de punten statisch zijn is het wellicht de moeite dit vooraf uit te rekenen, op te slaan en in te laden met de iconen tijdens weergave.

@edit:
Het is iig tijdstechnisch interessanter, aangezien DT uitzoeken en implementeren waarschijnlijk wat meer tijd kost. Wel leuk om te proberen in m'n vrije tijd overigens

Met de multi-graaf zit ik nog wel met het dilemma van welk punt het beste geselecteerd kan worden (korte afstand heeft soms voorkeur boven hoek, soms niet). Met een DT lijkt dit probleem opgelost te worden.

Helemaal perfect zal het nooit zijn, aangezien het verwachte selectiegedrag per gebruiker kan verschillen. Niet iedereen vindt alles op dezelfde manier logisch...

@edit2:
Vanzelfsprekend. Na mijn eerste miljoen neem ik contact met je op

[ Voor 38% gewijzigd door Tjoekbezoer op 15-10-2011 12:49 ]