Da matrice di punti a tabella e vice versa
Ho un "problema matematico", forse un po' troppo lungo e complesso da spiegare in dettaglio, ma che cercherò di formalizzare anche per renderlo più interessante.
In un piano cartesiano ci siano 9 punti $ P_0, P_1, ..., P_8 $ disposti in una matrice 3 x 3 a passo costante e uguale nelle due dimensioni.
Consideriamo ora una proposizione booleana sulla distanza euclidea $ D_{ij} $ tra i due punti generici $ P_i, P_j $, vera se e solo se la distanza è minore o uguale al passo.
Possiamo ora creare una tabella logica 9 x 9 che contenga tutte le combinazioni di punti con il valore booleano relativo ad ogni coppia.
La tabella è facilmente immaginabile anche senza scriverla: i punti di angolo avranno due punti che soddisfano la disequazione, i punti mediani ne avranno tre, mentre quello centrale quattro.
Veniamo al problema: è possibile invertire il procedimento? Ovvero, avendo a disposizione la sola matrice 9 x 9, è possibile ricreare la disposizione dei punti sul piano?
Ovviamente ci sono dei gradi di libertà che devono essere accettati, come il fatto che la disposizione ottenuta possa avere un offset qualsiasi in X e Y, possa essere speculare (rispetto alla disposizione originaria) nelle due direzioni e possa avere una rotazione qualsiasi. La disposizione ottenuta potrà apparire anche deformata o stirata / compressa nelle due direzioni. Anche la dimensione totale, ovviamente potrà essere libera.
Il punto fondamentale è che la posizione relativa dei punti resti la stessa: ad esempio se $ P_i $ si trovava tra $ P_j $ e $ P_k $ , questa caratteristica deve risultare invariata; se $ P_x $ era in angolo, dovrà risultare in angolo anche ottenendo la disposizione a partire dalla tabella.
E' possibile? Se è possibile, esiste un algoritmo già sperimentato?
(Per i curiosi, il problema riguarda il gli algoritmi di instradamento multi-hop nelle comunicazioni P2P in una rete mesh, quando Dijkstra risulta troppo complesso da implementare.)
In un piano cartesiano ci siano 9 punti $ P_0, P_1, ..., P_8 $ disposti in una matrice 3 x 3 a passo costante e uguale nelle due dimensioni.
Consideriamo ora una proposizione booleana sulla distanza euclidea $ D_{ij} $ tra i due punti generici $ P_i, P_j $, vera se e solo se la distanza è minore o uguale al passo.
Possiamo ora creare una tabella logica 9 x 9 che contenga tutte le combinazioni di punti con il valore booleano relativo ad ogni coppia.
La tabella è facilmente immaginabile anche senza scriverla: i punti di angolo avranno due punti che soddisfano la disequazione, i punti mediani ne avranno tre, mentre quello centrale quattro.
Veniamo al problema: è possibile invertire il procedimento? Ovvero, avendo a disposizione la sola matrice 9 x 9, è possibile ricreare la disposizione dei punti sul piano?
Ovviamente ci sono dei gradi di libertà che devono essere accettati, come il fatto che la disposizione ottenuta possa avere un offset qualsiasi in X e Y, possa essere speculare (rispetto alla disposizione originaria) nelle due direzioni e possa avere una rotazione qualsiasi. La disposizione ottenuta potrà apparire anche deformata o stirata / compressa nelle due direzioni. Anche la dimensione totale, ovviamente potrà essere libera.
Il punto fondamentale è che la posizione relativa dei punti resti la stessa: ad esempio se $ P_i $ si trovava tra $ P_j $ e $ P_k $ , questa caratteristica deve risultare invariata; se $ P_x $ era in angolo, dovrà risultare in angolo anche ottenendo la disposizione a partire dalla tabella.
E' possibile? Se è possibile, esiste un algoritmo già sperimentato?
(Per i curiosi, il problema riguarda il gli algoritmi di instradamento multi-hop nelle comunicazioni P2P in una rete mesh, quando Dijkstra risulta troppo complesso da implementare.)
Risposte
Premesso che hai sbagliato sezione e che spero di aver capito ...
... la "cosa" non mi pare difficile ... se $P_0$ è un punto d'angolo tra $P_1$ e $P_2$ avrai solo due coppie nella tua tabella e cioè $P_0P_1$ e $P_0P_2$ (non tengo conto dell'ordine, tanto son tutti doppi ...), da ciò deduci che $P_0$ è un angolo, idem per gli altri tre; il mediano tra due angoli è l'unico che "fa coppia" con quei due, gli altri non possono e quello che rimane è il centrale ... IMHO
Cordialmente, Alex

