Veel

Võrgu genereerimise algoritm

Võrgu genereerimise algoritm


Proovin lahendada võrgu genereerimise probleemi ja oleksin sisendite üle õnnelik. Kõigepealt minu probleemi kirjeldus:

Mul on vastavate vahemaadega asukohtade vaheliste ühenduste loend. Näiteks:

AsukohtA <-> AsukohtB: 4500 m AsukohtB <-> AsukohtC: 3000 m AsukohtC <-> AsukohtA: 2000 m… ja nii edasi…

Mida ma ei tea, aga proovige teada saada: minu asukohtade tegelik geograafiline asukoht. Ma tean mõne võrgu sõlme asukohta ja arvestades suurt vahemaade ühenduste loendit, peaks mul olema võimalik ligikaudselt leida oma tundmatute asukohtade asukohad.

Märkus: olen mitte püüdes tegelikult optimeerida selle võrgu kõiki teid (nt Dijkstra jne). Tahaksin lihtsalt teada, millised geograafilised koordinaadid minu süsteemi sõlmedel on.

Minu küsimus on: millist "sõlme paigutuse algoritmi" ma otsin? Mul oleks hea meel mis tahes märksõnade üle. Olen 100% kindel, et selle probleemi jaoks on olemas mõned algoritmid, kuid ma isegi ei tea, mida otsida.


Nagu sellest pildist näha

Iga tundmatu punkti jaoks on vaja teadaolevate koordinaatidega 3 punkti. Seega alustaksin teadaolevate punktide kolmnurksusega. Loodan, et ülejäänud protsess on pildilt selge.

Märkus: teadaolevate punktide kauguste ebatäpsuste tõttu peate hakkama saama 6 punktiga. Peate neist 3 rohima, ülejäänud 3 keskpunkt on teie tundmatu punkt. Võõrväärtuste eemaldamiseks on mitmeid meetodeid, mida ma isiklikult eelistan kumerat kerekoorimist.

Kahjuks töötab see kolmnurga sees tundmatu istumise korral. Kui see on väljaspool:

Peate leidma 3 punkti, mille vahekaugus on minimaalne