abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 11:55 | Komunita

Vývojový tým OpenSSL ve spolupráci s iniciativou Core Infrastructure konsorcia Linux Foundation spustil proces přelicencování této kryptografické knihovny ze současné licence na licenci Apache Licence v 2.0 (ASLv2). Nová licence usnadní začleňování OpenSSL do dalších svobodných a open source projektů. Všichni dosavadní vývojáři OpenSSL (Authors) obdrží v následujících dnech email s prosbou o souhlas se změnou licence.

Ladislav Hagara | Komentářů: 5
dnes 01:11 | Komunita

Před třemi týdny Mozilla.cz představila projekt Photon, jehož cílem je návrh a implementace nového vzhledu Firefoxu. Včera zveřejnila první náhled vzhledu Photon. Práce na projektu Photon jsou rozděleny do pěti týmů, které celkem čítají 19 lidí. Zaměřují se na zlepšení prvního spuštění Firefoxu a zaujetí nových uživatelů, celkovou úpravu vzhledu, zlepšení animací, zrychlení odezvy uživatelského rozhraní a také upravení nabídek. Vývoj lze sledovat v Bugzille.

Ladislav Hagara | Komentářů: 13
včera 20:00 | Komunita

OneDrive pro firmy je již ve webových prohlížečích na Linuxu stejně rychlý jako na Windows. Microsoft opravil chybu z listopadu loňského roku. OneDrive pro firmy běžel na Linuxu mnohem pomaleji než na Windows. V popisu chyby bylo uvedeno, že stačilo v prohlížeči na Linuxu nastavit v user-agentu Windows a vše se zrychlilo. Odpovědí Microsoftu bylo (Internet Archive: Wayback Machine), že Linux není podporován. Po bouřlivých diskusích na redditu i Hacker News byla chyba nalezena a opravena.

Ladislav Hagara | Komentářů: 4
včera 19:00 | Zajímavý projekt

Byla vyhlášena soutěž Hackaday Prize 2017. Soutěž je určena vývojářům open source hardwaru. Pro výherce je připraveno celkově 250 tisíc dolarů. Každý ze 120 finalistů získá tisíc dolarů. Nejlepší pak navíc 50, 30, 20, 15, 10 a 5 tisíc dolarů. Jedná se již o čtvrtý ročník soutěže. V roce 2014 zvítězil projekt globální sítě open source pozemních satelitních stanic SatNOGS. V roce 2015 zvítězil open source systém pro řízení elektrických invalidních vozíků pohybem očí Eyedriveomatic. V roce 2016 zvítězil modulární robot Dtto.

Ladislav Hagara | Komentářů: 0
včera 15:00 | Bezpečnostní upozornění

Byla vydána Samba ve verzích 4.6.1, 4.5.7 a 4.4.12. Řešen je bezpečnostní problém CVE-2017-2619. Pomocí symbolických odkazů a souběhu (symlink race) lze "teoreticky" získat přístup k souborům, které nejsou sdíleny. Linuxové distribuce jsou postupně aktualizovány (Debian).

Ladislav Hagara | Komentářů: 0
včera 07:43 | Nová verze

Na Steamu se objevil port hry Arma: Cold War Assault (Operation Flashpoint) pro Mac a Linux. … více »

creon | Komentářů: 28
včera 05:55 | Nová verze

Po 18 měsících od vydání verze 8.0 byla vydána verze 9.0 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab. Představení nových vlastností v příspěvku na blogu a na YouTube.

Ladislav Hagara | Komentářů: 0
včera 03:33 | Komunita

Platnost posledního patentu souvisejícího s Dolby Digital (AC-3) vypršela. Po MP3 se tak do Fedory oficiálně dostane také kodek AC-3.

Ladislav Hagara | Komentářů: 5
včera 00:44 | Komunita

Feral Interactive, společnost zabývající se vydáváním počítačových her pro operační systémy macOS a Linux, nabízí své hry na Steamu vývojářům open source 3D grafické knihovny Mesa zdarma. Podmínkou je minimálně 25 commitů za posledních 5 let. Stejnou nabídku dostali vývojáři knihovny Mesa v roce 2015 od Valve. O rok dříve dostali od Valve tuto nabídku vývojáři Debianu a Ubuntu.

Ladislav Hagara | Komentářů: 0
22.3. 23:55 | Nová verze

