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]  

Szeretnél hozzászólni? Jelentkezz be.
[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
[2012] jonas2015-03-04 22:54:07

A lényeg a következő. Először minden olyan csúcsban, ahol a töröttvonalak (láncok) végei találkoznak, találd meg az összes töröttvonalat, és ezeket rakd ciklikus sorrendbe a kiindulási szögük szerint. Utána ez alapján meg tudod találni az összes sokszöget, és mindegyiket az ezek határát alkotó töröttvonalakkal le tudod írni úgy. Ezt úgy lehet megtenni, hogy minden töröttvonalból elindulsz mindkét irányba, és átmész a következő töröttvonalra a csúcsnál, mindig balra fordulva.

Ez után meg kell találnod, hogy melyik pont melyik sokszögbe esik bele. Ha nem túl sok kijelölt pontod van (vagyis itt nem túl sok sokszöged), akkor ezt úgy teheted meg, hogy minden ponthoz és minden sokszöghöz megvizsgálod, hogy a pont beleesik-e a sokszögbe. Ez nagyjából &tex;\displaystyle O(l*n) &xet; ideig tart, ha &tex;\displaystyle l &xet; a szakaszok száma és &tex;\displaystyle n &xet; a kijelölt pontok száma, mert minden ponthoz minden sokszög minden élén végig kell menned, vagyis minden szakszon kétszer. Ha sok kijelölt pontod van, akkor ez túl sokáig tarthat. Van hatékonyabb megoldás is, ami csak kvázi-lineáris időt vesz igénybe, de ez az, amit bonyolult megérteni és bonyolult implementálni is. A könyv, amit idéztem, elmagyarázza az erre szolgáló eljárást.

Előzmény: [2008] Hajba Károly, 2015-03-04 17:49:22
[2011] jonas2015-03-04 22:42:47

Ja, és elméleti leírást szeretnél, hogy megértsd a szükséges algoritmust, vagy pedig inkább gyakorlatibb szoftverkönyvtárt, amivel implementálni tudod?

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2010] jonas2015-03-04 22:41:38

Úgy érted, hogy a láncok egymást nem keresztezik, csak a végpontjukban találkoznak, vagy esetleg érintik egymást? Az egyes területek sokszög alakúak, és a láncok teljesen körbezárják őket? Ha jól értem a feladatodat, akkor van rá nagyon hatékony algoritmus, de ez nem egyszerű.

Van erről a témáról egy jó könyv, amit ajánlanék. Magyar nyelvűt nem tudok.

Mark de Berg; Otfried Cheong; Marc van Kreveld; Mark Overmars, Computational Geometry; Algorithms and Applicatoins. Springer, "http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-77973-5". Vigyázz, legalább három különböző korú kiadás van belőle.

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2009] Hajba Károly2015-03-04 17:51:28

Igen, a vonal az szakasz. Pongyolán fogalmaztam.

Előzmény: [2007] Erben Péter, 2015-03-04 13:49:33
[2008] Hajba Károly2015-03-04 17:49:22

Hosszú magyarázó szöveget írtam, de OK-zásnál elszállt. Most sem időm, sem lelki erőm nincs újból leírni az egészet. Este otthon újból nekiesek és rajzot is készítek hozzá.

Jelenleg nem éles programozási feladat, csak az eljárást kellene kitalálni, meghatározni.

Elvileg akár milliárd pont és szakasz is lehetséges, de ezek több kisebb adott részből adódnak össze. A koordinátaérték max. százmillió.

Szakasz pontja csak már korábban leírt pont lehet.

Előzmény: [2007] Erben Péter, 2015-03-04 13:49:33
[2007] Erben Péter2015-03-04 13:49:33

Ez egy programozási feladat?

Ha igen, akkor szükség lenne még néhány adatra. Például:

- Legfeljebb hány pont lehet?

- Legfeljebb hány vonal lehet? A vonal az egy szakasz? A szakasz végpontjai a fentebb leírt pontok közül kerülnek ki, vagy ezek más pontok?

- Az előforduló koordináták abszolút értékére van felső becslésünk?

- Hány másodperc alatt kell futnia a programnak?

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2006] Hajba Károly2015-03-04 13:31:51

Üdv Mindenkinek!

Az alábbi problémába futottam bele, s ehhez kérném a segítségeteket.

-------

Van sok pontom a koordinátarendszer I. negyedének origóhoz közeli elég nagy, de nem végtelen méretű területén egész számú koordinátákkal meghatározva. Van továbbá sok, egymást nem metsző vonalam két különböző ponttal meghatározva. A pontok és vonalak egyedi, sorszám jellegű azonosítóval rendelkeznek, de a sorszámozás és elem (pont, vonal) helye között nincs összefüggés.

A vonalak valamilyen hosszú, elágazásmentes és folytonos láncot (tört vonal) képeznek. A láncok nem rendelkeznek azonosítóval és nincs meghatározva a lánc és az őt meghatározó vonalak közötti kapcsolat. Több lánc egy területet zár körbe oly módon, hogy a láncok csak végpontjuknál csatlakoznak ill. a csatlakozópontnál legalább 3 láncnak kell találkoznia. Minden körbezárt területen belül található egy önálló pont, mely a terület azonosítóját tartalmazza, de nincs meghatározva a terület és a területet meghatározó láncok kapcsolata.

Feladat:

