Vairāk

Daudzstūra veidošana virs sasniedzamas vietas


Pašlaik strādāju izohronu un pamatā esošo algoritmu jomā. Tagad problēmas rada nevis aprēķins, ja pats izohrons, bet gan rezultātu vizualizācija.
Mana izohrona algoritma rezultāts ir punkti un malas. Patiesībā man ir strādājošs risinājums, bet 3873 malām un 1529 mezgliem lietas šķiet mūžīgi (apmēram 2,0 sekundes manā Lenovo T440s klēpjdatorā, kurā ir 2015. gada Core i7 CPU un diezgan ātrs SSD). Sekundu vietā es gribu kaut ko vairāk kā msec :-).

Varbūt kāds var man palīdzēt samazināt aprēķina laiku, kas vajadzīgs, lai izveidotu daudzstūrus, kas vizualizē sasniedzamās zonas.

Bet pagaidi ... vispirms pirmās lietas!
Šeit ir redzama to malu vizualizācija, kas ir mana izohrona aprēķina rezultāts: Šīs malas tiek glabātas PostGIS datu bāzes tabulā un ir vienkāršas līnijas.

Tas, ko vēlos parādīt lietotājam, izskatās šādi: Ievērojiet atvienotos apgabalus attēla dienvidos un ļoti austrumos. Tie jāzīmē kā atsevišķas zonas (tāpēc šeit nav atļauta apvienošana :-))

Pašlaik es izmantoju šo vaicājumu:

SELECT ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (daudzstūri))), 4326)) AS pārklājums NO (SELECT ST_MakePolygon (ST_ExteriorRing (ST_GeometryN (segmenti, ģenerēt_sērijas) (1, ST_NumGeometries (segment) (ST))) "GEOMETRY", 20, 'quad_segs = 2')) AS segmenti FROM my_edges AS a) AS b) AS c

Es jau eksperimentēju un izlasīju arī daudz dokumentācijas, bet es vienkārši nevaru atrast labāku risinājumu.
Manuprāt, liela problēma ir ST_Union izmantošana (kā norādīts dokumentos, šī funkcija var būt lēna). Ļoti interesanti ir tas, ka tā aizstāšana ar ST_Collect, šķiet, palēnina ST_Buffer aprēķinu tā, ka viss sekojošais vaicājums aizņem vēl ilgāku laiku, lai gan tas neaizpilda laukumus starp malām (tas rada tikai buferi ap līnijām) ):

SELECT ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (daudzstūri))), 4326)) AS pārklājums NO (SELECT ST_Buffer (ST_Collect (ST_LineMerge ("GEOMETRY"))), 20, 'quad_segs = 2') AS daudzstūri no FR

Manā sistēmā tas aizņem apmēram 3,8 sekundes (tātad gandrīz divreiz vairāk laika). Mans pirmais secinājums no šī mazā etalona ir tāds, ka ST_Buffer kļūst negaidīti lēns, kad runa ir par MultiLineStrings (pat lēnāk nekā, veidojot buferus katrai rindai un apvienojot buferus - kas manās acīs ir vienkārši dīvaini)

Es arī mēģināju izmantot alfa formas (izmantojot ieviešanu no pgRouting), bet, tā kā nav alfa vērtības, ko iestatīt (un patiesībā es tagad īsti nezinātu, kurai vērtībai šādu vērtību iestatīt), es vienkārši saņemu vienu lielisku daudzstūri ( tāpēc es zaudētu reģionus dienvidos un austrumos kā atsevišķus reģionus, kas nav tas, ko es vēlos).
Arī ST_Polygonize (kas bija pirmā lieta, kas man ienāca prātā) nedeva nekādus lietojamus rezultātus, bet varbūt es kaut ko šeit palaidu garām ...

Vai ir labāks veids, kā izveidot PostGIS parādīto apgabalu? Varbūt arī izmantojot java kodu (jts) vai klienta puses javascript kodu (jsts)? Patiesībā es varētu dzīvot, zaudējot dažas detaļas, ja vien rezultātos redzamās zonas paliek atdalītas un aprēķins kļūst (daudz) ātrāks.


Atceļot GeoJSON serializāciju, manā klēpjdatorā seko apmēram 6,3 sekundes:

SELECT ST_MakePolygon (ST_ExteriorRing ((ST_Dump (ST_Union (ST_Buffer (geom, 20, 2)))). Geom)) FROM bz_edges

Aplūkojot OpenJUMP datus, ielu segmentos pamanīju diezgan daudz detaļu, salīdzinot ar vēlamo detalizācijas pakāpi. Šķiet, ka pat šo līniju vienkāršošana lidojumā var radīt lielu paātrinājumu PostGIS:

SELECT ST_MakePolygon (ST_ExteriorRing ((ST_Dump (ST_Union (ST_Buffer (ST_Simplify (geom, 10), 20, 2)))). Geom)) FROM bz_edges

kas samazina lietas līdz 2,3 sekundēm. Es domāju, ka es varētu darīt labāk, saglabājot vispārināto ģeometriju atsevišķā kolonnā, nevis aprēķinot to lidojuma laikā, bet tas faktiski nesniedza papildu labumu.

Atkarībā no tā, cik daudz koda esat gatavs rakstīt, jūs gandrīz noteikti varat strādāt labāk Java, ja nekas cits, jo varat izmantot vairāku kodolu priekšrocības. (Cik vērts, JTS veic iepriekš minēto darbību 2,8 sekundēs). Viena pieeja varētu būt pagarināšanaCascadedPolygonUnionlai dažas arodbiedrības darbības notiktu paralēli. (atjauninājums - šeit ir ParallelCascadedPolygonUnion)

Datu paraugos pamanīju, ka malas tiek saglabātas ar atsaucēm uz to sākuma un beigu mezgliem, t.i., jums ir iepriekš izveidota diagramma. Man ir aizdomas, ka jūs varat izveidot šos daudzstūrus daudz ātrāk, ja strādājat no diagrammas, nevis izmantojat vispārīgas ģeometrijas operācijas. Piemēram, es domāju, ka jūs varētu rīkoties šādi:

  1. identificēt grafika savienotos komponentus
  2. katram pievienotajam komponentam atrodiet mezglu ar minimālo X koordinātu (garantēts, ka tā atrodas komponenta ārpusē)
  3. staigājiet pa detaļas malām, vienmēr pagriezieties pa kreisi (vai pa labi), kad tas ir iespējams. Tādējādi jūs iegūsit katras detaļas ārējo gredzenu.
  4. atbilstoši poligonizējiet ārējo gredzenu un buferi.


Skatīties video: Imagine logo: ház eljárásokkal (Oktobris 2021).