Opera 44, verze 44.0.2510.857, byla prohlášena za stabilní. Nejnovější verze tohoto webového prohlížeče je postavena na Chromiu 57. Z novinek vývojáři Opery zdůrazňují podporou Touch Baru na nejnovějších MacBoocích Pro (gif). Přehled novinek pro vývojáře na blogu Dev.Opera.

Ladislav Hagara | Komentářů: 1
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (14%)
 (2%)
 (72%)
 (3%)
 (10%)
Celkem 926 hlasů
 Komentářů: 72, poslední 1.3. 11:16
    Rozcestník

    Dotaz: Algoritmus pro vyhledání nejkratší vzdálenosti

    8.7.2009 13:45 Deleted [8409] | skóre: 14 | blog: darkblog
    Algoritmus pro vyhledání nejkratší vzdálenosti
    Přečteno: 1226×

    Ahoj,

    nevím jak efektivně řešit tento problém. Mám pole bodů, a potřeboval bych funkci, která by co nejefektivněji našla nejkratší vzdálenost pro danou pozici. Naprosto triviálně to lze řešit lineárním prohledáváním, ale to je z hlediska výkonu nepoužitelné. Pro lepší porozumění předložím malý prototyp, kterým bych chtěl lépe vysvětlit, o co mi jde:

    struct DistancePoint
    {
      double x, y;
    };
    
    struct DistanceFinder
    {
      DistanceFinder();
      ~DistanceFinder();
    
      bool init(const DistancePoint* p, int count);
      void free();
      double find(double inX, double inY);
      void findSpan(double x, double y, int count, double* results);
    
      DistancePoint* _data;
      int _count;
    };
    
    DistanceFinder::DistanceFinder() :
      _data(NULL)
    {
    }
    
    DistanceFinder::~DistanceFinder()
    {
      free();
    }
    
    bool DistanceFinder::init(const DistancePoint* p, int count)
    {
      free();
      if (!count) return false;
    
      _data = (DistancePoint*)malloc(count * sizeof(DistancePoint));
      if (!_data) return false;
    
      memcpy(_data, p, count * sizeof(DistancePoint));
      return true;
    }
    
    void DistanceFinder::free()
    {
      if (_data) { ::free(_data); _data = NULL; }
    }
    
    double DistanceFinder::find(double x, double y)
    {
      double dist = fabs((_data[0].x - x) * (_data[0].y - y));
    
      for (int i = 1; i < _count; i++)
      {
        double d = fabs((_data[i].x - x) * (_data[i].y - y));
        if (dist > d) dist = d;
      }
    
      return sqrt(dist);
    }
    
    

    a teď stručně charakteristiku a pár typů k optimalizaci:

    • množství bodů se po initializaci nebude měnit, init() tedy má možnost vytvořit a inicializovat další datové struktury potřebné k hledání (binární stromy, atd).
    • protože to chci použít v počítačové grafice, jedna z optimalizací může využít fakt, že budu potřebovat hledat vždy pozice, které mají stejnou Y souřanici a na ose X budu přičítat 1.0.
    optimalizace tedy může využít potřeby pro tuto funkci:
    void DistanceFinder::findSpan(double x, double y, int count, double* results)
    {
      for (int i = 0; i < count; i++, x += 1.0) 
        results[i] = find(x, y);
    }
    

    Tak co, věděl by někdo, jakým směrem mám jít? Potřeboval bych vědět, jaké nejlepší datové struktury a algoritmy volit pro vytvoření dat, které použiju k efektivnímu vyhledání. Budu používat metodu findSpan(), takže samotná find() není vůbec důležitá.

    Chtěl bych to použít na generování podobných obrázků jako tyto.

    Odpovědi

    8.7.2009 14:33 saslik
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Jako trivialni reseni se  mi jevi, ze bych si nad mnozinou bodu vytvoril dva indexy dle souradnic x a y a s jejich pouzitim pak hledal metodou okenka. Napr. nejprve v kruznici o polomeru a, pak a*1,5 apod. Inspiraci pro lepsi reseni mohou byt struktury jako quadtree nebo R-tree.

    stativ avatar 8.7.2009 14:53 stativ | skóre: 54 | blog: SlaNé roury
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti
    Já bych z toho vytvořil váhovou matici sousednosti přičemž bych předpokládal, že body tvoří úplný graf (všechny jsou spojeny se všema) a pak zkusil třeba Dijkstru nebo Floyda.
    Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
    8.7.2009 15:29 petr_p | skóre: 59 | blog: pb
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Matice sousednosti vytvoří kvadratické množství hran. Dijkstra má složitost O(E+V.log(V)), tedy složitost by byla kvadratická. To naivní prohledání je lineární ;)

    Navíc Dijkstra je moc obecný. Tady si můžeme dovolit počítat s tím, že vzdálenosti bodů respektují topologii (tedy pokud se pohybujeme v Euklidovském prostoru). Například navržené kvarterní stromy jsou použitelné (používá to třeba Google na svých mapách).

    Ono obecně hledání ve vícerozměrných strukturách je ošklivé a moc se toho nedá ulehčit. Většina GISových algoritmů předpokládá nějaké zjednodušení, které umožní preferovat jeden směr (třeba autor říká, že bude hledat jen ve směru osy), na kterém se vybuduje efektivní vyhledávací struktura a vedlejší veličiny se pak už neohrabaným způsobem navěsí na její listy.

    8.7.2009 15:01 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Nevím, jestli jsem to dobře pochopil. Máš neprázdnou množinu bodů M a úsečku mezi body [a, y] a [b, y], kde a<b. A pro určité body úsečky [z, y] chceš určit vzdálenost k nejbližšímu bodu z množiny M?

    Budu předpokládat (možná špatně), že tě zajímají pouze vybrané hodnoty y např. 0, 1, 2, 3, ... A těch hodnot, které tě zajímají není mnoho. Potom pro každé y, které tě zajímá, můžeš spočítat intervaly na ose x [u1, u2], [u2, u3], [u3, u4],... takové, že pro každý bod [x,y], kde x je z intervalu [u(i), u(i+1)], bude nejbližší bod p(i).

    Příklad: Tedy pokud máš množinu M se dvěma body p(1)=[0, 1] a p(2)=[2, 1], a zajímá tě y=0, pak si předem spočítáš intervaly [-nekonečno, 1], [1, nekonečno] a pro každou úsečku mající y=0 víš, že pro každý bod s x <= 1 je nejbližší bod p(1) a pro x >= 1 je nejbliží bod vždy p(2).

    Tedy časová složitost je pro celou úsečku O(log n +count). Předzpracování nepočítám.

    8.7.2009 15:46 volca
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Podle me by mohl pomoci vyvazeny BSP strom. Liche body budou rezat 2d prostor horizontalne, sude vertikalne. Find potom bude traverzovat podle uzlu, vzdy vybere tu polovinu prostoru na ktere sedi hledany bod (a zapamatuje nejkratsi vzdalenost) - body v druhe polovine prostoru jsou urcite dal.

    Jde jen o to vyvazit ten BSP strom, aby v kazdem uzlu byla velikost obou vetvi srovnatelna.

    8.7.2009 16:05 volca
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    A sakra, jak ted o tom premyslim tak by to nefungovalo. Ty delici primky musi byt v polovine mezi dvema body, nikoli skrze body samotne...

    AraxoN avatar 8.7.2009 16:14 AraxoN | skóre: 45 | blog: slon_v_porcelane | Košice
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    BSP podľa osí ma tiež napadlo ako prvé, ale nerieši to podmienku najmenšej vzdialenosti od hľadaného bodu.

    Dotaz ma ale inšpiroval do tej miery, že idem kúpiť pravítko, trojuholník, ceruzky, kružidlo a papiere a večer nad tým budem bádať :-D

    A fine is a tax for doing wrong. A tax is a fine for doing well.
    8.7.2009 16:27 volca
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Hodne stesti :)

    Podle me to podle os nepujde, ale pujde to jako kolmice na spojnici dvou bodu v jejim stredu (ekvidistanta tech dvou bodu). Ta primka potom opravdu deli prostor na body blize bodu A a/nebo B. To vyvazovani by slo bud brute-force, tim ze se najde takova dvojice, jejiz delici cara produkuje pomer bodu na obou stranach co nejblizsi jednicce, nebo by mozna sel ten strom i zoptimalizovat po naivnim vybudovani - to vyvazovani bude obecne vetsi problem nez vystaveni toho stromu jako takoveho - coz je celkem jednoducha operace.

    Co se tyce toho dotazu, tam je zajimave ze by mozna slo snadno zoptimalizovat prochazeni tim, ze se bude predavat cela mnozina bodu (ve forme usecky). Usecka se potom bude delit ve dvi v kazdem uzlu - vzniknou segmenty se stejnou prislusnosti k nejblizsimu bodu po protlaceni vsech segmentu do listu :)

    AraxoN avatar 8.7.2009 16:36 AraxoN | skóre: 45 | blog: slon_v_porcelane | Košice
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Operácia zistenia toho, na ktorej strane priamky leží bod je (ak si dobre pamätám) triviálna - dosadia sa súradnice bodu do rovnice priamky ax+by+c a ak je výsledok kladný, tak to leží na jednej strane (ľavý podstrom), ak záporný tak na druhej (pravý podstrom) a ak rovný nule, tak bod leží na priamke (to by sa priradilo ku jednému z podstromov). Takže by z hľadiska výpočtovej zložitosti ani veľmi nevadilo, že priestor nebude delený podľa osí X a Y...

    A fine is a tax for doing wrong. A tax is a fine for doing well.
    9.7.2009 07:50 volca
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Tak po dalsim zamysleni musim odvrhnout myslenku ze to jde po segmentech - kazdy bod se musi resit zvlast. Podle os to samozrejme lze taky resit (kd-tree), ten prohledavaci algoritmus zkratka hleda nejkratsi bod do hloubky a neprechazi prez rozdelujici primku co je dal nez aktualni nejlepsi kandidat...

    AraxoN avatar 9.7.2009 09:42 AraxoN | skóre: 45 | blog: slon_v_porcelane | Košice
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Tu nižšie v diskusii je odkaz na wikipediu (Voronoi diagram) a sú k tomu aj algoritmy. Spomína sa tam zložitosť O(n.log(n)), čo mi pripadá o dosť lepšie než to nad čím som uvažoval ja :-( ... ale aspoň som sa trochu precvičil v rysovaní a som zásobený písacími pomôckami na 10 rokov dopredu! :-D

    A fine is a tax for doing wrong. A tax is a fine for doing well.
    8.7.2009 16:43 xnov22
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti
    8.7.2009 17:27 Ivan
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    Hmm nevim jestli je to pro tvoji ulohu optimalni alg. Ale predtav si nasledujici situaci:

    1. mame nakonecne veliky ctverec(koren stromu)

    2. Vlozime do nej jeden bod -> ctverec se rozdeli na 4 pod-ctverce. Tyto pod-ctvrce jsou synove korene.

    3. Mame dalsi bod. Projdeme koren, najdeme spravneho syna, a do nej vlozime dalsi bod a rozdelime ho na 4 syny

    Pokud svoje body rozume nahodne zamichas, tak dostanes strom, ktery projdes log. case. Podobny alg. se pouziva pro reprezentaci map, akorat se misto bodu pouzivaji usecky.

    Ivan

     

     

    8.7.2009 18:48 petr_p | skóre: 59 | blog: pb
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti
    A říká se tomu kvarterní strom.
    9.7.2009 09:53 tomfi | skóre: 19
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti

    A není právě řešení toho problému to co je na tom nejlepší, nejzáživnější? ... samotné naprogramování už je pak nuda.

    Vždyť jsou to jen jedničky a nuly ...
    9.7.2009 14:34 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: Algoritmus pro vyhledání nejkratší vzdálenosti
    Takže díky všem za reakce. Něco jsem zkoušel, ale zdá se mi, že chci řešit problém jiným způsobem, než by se měl řešit. Chci generovat výplň, která je definovaná jako grafická cesta (v GDI+ je to PathGradientBrush), tak mě napalo vygenerovat body té cesty, pak hledat ten nejbližší a podle toho přiřadit pixelu barvu (podle gradient lut tabulky). Jenže tento způsob je asi overkill a řešit se to dá pomocí trojúhelníků.

    Jinak pomocí nejkratší vzdálenosti se mi líbí ty Voronoi diagramy, myslím, že by to krásně sedlo na hledání pole hodnot, ale stejně to budu řešit s největší pravděpodobností pomocí těch trojúhelníků.

    Kdyby někdo věděl i jiný způsob, rád se nechám poučit. Kdybych měl upřesnit problém, tak já hledám nejkratší vzdálenost k úsečkám (tedy grafické cestě složené z úseček), ale měl jsem pocit, že jednodušší by bylo převést to na body a jen hledat nejkratší vsdálenosti k nim.

    Založit nové vláknoNahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.