Létre kell hozni a láncok azonosítóját és a vonalak azonosítója és csakis ennek segítségével, sorrend függő felsorolással meg kell határozni (le kell írni) a lánc és az őt meghatározó vonalak közötti kapcsolatot; továbbá a láncok azonosítója és csakis ennek segítségével, sorrend függő felsorolással meg kell határozni (le kell írni) a terület és az őt meghatározó láncok közötti kapcsolatot ill. hozzárendelni a terület azonosítójához.

-------

Még nem mélyedtem el mélyen a problémába, de minden ötlet vagy már valahol fellelhető magyar nyelvű elméleti leírás, mely közelebb vihet a megoldáshoz érdekel és előre is köszönöm.

[2005] S:R.2015-02-24 20:44:44

Igaz, ez így nem jó.

Előzmény: [2004] Nagypapa, 2015-02-24 18:00:27
[2004] Nagypapa2015-02-24 18:00:27

Ez csak akkor igaz, ha különböző M-ekre MA+MB=állandó, a példában ez nem teljesül.

Előzmény: [2003] S:R., 2015-02-23 21:01:52
[2003] S:R.2015-02-23 21:01:52

Javítsatok ki, ha ez így nem korrekt, de én így csinálnám: Írjuk fel a számtani és mértani közép közötti egyenlőtlenséget az MA és MB szakaszok hosszára! A számtani közép >= mint a mértani közép, egyenlőség esetén minimális. Ez pedig akkor van, ha MA=MB. tehát az MA+MB összeg MA=MB-re minimális

Előzmény: [1999] epsilon, 2015-02-21 16:27:04
[2002] epsilon2015-02-21 19:22:13

Ok, köszi, értem, a tükrözési elv alapján tényleg nyilvánvaló.

Előzmény: [2001] Nagypapa, 2015-02-21 17:21:29
[2001] Nagypapa2015-02-21 17:21:29

Tükrözd pl. A-t e-re és a tükörképet kösd össze B-vel. A kapott M metszéspont létezik (miért), és MA+MB minimális, továbbá MA=MB is teljesül.

A bizonyítást Rád bízom.

Előzmény: [1999] epsilon, 2015-02-21 16:27:04
[2000] w2015-02-21 17:19:02

Tükrözd &tex;\displaystyle B&xet;-t az &tex;\displaystyle e&xet; egyenesre!

Előzmény: [1999] epsilon, 2015-02-21 16:27:04
[1999] epsilon2015-02-21 16:27:04

Üdv Mindenkinek! Lenne egy egyszerű geometria feladatom, amire egy egyszerű megoldást keresek:"Legyen A, B két rögzített pont a síkban, és egy e egyenes ami párhuzamos az AB egyenessel.(az e és AB közötti távolság rögzített). Legyen M az e egyenes egy változó pontja. Igazoljuk, hogy az MA+MB összeg akkor minimális, ha MA=MB."Olyan megoldás kellene, ami nem használ matematikai analízist, sem az izoperimetrikus tételek valamelyikét. Tudnátok-e segíteni? Előre is kösz, üdv: epsilon

[1998] jonas2015-02-20 22:02:52

Nem sok. Úgy nagyjából három ezrelék az esély, ha véletlenszerűen töltöd ki a szelvényt.

Előzmény: [1997] Bátki Zsolt, 2015-02-20 05:39:55
[1997] Bátki Zsolt2015-02-20 05:39:55

Korrekt. Az érdekesség, hogy bejön itt is az 'e' Az előzőhöz: Tippeltük: 3,6,43,55,61 Kihúzták 62,66,78,81,85 Mi az esélye, hogy a tippelt legnagyobbja, kisebb mint a kihúzott legkisebbje?

[1996] Róbert Gida2015-02-16 21:53:24

Legyen &tex;\displaystyle n=\binom{90}{5}&xet;, ekkor a valószínűség &tex;\displaystyle 1-(1-\frac{1}{n})^n&xet;, nagyjából &tex;\displaystyle 1-e^{-1}&xet;. (1988-as kérdésed pedig iszonyú pongyolán van feltéve).

Előzmény: [1995] Bátki Zsolt, 2015-02-15 23:16:02
[1995] Bátki Zsolt2015-02-15 23:16:02

A lottós feladat nem volt népszerű. Itt egy másik:

Mint tudjuk n=(90 alatt az 5) számú különböző tipp van. n= kb 43 millió.

Ha n darab szelvényt véletlenszerűen töltünk ki, akkor Mennyi a valószínűsége, hogy lesz benne 5-ös?

Az ötösök számának várható értéke, gondolom 1.

[1994] emm2015-01-26 19:43:20

Az csak konstans szorzóban változtat, általában &tex;\displaystyle a=2&xet;-t vagy &tex;\displaystyle a=e&xet;-t láttam használva.

Előzmény: [1993] Zilberbach, 2015-01-25 12:57:36
[1993] Zilberbach2015-01-25 12:57:36

Claude Elwood Shannon, az információelmélet megalkotója a következő egyenlettel írta le az információtartalmat: H = k·log¡a(1/p) ahol k a jelkészletből felhasznált jelek száma, p a jelkészletből 1 jel kiválasztásának valószínűsége, H az információtartalom. De honnan kapjuk meg a fönti képletben az "a"-t a logaritmus alapszámát?

[1990] emm2015-01-20 14:54:19

Szinbád és a háremhölgyek problémája. Első 12 oldalon kiszámolja a siker valószínűségét, és hogy az tényleg optimális stratégia :)

Előzmény: [1989] marcius8, 2015-01-20 11:21:47

  [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]