Daha çox

Əldə edilə bilən bir ərazidə çoxbucaqlı qurmaq

Əldə edilə bilən bir ərazidə çoxbucaqlı qurmaq


Hal -hazırda izokronlar və əsas alqoritmlər sahəsində çalışıram. İndi problemlərə səbəb olan şey, izokronun özünün hesablanması deyil, nəticələrin görselleştirilməsidir.
İzokron alqoritmimin nəticəsi nöqtələr və kənarlardır. Əslində işləyən bir həllim var, amma 3873 kənar və 1529 qovşaq üçün işlər sonsuza qədər davam edir (2015 Core i7 CPU və olduqca sürətli SSD olan Lenovo T440s noutbukumda təxminən 2.0 saniyə). Saniyə yerinə msec :-) kimi bir şey istəyirəm.

Bəlkə kimsə mənə əlçatan əraziləri görselleştiren çoxbucaqlıların qurulması üçün lazım olan hesablama müddətini azaltmağımda kömək edə bilər.

Ancaq gözləyin ... hər şeydən əvvəl!
İzokronumun hesablama nəticəsi olduğum kənarların görüntüsü budur: Bu kənarları bir PostGIS verilənlər bazası cədvəlində saxlanılır və sadə xətlərdir.

İstifadəçiyə göstərmək istədiyim şey belə görünür: Şəklin çox cənubunda və çox şərqində əlaqəsi kəsilmiş yerlərə diqqət yetirin. Bunlar ayrı sahələr kimi çəkilməlidir (buna görə burada birləşməyə icazə verilmir :-))

Hal -hazırda bu sorğudan istifadə edirəm:

SEÇ ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (poligonlar)), 4326)) AS FROM (SE_ST_MakePolygon (ST_ExteriorRing (ST_GeometryN) (seqmentlər, generate_series (1), ST_NumGeometrləri)) "GEOMETRİ", 20, 'quad_segs = 2')) AS seqmentləri my_edgesdən AS a) AS b) AS c

Artıq bir az təcrübə etdim və bir çox sənədləri də oxudum, amma daha yaxşı bir həll tapa bilmirəm.
Gözümdə ən böyük problem ST_Unionun istifadəsidir (sənədlərdə qeyd edildiyi kimi bu funksiya yavaş ola bilər). Çox maraqlı şey budur ki, onu ST_Collect ilə əvəz etmək, ST_Buffer hesablamasını ləngidir, beləliklə, aşağıdakı sorğuların hamısı daha uzun çəkir, baxmayaraq ki kənarları arasındakı sahələri doldurmur (yalnız xətlərin ətrafında tampon yaradır) ):

SELECT ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (polygons)), 4326)) AS FROM (SELECT ST_Buffer (ST_Collect (ST_LineMerge ("GEOMETRY")))), 20, 'quad_segs = 2'M AS_ ASG

Bu, sistemimdə təxminən 3,8 saniyə çəkir (demək olar ki, iki dəfə). Bu kiçik testdən çıxardığım ilk nəticə budur ki, MultiLineStrings -ə gəldikdə ST_Buffer gözlənilmədən yavaşlayır (hər sətir üçün tampon yaratmaq və tamponları birləşdirməkdən daha yavaşdır - gözümdə çox qəribədir)

Mən də alfa formalarını (pgRouting tətbiqindən istifadə edərək) istifadə etməyə çalışdım, amma təyin etmək üçün bir alfa dəyəri olmadığından (və əslində indi belə bir dəyəri təyin etmək üçün həqiqətən hansı dəyərə verməyəcəyəm) yalnız bir böyük çoxbucaq alıram ( buna görə çox cənub və şərqdəki bölgələri ayrı bölgələr olaraq itirərdim, bu da istədiyim deyil).
Həm də ST_Polygonize (ağlıma gələn ilk şey idi) heç bir faydalı nəticə vermədi, amma bəlkə də burada nəyisə qaçırdım ...

PostGIS -də göstərilən sahəni yaratmaq üçün daha yaxşı bir yol varmı? Bəlkə də java kodu (jts) və ya müştəri tərəfi javascript kodunu (jsts) istifadə etməklə? Nəticədə göstərilən sahələr ayrı qaldıqca və hesablama (çox) daha sürətli olduğu müddətcə, bəzi detalları itirməklə yaşaya bilərdim.


GeoJSON seriyalaşmasını bir kənara qoyaraq, dizüstü kompüterimdə təxminən 6.3 saniyə çəkir:

SEÇ ST_MakePolygon (ST_ExteriorRing ((ST_Dump (ST_Union (ST_Buffer (geom, 20, 2)))). Geom)) bz_edges -dən

OpenJUMP -dakı məlumatlara baxaraq, çıxış hissəsində istənilən detal səviyyəsinə nisbətən küçə seqmentlərində bir az detal gördüm. Görünür ki, hətta bu xətlərin anında sadələşdirilməsi də PostGIS-də böyük bir sürətlənmə yarada bilər:

SEÇ ST_MakePolygon (ST_ExteriorRing ((ST_Dump (ST_Union (ST_Buffer (ST_Simplify (geom, 10), 20, 2))). Geom)) bz_edges -dən

şeyləri 2,3 saniyəyə endirir. Ümumiləşdirilmiş həndəsəni anında hesablamaq əvəzinə ayrı bir sütunda saxlayaraq daha yaxşı işlər görə biləcəyimi düşündüm, amma bu heç bir əlavə fayda vermədi.

Nə qədər kod yazmaq istədiyinizə görə, birdən çox nüvədən istifadə edə biləcəyiniz üçün başqa bir şey olmasa, demək olar ki, Java -da daha yaxşı işlər görə bilərsiniz. (Dəyərinə görə, JTS yuxarıdakı əməliyyatı 2,8 saniyədə yerinə yetirir). Bir yanaşma uzatmaq ola bilərCascadedPolygonUnionBirlik əməliyyatlarının bir qismini paralel olaraq həyata keçirmək. (yeniləmə - burada ParallelCascadedPolygonUnion)

Nümunə məlumatlarında, kənarların başlanğıc və son qovşaqlarına istinadlarla saxlanıldığını, yəni əvvəlcədən qurulmuş bir qrafikinizin olduğunu gördüm. Bu çoxbucaqlıları yarada biləcəyinizdən şübhələnirəm çox Ümumi həndəsə əməliyyatlarından istifadə etmək əvəzinə qrafikdən işləsəniz daha sürətli olar. Məsələn, belə bir şey edə biləcəyinizi düşünürəm:

  1. qrafikin əlaqəli komponentlərini müəyyənləşdirin
  2. bağlı olan hər bir komponent üçün minimum X koordinatına malik düyünü tapın (komponentin xaricində olması zəmanət verilir)
  3. mümkün olduqda həmişə sola (və ya sağa) dönərək komponentin kənarlarını gəzin. Bu, hər bir komponentin xarici üzüyünü verəcəkdir.
  4. xarici halqanı poliqonlaşdırın və müvafiq olaraq tamponlayın.