Cordialmente, Alex
Grazie per la risposta.
Se ho sbagliato sezione, chiedo a chi ha i superpoteri, di spostare il 3D nella sezione corretta (qual è?).
Il problema con 9 punti è solo per rendere comprensibile l'aspetto "numerico" della questione. Con un numero così piccolo di nodi si può agire per esclusione e il modo in cui procedi dà il risultato voluto.
Chiedevo informazioni sull'esistenza di un algoritmo generico perché l'implementazione reale ha qualcosa come 1400 punti e scattering casuale sul piano. Ovviamente non può essere risolta a tentativi.
Se ho sbagliato sezione, chiedo a chi ha i superpoteri, di spostare il 3D nella sezione corretta (qual è?).
Il problema con 9 punti è solo per rendere comprensibile l'aspetto "numerico" della questione. Con un numero così piccolo di nodi si può agire per esclusione e il modo in cui procedi dà il risultato voluto.
Chiedevo informazioni sull'esistenza di un algoritmo generico perché l'implementazione reale ha qualcosa come 1400 punti e scattering casuale sul piano. Ovviamente non può essere risolta a tentativi.
Beh, tu hai fatto una domanda e io ho risposto a quella ... se il problema è diverso basta dirlo ...
Penso che la sezione più adatta sia informatica ...
EDIT: cmq penso che il problema si possa risolvere allo stesso modo, partendo dagli angoli, trovando i vicini e cosi via ... costruendolo punto per punto ...

Penso che la sezione più adatta sia informatica ...
EDIT: cmq penso che il problema si possa risolvere allo stesso modo, partendo dagli angoli, trovando i vicini e cosi via ... costruendolo punto per punto ...
Nulla da dire sulla tua risposta. Era necessario partire con una ultra-semplificazione per rendere comprensibile il problema. Questo scambio era preventivato e sarà utile per costruire un percorso che renda comprensibile il problema. (Partire descrivendo una nuvola informe di punti in un iperspazio con una metrica non euclidea avrebbe reso tutto incomprensibile).
Tornando al "punto", la tua idea di partire da un angolo non credo possa essere utilizzabile perché non esiste un angolo nella disposizione iniziale: i punti sono sparsi e si possono avere concentrazioni diverse in diverse aree. Quindi un punto potrà trovarsi con molti altri vicini, mentre altri punti potranno averne magari uno solo.
Ciò che si vuole ricostruire è la disposizione relativa dei punti, indipendentemente dalla forma iniziale. Appena posso, provo a disegnare qualcosa.
Tornando al "punto", la tua idea di partire da un angolo non credo possa essere utilizzabile perché non esiste un angolo nella disposizione iniziale: i punti sono sparsi e si possono avere concentrazioni diverse in diverse aree. Quindi un punto potrà trovarsi con molti altri vicini, mentre altri punti potranno averne magari uno solo.
Ciò che si vuole ricostruire è la disposizione relativa dei punti, indipendentemente dalla forma iniziale. Appena posso, provo a disegnare qualcosa.
Adesso è tardi e comunque io non sono adatto per questo problema, fidati
... come detto un'altra sezione sarebbe meglio ... per te e il tuo problema soprattutto
... però una cosa la dico lo stesso: mi sta bene l'idea di presentare il problema con un "modellino in scala" però deve essere identico a quello vero e cioè con le stesse "problematiche" e condizioni ... se mi dici che i punti d'angolo non ci sono allora la tua presentazione iniziale non è "semplificata", è sbagliata ... IMHO ...
Cordialmente, Alex



