Interneto platybėse aptiktas įrašas apie tai, kaip paskaičiuoti poligonų etikečių pozicijai skirtas centro linijas.
Pabandžiau šitą mintį realizuoti atviro kodo priemonėmis. Voronoi poligonų skaičiavimą daro standartinės PostGIS funkcijos. Tarkim St_straightskeleton grąžina tokį rezultatą:
Kaip matome, griaučiai per daug detalūs. Šita problema sprendžiama darant vienokį ar kitokį pradinio poligono supaprastinimą (gelsvas poligonas – supaprastintas mėlynasis, griaučiai paskaičiuoti geltonam poligonui)
Jau daug geriau. Dabar, pagal aukščiau minėtą straipsnį, reikia paskaičiuoti ilgiausią kelią. Skaičiavimą norėjau turėti duomenų bazėje, realizuotą grynai PostgreSQL priemonėmis, todėl šis gan chrestomatinis grafų uždavinys tapo nedideliu iššūkiu: negalima buvo nei padaryti patogios objektų struktūros grafo vaizdavimui, nei naudoti rekursijos. Bet, nors ir negražus, kodas veikia, veikia greitai, ir grąžina tokį rezultatą (raudona linija).
Kaip ir būtų viskas, gautą centro liniją reikėtų dar paglotninti (tarkim Chaikino algoritmu).
Bet ne viskas taip paprasta. Tarkime jei imame poligoną su iškarpomis (salomis), tai galime gauti tokių egzotiškų variantų (formaliai teisingų, tai tikrai ilgiausias kelias)
Vienas iš sprendimo variantų būtų griaučius skaičiuoti tik pagal išorinį poligoną. Bet tada užrašas gali eiti per salas, kas ne visada yra gražu/priimtina. Matyt reikėtų išmesti tik mažas salas, virš kurių gali būti braižoma etiketė.
Kita pastebėta problema – formaliai ilgiausia linija nėra idealiausia linija etiketei:
Taigi matosi poreikis poligono etiketės linijos funkciją patobulinti. Pavyzdžiui pridėti galimybę rekursijai paskaičiavus eilinę liniją, prieš lyginant ilgį su anksčiau surasta „lydere“, pritaikyti papildomus koeficientus, kurie mažintų realiai paskaičiuotą ilgį:
- Už linijos iškraipymą (skaičiuojam azimuto kitimo modulį ties kiekvienu segmentų susikirtimu). Klausimas prieš ar po glotninimo.
- Už nutolimą nuo horizontalios linijos. Daugmaž apvaliuose poligonuose vardan nedidelio ilgio skirtumo nėra prasmės paskaičiuoti vertikalią centro liniją, jei horizontali bus tik truputį trumpesnė.
Kokių dar minčių būtų šiuo klausimu? Galutinis algoritmas bus patalpintas Atvirojo žemėlapio github repozitorijoje su atvira licencija. Jei kas norite pažaisti su darbine versija – kreipkitės asmeniškai.