Daugiau

Kas yra įgaubto korpuso apibrėžimas, algoritmai ir praktiniai sprendimai?

Kas yra įgaubto korpuso apibrėžimas, algoritmai ir praktiniai sprendimai?


Išgaubtas korpusas

Išgaubtas formos korpusas apibrėžiamas taip:

Matematikoje išgaubtas korpusas arba išgaubtas apvalkalas X taškų rinkiniui realioje vektorinėje erdvėje V yra minimalus išgaubtas rinkinys, kuriame yra X (Vikipedija)

Vikipedija tai gražiai vizualizuoja, naudodama gumos juostos analogiją, ir yra keletas gerų algoritmų, kaip ją apskaičiuoti.

Įgaubtas korpusas

Įgaubtas korpusas vizualizuojamas naudojant raudoną liniją žemiau esančiame paveikslėlyje (mėlyna linija vaizduoja išgaubtą korpusą). Intuityviai tai yra daugiakampis, apimantis visus taškus, tačiau jo plotas yra mažesnis (minimalus?), Palyginti su išgaubtu korpusu. Dėl to daugiakampio kraštinės ilgis yra ilgesnis.

Įgaubtas korpusas gali būti kai kurių realaus pasaulio problemų sprendimas (pvz., Rasti pagrįstą miesto ribą).

Nepavyko rasti tinkamo įgaubto korpuso sąvokos apibrėžimo, algoritmo ir praktinio sprendimo. „Grass Wiki“ yra keletas aprašymų ir vaizdų, o „concavehull.com“ yra komercinis sprendimas.

Turite idėjų, algoritmų ir nuorodų?


Kaip pažymi „scw“, norite įgyvendinti α formas.

Alfa formos gali būti laikomos išgaubto korpuso apibendrinimu. Pirmą kartą jie buvo aprašyti 1981 m.

Edelsbrunneris, H .; Kirkpatrick, D .; Seidelis, R .; , „Dėl plokštumos taškų rinkinio formos“, Informacijos teorija, IEEE Transactions on, t.29, nr.4, p. 551–559, 1983 m. Liepa

Atvirojo kodo diegimai egzistuoja jus dominančioje aplinkoje:

PostGIS

Jei naudojate „PostGIS“ krūvą, „pgRouting“ pasirinktinis „Driving Distance“ plėtinys parodo alfa formos įgyvendinimą. Tačiau nesu tikras, ar galite pakeisti alfa parametrą.

Naudojimas yra žemiau:

SELECT the_geom AS alpha_shape FROM points_as_polygon ('SELECT id, ST_X (your_geom) AS x, ST_Y (your_geom) AS y FROM your_table');

Python

Tikriausiai yra daug „Python“ modulių, kuriuos galėtumėte naudoti. Girdėjau gerų dalykų apie CGAL, C ++ skaičiavimo geometrijos biblioteką. CGAL dalims yra „Python“ įvyniojimai, įskaitant CGAL alfa formos įgyvendinimą „Python“.

Atminkite, kad kai kurios CGAL dalys yra licencijuotos pagal QPL, o tai reiškia, kad jei platinsite savo programą, susietą su CGAL, gali tekti ją išleisti pagal QPL. Gerai išlaikyti savo kodą nuosavybės teise, jei neplatinsite savo programos kodo ar dvejetainių failų.


Štai ko jūs ieškote.

Programą galite atsisiųsti ir išbandyti: (java, pagal GPL licenciją)

Straipsnyje pateikiamas algoritmas:

Duckham, M., Kulik, L., Worboys, M. F., Galtonas, A. (2008) Efektyvus paprastų daugiakampių generavimas, apibūdinantis plokštumos taškų aibės formą. Rašto atpažinimas v41, 3224-3236


Atrodo, kad tai yra specifinis alfa formų, kurios, mano nuomone, yra bendresnė šios problemos forma, taikymas. R turi alfa korpuso modulį, kuriame yra puikūs alfa formų skaičiavimo dokumentai. Taip pat patikrinkite šį išsamų alfa formų foną. Jei norite apskaičiuoti tik išgaubtus/įgaubtus korpusus, patikrinkite lazerio dalį, dalį lazerių, ji gerai keičiasi ir gali valdyti milijonus įvesties taškų.

Galiausiai, ši įdomi „Flickr“ alfa formų programa prieš kurį laiką padarė raundus, parodydama jų naudingumą vartotojų sugeneruoto taško turiniui kaupti:


„PostGIS“ magistralėje įdiegtas ST_ConcaveHull. http://postgis.net/docs/ST_ConcaveHull.html


Aš sukūriau labai efektyvų įrankį, vadinamą riba (1,2), kuris apskaičiuoja įgaubtą LIDAR korpusą LAS/LAZ/SHP/ASCII formatu ir išsaugo rezultatą kaip vektoriaus ribinį daugiakampį ESRI Shapefile formatu arba geografiškai nurodytą KML failą.

Štai paleidimo pavyzdys:

C:  lastools  bin> lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp 3265110 taškų skaičiavimas ir išgaubto korpuso skaičiavimas 3265110 taškų atžvilgiu, augantis į vidų įgaubto korpuso link (su įgaubimu = 50), išgaubęs įgaubtą korpusą, įgaubtas korpusas turi 1639 taškus