Cordialmente, Alex
Come ti dicevo, è ok anche per me spostare il £D, ma io non posso farlo (e non ne apro certo un altro come duplicato...). Se un moderatore può farlo, beh, grazie fin d'ora.
La prima esposizione è una sovra-semplificazione del problema. E' voluto che sia estremamente semplice: se non si riesce a risolvere quella, allora non ha senso cercare di affrontare il problema completo.
Allego un'immagine di una situazione più vicina alla realtà: in nero i punti (nodi) dell'insieme; in blu il nodo di riferimento; in rosso i nodi che soddisfano la condizione (distanza inferiore alla soglia). Cambiando il nodo di riferimento, ovviamente cambiano anche i nodi che soddisfano la disuguaglianza. Legata a questa immagine c'è una tabella 1358 x 1358 che... non riporto.

Aggredire il problema da qui non mi sembra una buona idea... provare a farlo per la versione "soft" del primo messaggio forse può dare buone idee per risolvere il problema vero.
La prima esposizione è una sovra-semplificazione del problema. E' voluto che sia estremamente semplice: se non si riesce a risolvere quella, allora non ha senso cercare di affrontare il problema completo.
Allego un'immagine di una situazione più vicina alla realtà: in nero i punti (nodi) dell'insieme; in blu il nodo di riferimento; in rosso i nodi che soddisfano la condizione (distanza inferiore alla soglia). Cambiando il nodo di riferimento, ovviamente cambiano anche i nodi che soddisfano la disuguaglianza. Legata a questa immagine c'è una tabella 1358 x 1358 che... non riporto.

Aggredire il problema da qui non mi sembra una buona idea... provare a farlo per la versione "soft" del primo messaggio forse può dare buone idee per risolvere il problema vero.
Ma qual è il problema vero? In quest'ultimo post metti "il punto di partenza" ma non quello di arrivo, non scrivi a "cosa" vuoi arrivare, e non é vero che lo hai messo nel primo post, perché a quel caso "preciso" con certe condizioni "definite" ti è stata data risposta (esauriente secondo me), che però non ti sta bene "non ci sono angoli, non è una matrice, ..."
Bene, allora dovresti "chiarire" qual è "l'oggetto" al quale vuoi giungere ...
Cordialmente, Alex
Bene, allora dovresti "chiarire" qual è "l'oggetto" al quale vuoi giungere ...
Cordialmente, Alex
axpgn, mi spiace di non risultarti chiaro come ti sembrerebbe doveroso, e quindi provo a rendere di più facile comprensione il mio ultimo post:
il punto di partenza è quella disposizione di punti, fino a qui sono riuscito ad essere sufficientemente chiaro anche secondo te. Il punto di arrivo è... lo stesso del punto di partenza, la stessa disposizione di punti sul piano. In mezzo ci sta la matrice booleana 1358 x 1358.
Il percorso dalla disposizione di punti alla matrice non comporta alcun problema, mentre il passaggio dalla matrice alla disposizione di punti... non mi riesce. Qui sta il problema.
A lato ci sono i dettagli del primo post, in particolare sui gradi di libertà per la disposizione finale.
P.S. la rappresentazione grafica dei punti è colorata per fornire l'esempio di una delle righe della matrice. E' la riga corrispondente al punto in blu: i punti rossi sono quelli che soddisfano la disequazione, quelli neri, sono quelli che non la soddisfano.
P.P.S. La soluzione da te proposta per il problema semplificato di cui al primo post, è la soluzione particolare a quello specifico esempio, non è un algoritmo che permetta di risolvere la classe dei problemi di cui quello e solo un esempio. Nel mio secondo post, chiarisco che l'oggetto del desiderio è un algoritmo generico per tale soluzione e non la soluzione dell'esempio. Quindi, non ci sono problemi "veri" e altri "meno veri": ciò a cui vorrei arrivare non è variato dall'inizio, è scritto li.
il punto di partenza è quella disposizione di punti, fino a qui sono riuscito ad essere sufficientemente chiaro anche secondo te. Il punto di arrivo è... lo stesso del punto di partenza, la stessa disposizione di punti sul piano. In mezzo ci sta la matrice booleana 1358 x 1358.
Il percorso dalla disposizione di punti alla matrice non comporta alcun problema, mentre il passaggio dalla matrice alla disposizione di punti... non mi riesce. Qui sta il problema.
A lato ci sono i dettagli del primo post, in particolare sui gradi di libertà per la disposizione finale.
P.S. la rappresentazione grafica dei punti è colorata per fornire l'esempio di una delle righe della matrice. E' la riga corrispondente al punto in blu: i punti rossi sono quelli che soddisfano la disequazione, quelli neri, sono quelli che non la soddisfano.
P.P.S. La soluzione da te proposta per il problema semplificato di cui al primo post, è la soluzione particolare a quello specifico esempio, non è un algoritmo che permetta di risolvere la classe dei problemi di cui quello e solo un esempio. Nel mio secondo post, chiarisco che l'oggetto del desiderio è un algoritmo generico per tale soluzione e non la soluzione dell'esempio. Quindi, non ci sono problemi "veri" e altri "meno veri": ciò a cui vorrei arrivare non è variato dall'inizio, è scritto li.
Partire descrivendo una nuvola informe di punti in un iperspazio con una metrica non euclidea avrebbe reso tutto incomprensibile
A parte il concetto maldefinito di informe direi che sarebbe stato meglio. La matematica è precisa e formale. Un problema definito in modo approssimativo e usando termini inappropriati è molto difficile da risolvere se non impossibile.
Detto questo, la matrice booleana contiene molte meno informazioni della distribuzione di partenza. E se anche avessi i valori della distanza invece dei booleani non avresti comunque la soluzione unica.
Non c'è nulla di cui dispiacersi ...
... piuttosto prova a mandare un MP ad un moderatore per il cambio di sezione ...
Comunque, rimango dello stesso parere ... per farla breve un paio di cose:
1) Se quello che vuoi ottenere è quella stessa, identica "mappa" non vedo come ciò sia possibile, dato che ti occorrerebbero un paio di informazioni per ogni punto (coordinate cartesiane, polari, ...) mentre tu ne hai solo una (vicini o lontani).
2) Se invece vuoi qualcosa di simile a quanto detto nel primo post e con le stesse caratteristiche, il metodo che ho espresso lì va bene, perché se è vero che è una soluzione particolare per un caso particolare, è vero anche che è tranquillamente e facilmente estendibile ad un qualsiasi "ipercubo" (o parallelepipedo o quello che è ...) con $n$ dimensioni e con tutti i punti che ci stanno dentro ...
Cordialmente, Alex

