grafico c ++ non orientato con una direzione [chiusa]

1

Voglio creare un grafico in C ++ che abbia direzioni, con le direzioni non intendo la direzione di un bordo, ma quello che voglio è un grafo non orientato in cui i bordi hanno una direzione verso il vertice successivo, per esempio consideriamo siamo in vertice1

up      = vertex2
right   = vertex3
down    = vertex4
left    = vertex5

Consideriamo le seguenti classi di base

 Class Edge{
    //To save an connection between two vertexes 
    Vertex point1;
    Vertex point2;
 }

 Class Vertex
 {
     string description;
 }

Per questo problema ho trovato alcune soluzioni possibili.

1. Dai ai vertici una mappa con una direzione (enum) e un altro vertice per quella direzione (nullptr se non ci sono spigoli in quella direzione).

svantaggio è che dobbiamo salvare le direzioni su entrambi i vertici o in loop tutti gli altri vertici per vedere se è collegato al vertice corrente.

Pro ? non abbiamo bisogno di bordi.

2. Aggiungendo una variabile all'oggetto Edge che contiene una direzione, possiamo stabilire che la direzione è dal punto 1 al 2, quindi se il valore della direzione è inferiore rispetto alla direzione da point2 a point1 è attivo. Possiamo salvare un elenco con tutti i bordi.

Un'altra importante differenza è che la soluzione 1 salva i bordi nei vertici e la soluzione 2 in una classe che contiene un elenco con bordi.

Contesto

Ciò che è importante, è che voglio essere in grado di impostare la mia posizione su un vertice e spostarmi, quando spostato ho bisogno di ricordare che ho usato la connessione tra i vertici. Con la soluzione 1 posso aggiungere una mappa per i visitatori che ha una direzione enum (uguale al concetto per salvare le direzioni). Con la soluzione 2 potrei aggiungere un bool visitato. Devo salvare la variabile "visitata" perché voglio testare un algoritmo dijksta modificato in base ai bordi visitati.

In breve, come dovrei creare un grafo non orientato in cui i bordi hanno una direzione (direzione come su, giù, sinistra, destra dal vertice corrente).

Che cosa mi consiglieresti di fare?

    
posta Sven van den Boogaart 02.11.2015 - 20:00
fonte

1 risposta

1

Dividi il tuo grafico in aree di dimensioni fisse.
Ogni vertice delle aree è ora il tuo punto fisso di riferimento Dai la direzione ai bordi mentre cambiano posizione
Calcola la tua destinazione come vertici formati da bordi dai vertici delle aree fisse.
Registra i vertici, la durata e la velocità a ogni direzione cambia
Ora puoi pre-tracciare un arco o un angolo se necessario per una vista o una superficie

Aggiungere la direzione come sarebbe la direzione della bussola dal vertice 1 (origine) al vertice 2 (destinazione) sarebbe semplice come determinare se i vertici dell'origine sono maggiori o minori dei vertici della destinazione. Per quanto riguarda la posizione in cui si memorizzerebbe questo valore, questa sarebbe la discrezionalità dei programmatori.

Un metodo simile è utilizzato dal gioco Minecraft. Cercare su questo potrebbe essere di aiuto.

    
risposta data 02.11.2015 - 22:46
fonte

Leggi altre domande sui tag