Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Valaki mondja meg!

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]  

Szeretnél hozzászólni? Jelentkezz be.
[2022] Hajba Károly2015-03-07 19:56:13

Nem T_OBJ_ szerepel, hanem T_FELIRAT

Előzmény: [2019] Hajba Károly, 2015-03-07 18:31:21
[2021] Róbert Gida2015-03-07 19:42:21

Heurisztika is müködik itt: legyen S a sokszög súlypontja, míg d az S és a csúcsok közötti maximális távolság. Így, ha egy p pont d-nél távolabb van S-től, akkor nem lehet a sokszögben. (és ez konkáv sokszögre is igaz természetesen).

Általában egy megyében van egy terület, így csak azokat a sokszögeket kell végignézni amik az adott megyében vannak. Egy szebb algoritmus lehetne quadtree-k alkalmazása: http://en.wikipedia.org/wiki/Quadtree .

[2020] Erben Péter2015-03-07 19:41:52

Szép feladat.

A valódi projektekben az adatok pontatlansága, illogikus tárolása sokszor több gondot okoz, mit az, hogy van-e jó algoritmus az elméleti problémára. A hibák javítása és az adatok "tisztítása" nehezebb, mit az eredeti kérdés megoldása.

Előzmény: [2017] Hajba Károly, 2015-03-07 17:22:54
[2019] Hajba Károly2015-03-07 18:31:21

Itt egy minta. 14. és 16. oldal

14. oldal: A határvonal a szakasz (s ezért írtam először vonalat), a határ a lánc, s a felület a terület.

16. oldal: A tényleges állományokban csak a T_PONT, T_HATARVONAL és ezektől független T_OBJ_ATTRDB van meghatározva, azaz a [* sárga szám *] helyett [**] szerepel, így nincs a T_FELULET-hez kötve. A * az adatok közötti szakaszoló jel.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2018] Hajba Károly2015-03-07 17:46:47

Tesztadat a szabványos DAT formátumban ill. a jelzett digitális szinten a földhivataloknál rendelkezésre állnak. Annyi észrevétellel, hogy egyes egyébként illeszkedő szakaszok elvileg közös pontja néha, ha csak kis mértékben is, de csak közel egymás mellett van. Gyanítom, hogy ez a régi rajzos térképek kézi digitalizálásának következménye. A CAD programom dwg-t fogad, s ha egy zárt görbébe kattintok, akkor azt kitölti. Sokszor ez nem sikerül és 'nem zárt görbe' hibajelzést ad, pedig ránézésre a rajzon a görbe zárt.

Majd megkérdezem, hogy (a DAT és DWG-n kívül) még milyen formátumban igényelhető adat.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2017] Hajba Károly2015-03-07 17:22:54

Köszönöm a részletes leírást.

Tegnap este rábukkantam az (A) példádra a wikin.

A feladat teljesen az életből való, sajnos minden téren. A szakaszok a földhivatali nyilvántartásban a telekhatárokat képező ömlesztve digitalizált szakaszok, az önálló pontok ezen telkek helyrajzi szám feliratának a helye. A '90-es évek végén nagyon jól kidolgozott szabvány lett megalkotva erre, de a megvalósítás során csak a lehető legkisebb átalakítást hajtották végre. A szabványban le van írva a telek fogalma is, de a nyilvántartásban nincsenek hozzárendelve a szakaszok ill. a láncok. Pedig amennyiben ez meg lenne oldva, akkor az erre alapuló területi tervezésnél nem egy CAD-es fedvényrajzot kellene készíteni kézzel és egérrel, ami vagy illeszkedik a töréspontokhoz vagy csak megközelíti, hanem a helyrajzi számmal. A hrsz-hez csak hozzárendelem a területfelhasználási adatokat, és a többit egy program elintézi ill. precízen felrajzolja, valóságos területi kimutatást készít. De jelenleg ez csak közelítő és emiatt nem lehet hiteles.

Most indult egy pilot program a "digitális Magyarországért", s ez épp abban a városban van, ahol dolgozom és épp ismerem az egyik kulcsembert. Így teszek egy kísérletet arra, hogy ez az átalakítás is bekerülhessen idővel a programba. Ehhez látnom kell a feladat folyamatát, méretét, buktatóit, s minden közbe jöhető dolgot mivel idő és pénzügyi igényt kell adni ahhoz, hogy esetleg bekerülhessen.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2016] Erben Péter2015-03-07 15:12:00

Azt elfelejtettem mondani, hogy ezek az egyszerű de lassú (&tex;\displaystyle O(l\cdot n)&xet;) algoritmusok voltak.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2015] Erben Péter2015-03-07 15:10:03

A legtöbb helyen két módszert említenek. (A) "metszések száma" /crossing number/; (B) "kanyargási szám" /winding number/. Inclusion of a point in a polygon