Comunque, rimango dello stesso parere ... per farla breve un paio di cose:
1) Se quello che vuoi ottenere è quella stessa, identica "mappa" non vedo come ciò sia possibile, dato che ti occorrerebbero un paio di informazioni per ogni punto (coordinate cartesiane, polari, ...) mentre tu ne hai solo una (vicini o lontani).
2) Se invece vuoi qualcosa di simile a quanto detto nel primo post e con le stesse caratteristiche, il metodo che ho espresso lì va bene, perché se è vero che è una soluzione particolare per un caso particolare, è vero anche che è tranquillamente e facilmente estendibile ad un qualsiasi "ipercubo" (o parallelepipedo o quello che è ...) con $n$ dimensioni e con tutti i punti che ci stanno dentro ...
Cordialmente, Alex
vict85, la terminologia è purtroppo quella di un non-matematico. La mia matematica si limita a quella di ingegneria vecchio ordinamento, arrugginita da qualche lustro di utilizzo solo funzionale (funzionale scritto in corsivo...).
Sul fatto che la MB (matrice booleana) contenga molte meno informazioni della disposizione, non v'è alcun dubbio. La prima analisi che ho svolto è stata proprio questa: il contenuto informativo. L'impressione è che come è innegabile che si abbia perdita di informazione, mi pare altrettanto innegabile che la posizione relativa (non le distanze) tra i punti si dovrebbero conservare.
Nella disposizione finale, le distanze, l'orientamento, la forma della nuvola di punti non sono importanti; ciò che conta è che in un ipotetico percorso da un punto ad un altro si mantenga la sequenza dei punti ai quali si passa vicino (vedi dettagli primo post).
L'assunto che il contenuto informativo nella MB sia sufficiente, deriva da alcune valutazioni fatte su modelli ultra-semplificati, come quello a dimensione 1, con una serie di punti disposti lungo un'asse. Ricostruire la disposizione partendo dalla MB è un'operazione elementare e l'informazione che si perde è solo la distanza assoluta e il verso della disposizione lungo l'asse (entrambe non importanti).
Purtroppo, già il passaggio da dimensione 1 a dimensione 2 mi risulta risolvibile solo in casi molto semplici (vedi post 1), non parliamo dei casi con dimensione 3 o 4, come poi dovrebbe essere necessario affrontare.
axpgn, potresti gentilmente indicarmi come il metodo da te indicato si potrebbe estendere ad un caso più generico? Se riuscissi a comprenderlo potrei provarlo immediatamente nel simulatore scritto proprio allo scopo. Sarebbe la soluzione.
Sul fatto che la MB (matrice booleana) contenga molte meno informazioni della disposizione, non v'è alcun dubbio. La prima analisi che ho svolto è stata proprio questa: il contenuto informativo. L'impressione è che come è innegabile che si abbia perdita di informazione, mi pare altrettanto innegabile che la posizione relativa (non le distanze) tra i punti si dovrebbero conservare.
Nella disposizione finale, le distanze, l'orientamento, la forma della nuvola di punti non sono importanti; ciò che conta è che in un ipotetico percorso da un punto ad un altro si mantenga la sequenza dei punti ai quali si passa vicino (vedi dettagli primo post).
L'assunto che il contenuto informativo nella MB sia sufficiente, deriva da alcune valutazioni fatte su modelli ultra-semplificati, come quello a dimensione 1, con una serie di punti disposti lungo un'asse. Ricostruire la disposizione partendo dalla MB è un'operazione elementare e l'informazione che si perde è solo la distanza assoluta e il verso della disposizione lungo l'asse (entrambe non importanti).
Purtroppo, già il passaggio da dimensione 1 a dimensione 2 mi risulta risolvibile solo in casi molto semplici (vedi post 1), non parliamo dei casi con dimensione 3 o 4, come poi dovrebbe essere necessario affrontare.
axpgn, potresti gentilmente indicarmi come il metodo da te indicato si potrebbe estendere ad un caso più generico? Se riuscissi a comprenderlo potrei provarlo immediatamente nel simulatore scritto proprio allo scopo. Sarebbe la soluzione.
Non c'è problema a ripeterlo però ribadisco che lo puoi applicare ad una "struttura" che abbia le caratteristiche che tu hai indicato nel primo post e non certo "alla mappa di punti" ... inoltre credo che non sia per niente efficiente, solo possibile ...
Se prendi un cubo avrai che i vertici si collegano ad altri tre punti, i punti sugli spigoli con altri quattro, i punti sulle facce con altri cinque e quelli interni al cubo con altri sei: in questo modo puoi classificare i tuoi punti.
Se parti a "disegnare" da un vertice (ma potresti partire da un punto qualsiasi) scegli uno dei tre punti a cui è collegato ed inizi a costruire uno spigolo; dai quattro punti collegati a questo secondo punto prendi l'unico che ha quattro collegamenti invece di cinque ovvero il punto che sta sullo spigolo e non sulle facce; prosegui così per completare lo spigolo e poi gli altri ... finito con gli spigoli, passi alle facce, cioè partendo da un qualsiasi punto che sta su uno spigolo scegli uno dei due punti collegati ad esso che stanno sulle facce e da quest'ultimo rifai lo stesso ragionamento fatto prima: tra i cinque punti collegati a questo ne scegli uno che stia su una faccia (cioè che abbia cinque collegamenti) e prosegui allo stesso modo, tieni conto che in ogni punto tu sai da "dove provieni" ovvero da quale punto sei partito perciò non c'è pericolo di ripercorrere una strada già fatta; finite le facce passi ai punti interni ...
In teoria non è difficile ma un'implementazione pratica la vedo difficoltosa ...
Cordialmente, Alex