Kai kurios rezultatų nuotraukos yra čia.


Čia yra R funkcija, įgyvendinanti „Alpha Hull“ modelį. Išvestis yra sp daugiakampio objektas. Žiūrėkite pavyzdį antraštėje. Tam reikalingi paketai sp, alfahull ir maptools.

** Atnaujinimas (2018-01-15) „alfahull“ paketo gaminamų objektų pakeitimai buvo daug. Todėl turėjau perrašyti funkciją. Į paketą „spatialEco“ pridėjau išgaubtą korpusą. Tačiau dėl licencijavimo apribojimų „alfahull“ pakete ši funkcija pasiekiama tik „GitHub“ kūrimo versijoje. Kūrimo versiją galima įdiegti naudojant:

biblioteka (devtools) install_github ("jeffreyevans/spatialEco")

Čia yra funkcijų naudojimo pavyzdys

bibliotekos (sp) bibliotekos (spatialEco) duomenys (meuse) koordinatės (meuse) = ~ x+y a <- išgaubtas Korpusas (meuse, alpha = 100000) plot (a) taškai (meuse, pch = 19)

Konvertuokite gautą „SpatialLinesDataFrame“ į „SpatialPolygonsDataFrame“

biblioteka (sf) a <- sf :: st_as_sf (a) a <- sf :: st_polygonize (a) klasė (a <- as (a, „Erdvinis“)) sklypas (a)

Išbandykite kelias alfa reikšmes

par (mfcol = c (2,2)) (a in c (500, 1500, 5000, 100000)) {ch <- išgaubtas Korpusas (meuse, alfa = a) grafikas (ch) taškai (meuse, pch = 19) pavadinimas (įklijuoti0 ("alfa =", a))}


Apie R diegimo alfa formas yra straipsnis apie „Alfa formų pavertimą SP objektais“

Jis pagrįstas alfahull, sp ir spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919


JTS (https://github.com/locationtech/jts) suteikia išgaubto korpuso diegimą. Martinas Daviesas taip pat paminėjo, kad darbuose yra „Alfa Shape“ algoritmas, todėl galbūt norėsite patikrinti SVN saugyklą, kad pamatytumėte, ar ji dar yra, jei to norite.


Kalbant apie JTS, galite naudoti „Geoscript“ manipuliuoti JTS biblioteka. Straipsnį apie išgaubtą korpusą rasite http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html. „GeoScript“ diegimas galimas naudojant „JavaScript“, „Python“, „Scala“ ir „Groovy“. Oficiali svetainė: http://geoscript.org


Štai programa, parašyta C, kuri apskaičiuoja išgaubtus korpusus, alfa formas, Delauney trikampius ir Voronoi tūrius:

  • Korpusas - Kenas Clarksonas (2002)

Kitas išgaubtas korpuso algoritmas su C ir „Java“ diegimais yra čia:

  • Išgaubtas korpusas (2D) - skaičiavimo geometrija C, Joseph O'Rourke (1998)

Norėdami pridėti prie ankstesnių šio įrašo atsakymų, bent jau nuo QGIS 2.6 turi įgaubto korpuso algoritmą

Parametrai
Įvesties taško sluoksnis [vektorius: taškas]
čia įdėkite parametrų aprašymą

Slenkstis (0-1, kur 1 yra lygiavertis išgaubtam korpusui) [skaičius]
čia įdėkite parametrų aprašymą
Numatytasis: 0.3

Leisti skyles [loginis]
čia įdėkite parametrų aprašymą
Numatytasis: tiesa

Padalinti kelių dalių geometriją į vienos dalies geometriją [loginis]
Numatytasis: klaidinga

Išėjimai Įgaubtas korpusas [vektorius]
įdėkite išvesties aprašymą čia

Konsolės naudojimas
processing.runalg ('qgis: įgaubtas korpusas, įvestis, alfa, skylės, no_multigeometry, output)

Be to, „Esri“ turi įrankį „Minimali ribinė geometrija“ (duomenų valdymas)

Tai leidžia pasirinkti geometrijos tipą, į kurį įeina išgaubtas korpusas


Yra naujas „GRASS GIS 7“ priedas: v.concave.hull. Taip pat žiūrėkite http://grasswiki.osgeo.org/wiki/Create_concave_hull


Padėti išsiaiškinti jūsų klausimo dalį „tinkamai apibrėžti“; galbūt pažiūrėjote į https://en.wikipedia.org/wiki/Convex_hull ir radote tai, kas galėtų būti laikoma „tinkamu“ apibrėžimu, tačiau pastebėjote, kad jo trūksta, todėl galbūt „naudingesnis“ apibrėžimas:

Dėl kiekvieną taškas išgaubto korpuso viduje, tiesi linija iki bet koks taškas ne korpuso viduje, tik vieną kartą susikirs korpusą.

Tai naudinga, nes gavę tašką galite per jį sukonstruoti liniją ir išbandyti tą sukonstruotą liniją, kertančią korpuso segmentus.

  • Nėra sankirtos, taškas nėra korpuse.
  • Vienos sankryžos taškas yra ant korpuso.
  • Dvi sankirtos taškas yra korpuso viduje
  • Tiesi linija negali kirsti išgaubto korpuso daugiau nei du kartus