Volba vhodného algoritmu

LadislavBöhm

Volba vhodného algoritmu
« kdy: 13. 04. 2014, 14:54:58 »
Ahoj,

nejsem profesí programátor, ale v jednom hobby projektu řeším volbu vhodného algoritmu. Mám dvě množiny bodů v kartézské soustavě souřadnic o dvou osách (X a Y). Poloha každého bodu je tedy určena hodnotou X a Y. Potřebuji najít dva nejbližší body těch množin.

Jednoduchý náčrt vypadá takto:



Zatím to dělám metodou brute-force, protože bodů je málo, ale chtěl bych zvolit něco, s menší složitostí. Jaký algoritmus mám použít? Pokud je to relevantní, píšu to v C#.

Díky



Re:Volba vhodného algoritmu
« Odpověď #2 kdy: 13. 04. 2014, 15:51:25 »
mne tak z hlavy napada vyuziti R-stromu na indexovani oblasti abych porovnaval pokud mozno pouze blizke body

LadislavBöhm

Re:Volba vhodného algoritmu
« Odpověď #3 kdy: 13. 04. 2014, 16:06:22 »
Tak jsem studoval a zapomněl jsem přidat důležitou informaci, že ty dvě množiny tvoří konvexní polygon.

Původní obrázek je tedy nepřesný, správně ten problém vypadá takto:

karel

Re:Volba vhodného algoritmu
« Odpověď #4 kdy: 13. 04. 2014, 16:25:45 »
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.


karel

Re:Volba vhodného algoritmu
« Odpověď #5 kdy: 13. 04. 2014, 18:23:31 »
 - No ono bude hodně záviset složitost, správnost a rychlost výpočtu na předpokladech, kde ty body jsou :-)) - jaká je jich "souvztažnost", pravděpodobost výskytu ap. kriteria, abychom si usnadnili práci. No to těžiště byl jenom jeden z nástřelů a vidím, že jsou i takové situace, kdy mě to odvede od správného řešení... No možná díky konvexnosti, skrytým hranám co nepůjdou vidět z těžišť na protilehlé množině (promítnutí 'světla'); bodů co mají blíže k těžišti druhé množiny než ke své množině <--> především tudy bych se asi ubíral (ale už znovu tuším, že najdu vyjímky ve své úvaze) Ale ta konvexnost je krásná... Kruci, analogový počítač, průtok kapalinou, největší tlak, rychlost,..., anebo kde nám prskne výboj...

andy

Re:Volba vhodného algoritmu
« Odpověď #6 kdy: 13. 04. 2014, 20:14:02 »
Vhodneho algoritmu znamena presne co? Z hladiska vypoctoveho, pamatovej narocnosti... ?

LadislavBöhm

Re:Volba vhodného algoritmu
« Odpověď #7 kdy: 13. 04. 2014, 21:18:48 »
Jde mi spíše o výpočtovou náročnost, jak jsem psal, zatím mi to funguje na brute-force přístupu, který je v tomhle ohledu to nejhorší. Proto hledám lepší variantu.

anonym

Re:Volba vhodného algoritmu
« Odpověď #8 kdy: 14. 04. 2014, 03:34:34 »
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.

precet sem si problem a napadnul me +- stejny algoritmus, tehle prizpevek sem cetl az kdyz sem to mel sepsane ;)

slozitost mi vysla NlogN pro prumerny/idealni pripad, N^2 pro nejhorsi (tedy ze pri kazdem odriznuti zabiju jen 1 vrchol)

je tu ale otazka - hledame nejblizsi body polygonu, nebo nejblizsi vrcholy? je mozne ze nejblizsi body budou tak ze to je vrchol-bod na hrane.
situace bod na hrane - bod na hrane by nemela nikdy nastat (krom specialniho pripadu kdy nejblizsi hrany jsou rovnobezne, ale pak existuji 2 pary vrchol-vrchol se stejnou vzdalenosti)

najit pripady vrchol-hrana by melo u konvexniho byt jednoduche, myslim ze bude stacit najit nejblizsi vrcholy, a pak zkontrolovat k nim sousedici hrany (zadna jina by nemela byt kandidat), to tak ze kolmice na hranu skrz vrchol z druhe mnoziny, prusecik je kandidat na nejblizsi bod

Re:Volba vhodného algoritmu
« Odpověď #9 kdy: 14. 04. 2014, 09:03:28 »
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.

To podle mne nebude fungovat, pokud budou nějaké body daleko od těžiště.
Kód: [Vybrat]
.....   |   .....
        |
        |
        |
       .|.