Se prendi un cubo avrai che i vertici si collegano ad altri tre punti, i punti sugli spigoli con altri quattro, i punti sulle facce con altri cinque e quelli interni al cubo con altri sei: in questo modo puoi classificare i tuoi punti.
Se parti a "disegnare" da un vertice (ma potresti partire da un punto qualsiasi) scegli uno dei tre punti a cui è collegato ed inizi a costruire uno spigolo; dai quattro punti collegati a questo secondo punto prendi l'unico che ha quattro collegamenti invece di cinque ovvero il punto che sta sullo spigolo e non sulle facce; prosegui così per completare lo spigolo e poi gli altri ... finito con gli spigoli, passi alle facce, cioè partendo da un qualsiasi punto che sta su uno spigolo scegli uno dei due punti collegati ad esso che stanno sulle facce e da quest'ultimo rifai lo stesso ragionamento fatto prima: tra i cinque punti collegati a questo ne scegli uno che stia su una faccia (cioè che abbia cinque collegamenti) e prosegui allo stesso modo, tieni conto che in ogni punto tu sai da "dove provieni" ovvero da quale punto sei partito perciò non c'è pericolo di ripercorrere una strada già fatta; finite le facce passi ai punti interni ...
In teoria non è difficile ma un'implementazione pratica la vedo difficoltosa ...