Az (A) azt csinálja, hogy húz egy egyenest a ponton át, és megnézi ennek az egyenesnek és a tartományt határoló szakaszoknak az összes metszéspontját. Ezeket a metszéspontokat rendezi, és azt feltételezi, hogy ha nem történt valami baj, akkor a metszéspontok felváltva jelzik, hogy beléptünk a tartományba, majd kiléptünk belőle. Tehát ez a konkáv tartományokra is működik. Ha a pontunk előtt páratlan sok metszéspont van az egyenesen (valamelyik irányból), akkor bent vagyunk, ha páros, akkor kint.

A gyakorlati megvalósításkor sok-sok nehézséggel szembesülünk.

1. Ha az egyenes átmegy a tartomány egy csúcsán, akkor azt két metszéspontnak hihetjük (a két szomszédos szakaszon egy-egy.)

2. Ha az egyenesre esik valamelyik határ szakasz, akkor ott végtelen sok közös pont van, és nem léptünk se be se ki.

3. Nem mindegy, hogy valós vagy egész aritmetikát alkalmazunk, mert egy egyenes és egy szakasz, illetve a pont és valamelyik szakasz nagyon közel eshet egymáshoz. Valós aritmetikát használva baj lehet a kerekítési hibákból, egész aritmetikánál pedig hatalmasra nőhetnek a nevezők és a számlálók, azért nem elegendők a programozási nyelvek beépített típusai. Ha az egész probléma eredete grafikai, és csak a képernyőn akarjuk pontokról eldönteni, hogy egy képernyőre rajzolt pixel egy képernyőre rajzolt tartományhoz képest hol van, akkor kevésbé kell félni a numerikus dolgoktól, mert a pixel méreténél kisebb hibák úgysem fognak látszani.

A (B) azon alapul, hogy megszámolja, hányszor kerüli meg a poligon a pontot. Akkor van kívül egy pont, ha nullaszor. Valahogy úgy megy a számolás, hogy a körüljárás szerint sorra vesszük a tartományt határoló szakaszokat, és mindegyikre kiszámoljuk, mekkora szögben látszik (irányított szakasz, irányított szög) a pontból. Külső pontra az előjeles szögek összege nulla, ez szemléletesen látszik konvex tartomány esetén.

Itt meg az a gond, hogy rengeteg inverz trigonometrikus függvényhívást csinálunk, ami lassú és ott is lehetnek kerekítési problémák.

Ha vannak konkrét bemenő adataid (amik nem titkosak), az érdekelne, mert ehhez a problémához nem egyszerű jó tesztadatokat gyártani.

Előzmény: [2013] Hajba Károly, 2015-03-06 16:56:29
[2014] Hajba Károly2015-03-06 17:21:29

Az előbb valamiért beleképzeltem a háromszögekre bontást, de te erről nem beszéltél.

Így akkor ezen sokszögbe beleesés vizsgálatának mikéntjéről is kérnék egy kis fejtágítást. Gyanítom, hogy a szakaszok által meghatározott egyenes egyik oldalán pozitív, míg a másik oldalán negatív értéket eredményezne a pont és végig pozitív oldalon kell maradni. De ebbe még bele kellene mélyednem.

Előzmény: [2012] jonas, 2015-03-04 22:54:07
[2013] Hajba Károly2015-03-06 16:56:29

Az első bekezdésben leírtakra időközben én is rájöttem. A pontokhoz hozzárendelem a vonalak azonosítóját. A vonalakhoz rendelt pontazonosítók meg már eleve adottak. Ahol ez nagyobb, mint 2, az csúcspontok. Ezek ismeretében már megtalálható az eljárás a területek körbejárásához.

A kérdés a második bekezdés. (A könyv nem játszik, nem tudok angolul.) Gyakorlatilag a vizsgált sokszöget elemi háromszögekre kell bontanom és minden háromszögre vizsgálni, hogy benne van-e. S ez időrabló mulatság.

Ha elmagyarázod, én állok elé a rögös utas hatékonyabb megoldás megértése elé.

Előzmény: [2012] jonas, 2015-03-04 22:54:07

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]    [162]    [163]    [164]    [165]    [166]    [167]    [168]    [169]    [170]    [171]    [172]    [173]    [174]    [175]    [176]    [177]    [178]    [179]    [180]    [181]    [182]    [183]    [184]    [185]    [186]    [187]    [188]    [189]    [190]    [191]    [192]    [193]    [194]    [195]    [196]    [197]    [198]    [199]    [200]    [201]    [202]    [203]    [204]    [205]    [206]    [207]    [208]    [209]    [210]    [211]    [212]    [213]    [214]    [215]    [216]    [217]    [218]    [219]    [220]    [221]    [222]    [223]    [224]    [225]    [226]    [227]    [228]    [229]    [230]