Tady jsou si nejbližší evidentně ty dva body dole, ale jakmile budete počítat s těžištěm, vyloučíte je.

gamer

Re:Volba vhodného algoritmu
« Odpověď #10 kdy: 14. 04. 2014, 09:15:21 »

anonym

Re:Volba vhodného algoritmu
« Odpověď #11 kdy: 14. 04. 2014, 09:17:30 »
To podle mne nebude fungovat, pokud budou nějaké body daleko od těžiště.
Kód: [Vybrat]
.....   |   .....
        |
        |
        |
       .|.
Tady jsou si nejbližší evidentně ty dva body dole, ale jakmile budete počítat s těžištěm, vyloučíte je.

neni pravda, alespon v tomhle pripade (a variacich)

ty rezny roviny budou rovnobezny s tou delici primkou, tedy asi takhle

Kód: [Vybrat]
...|..   |   ..|...
   |     |     |
   |     |     |
   |     |     |
   |    .|.    |

zajimavejsi pripad je kdyz jeden polygon otocis vzhuru nohama:

Kód: [Vybrat]
.....  | .
       |
       |
       |
     . |  .....

pak ti vznikne neco takovehohle, coz porad funguje:

Kód: [Vybrat]
.../.  | .
  /    |      /
 /     |     /
/      |    /
     . |  ./....

teziste tady dava dve vlastnosti - je uvnitr polygonu (a snadno vypocitatelne), a pri rezu odebere cca polovinu vrcholu. pro korektnost je AFAIK potreba jen prvni vlastnost, pro slozitost NlogN druha

Re:Volba vhodného algoritmu
« Odpověď #12 kdy: 14. 04. 2014, 09:43:36 »
neni pravda, alespon v tomhle pripade (a variacich)

ty rezny roviny budou rovnobezny s tou delici primkou, tedy asi takhle
Aha, omlouvám se, špatně jsem pochopil, kde budou ty kolmice na spojnici těžišť.

anonym

Re:Volba vhodného algoritmu
« Odpověď #13 kdy: 15. 04. 2014, 01:09:22 »
neni pravda, alespon v tomhle pripade (a variacich)

tak sem si nakonec nalezl protipriklad, teda pokud tazatel chce nejblizsi vrcholy (tedy ne body na hranach)

Kód: [Vybrat]
.          |.
           |
           |
           |
          .|   .
           |
           |
           |
.          |.

nejblizsi vrcholy v tomhle pripade jsou ty nejvic vpravo u obou polygonu, ale metoda rezani pres stred by je nenasla (co by nasla je nejblizsi par vrchol-bod na hrane, ale k tomu taky muze byt protipriklad)

karel

Re:Volba vhodného algoritmu
« Odpověď #14 kdy: 15. 04. 2014, 23:08:31 »
Nevím, jestli už je dobojováno a hledači našli co hledali... a úkol je splněn, nebo nikoliv. Proto se vrátím k mojí myšlence a zkusím ji rozvést (jenom ji jsem "schopen" sledovat :-)) a poprosil bych vás o posouzení.  Co a jak vidím já: 1) Konvexnost - stěžejní, ulehčující a umožňující práci s pomocnými konstrukcemi jako --> 2) Těžiště 3) Body tvoří obvod 'bubliny' (bubliny jsou konvexní...) 4) Každý Bod má svého nejbližšího partnera nalevo L a napravo R. Teď s těmi myšlenkami zatřeseme... a zkusíme algoritmizovat: 5) Vybereme náhodně dva body = jeden na jedné bublině a druhý na druhé. Označme je B1 a C1 6) Spočteme těžiště bublin - ozn. BT, CT. 7) Vypočtu vzdálenosti mezi B1 a C1 , mezi těžišti BT a CT. 8.)...(a teď třeba takto) vypočtu vzdálenosti mezi body po levici a pravici bodu B1a samotného bodu B1 <-vůči-> bodům levice a pravice C1a samotného C1. Získám takto 9 vzdáleností a vyberu z nich dvojici jež splňuje minimální vzdálenost do dalšího 'kola'. Pokud taková nová dvojice neexistuje, neboť původní (B1-C1) byla 'už' minimem, pak ... /zde mám možnost/nutnost! zapracovat ještě kritérium s těžištěm/ + /zde mám možnost/nutnost! zapracovat ještě kritérium, zda mezi body není stěna bubliny - s potenciálně bližšími body.../ <-- detekci nechám pro někoho jiného, anebo až se vyspím. Snad je alespoň 'lezení' po bublině, tj. práce se sousedy inovativní (neperspektivní body, řešení - zabít).