Cordialmente, Alex
Raramente quello che vale in dimensione 1 può essere portato in dimensioni maggiori. In ogni caso quello che tu ti stai chiedendo, se ho capito bene, è come immergere un grafo (la cui matrice di adiacenza è definita dalla tua matrice booleana) in \(\displaystyle \mathbb{R}^n \) in modo tale che i nodi connessi lo rimangano e i nodi sconnessi siano almeno ad una certa distanza. Sicuramente è possibile, ma non penso che esista un modo semplice e computazionalmente efficiente (vedo tra l'altro vari punti problematici nella descrizione di axpgn[nota]Una volta trovato la posizione per un punto non è detto che questa non vada cambiata più avanti.[/nota]).
No, vict85, non c'è problema se lo fai in modo "ordinato" ... per esempio, mentre costruisci il primo spigolo partendo da un vertice puoi già costruirti il "bordo" di una faccia, così che quando finisci lo spigolo e arrivi all'altro vertice tra i due spigoli che si dipartono da questo vertice puoi scegliere che sta dalla parte della faccia che stai già costruendo; partendo a "costruire" da un punto conosciuto sai sempre dove ti trovi ...
Ovviamente è un metodo che fa schifo dal punto di vista dell'efficienza, volevo solo dimostrarne l'esistenza e la relativa "facilità"
Butto lì un'idea ... se hai un punto di partenza "preciso" puoi costruire un sistema "a livelli": il punto di partenza sta a livello $0$, i punti vicini ad esso stanno sul livello $1$, i punti vicini a quelli del livello $1$ ma che NON stanno sui livelli $1$ e $0$ li metti sul livello $2$, sul livello $3$ metti quelli vicini ai punti di livello $2$ ma che NON stanno sui livelli $2,1,0$ così via ...
Cordialmente, Alex
Ovviamente è un metodo che fa schifo dal punto di vista dell'efficienza, volevo solo dimostrarne l'esistenza e la relativa "facilità"
Butto lì un'idea ... se hai un punto di partenza "preciso" puoi costruire un sistema "a livelli": il punto di partenza sta a livello $0$, i punti vicini ad esso stanno sul livello $1$, i punti vicini a quelli del livello $1$ ma che NON stanno sui livelli $1$ e $0$ li metti sul livello $2$, sul livello $3$ metti quelli vicini ai punti di livello $2$ ma che NON stanno sui livelli $2,1,0$ così via ...
Cordialmente, Alex
Stai dando per scontato che le facce siano facili da definire. Potresti anche trovarti in una situazione in cui un punto centrale ha 3 o più connessioni tutte disconnesse tra di loro. In questo caso, quando si andranno ad aggiungere i punti connessi ai punti esterni potresti trovarti a dover permutare i punti del "bordo". Spero di essermi espresso bene.
Certamente se si avesse una triangolazione dei punti di partenza il problema diventerebbe molto più semplice.
Certamente se si avesse una triangolazione dei punti di partenza il problema diventerebbe molto più semplice.
Beh, ho ribadito che vale solo per la struttura che lui ha definito in partenza (dove si parlava di "matrice 3x3, passo costante, ecc.") ... se mancano dei pezzi al "cubo", e ci sono "buchi" la faccenda si fa più complicata (anche se penso che si possa gestire) ... comunque non è questo il suo problema ...
