PC-HELP.CZ

Zdravím.
Máte určité bludiště- množinu bodů v rovině - definovaný střed těchto bodů a poloměr.
Jste uprostřed, opět definice střed, poloměr, a potřebujete se dostat ven nejkratší možnou cestou.

Jak vytvořit algoritmus?
Prosím případně o popis jak pro úplné trdlo, potrvá mi tomu porozumět.

Mockrát děkuji.

pudu jednou cestou, když nebude slepá tak pudu dál a budu se snažit jít pořád z kruhu
logický ne?

No tak to mi je celkem jasné... Ale horší je pro mě je to přenést do algoritmu. Matematiku zvládám, ale s tímhle nemám moc zkušeností, tak nevím, jaké funkce využít.

Ty body jsou místa kam můžeš skákat? Podle jakých pravidel? Kdyby to bylo libovolně, tak by stačilo najít bod ležící zvenku nejblíž tomu poloměru a skočit rovnou na něj! Takže Pythagorova věta:



Nebo je to naopak, že na ty body nesmíš vstoupit a musíš prokličkovat mezi nimi?

Nene, nejspíš jsem to špatně popsala... Neskákat, ale prokličkovat :-) Vymanipulovat se mezi nimi, žádné nějaké "naklánění" apod.

Takže ty body jsou různě velká "kolečka", a ty musíš s dalším kolečkem mezi nimi nějak projet ven. Teď to mám správně?

Ano, přesně takto to myslím :-) A pokud možno nejkratší možnou cestou.

Tak zjistit jestli projdeš mezerou nebude tak těžké, ale vymysli jak spočítat délku té dráhy včetně obloučků:

Asi by bylo jednodušší přičíst poloměr toho utíkajícího bodu ke všem ostatním a pohybovat se po tečnách.

A další otázka - jak poznám že už jsem "venku" z toho bludiště?

Ještě dodám, že věc se má tak, že překážky mohou mít různý poloměr... Ale to snad nebude problém?

K otázce... Sama nevím. Nejspíš jen najít algoritmus, tak se z toho "vydrápat".

Různý poloměr nevadí, stejně se ty puntíky budou zpracovávat postupně. Tak postup bych navrhoval asi takhle:

1. K poloměru všech překážek přičíst poloměr toho cestovatele. Šlo by to i během hledání, ale je to počítání navíc, a složitější vzorečky. Takhle pak stačí pracovat s bodem s nulovou velikostí.

2. Z výchozího bodu brát postupně všechny překážky, a k nim vypočítat tečny k součtu průměrů (pozor, každá má dvě!).

3. Pokud tečna neprotíná žádnou jinou překážku (zase oba průměry), tak se hledá společná tečna k další překážce (rekurze na bod 2.), dokud se cestovatel nedostane na hranici N-úhelníku vytvořeného středy všech překážek. To je ta černá čára kolem.

4. V tu chvíli kdy je na hranici (průnik kružnice se spojnicí středů) se sečtená délka dráhy porovná s nejkratší doposud nalezenou, a pokud je kratší, tak se nahradí.

Ale jak tohle všechno spočítat se mě fakt neptej, kdysi na střední jsme nějaké protínání počítali, ale to je asi tak všechno co si z toho pamatuji
Ta dráha by se dala ukládat do pole nebo do spojového seznamu.

Zapomněl jsem jednu důležitou věc, takže:

5. Když dojdeš na hranici, nebo do slepé uličky, tak se vrátíš o jednu úroveň zpátky a vyzkoušíš další tečnu, tak dlouho dokud tam nějaké neotestované jsou.

Nakonec, po vyčerpání všech možností, budeš zase stát na výchozím bodě, a budeš mít zaznamenanou nejkratší možnou cestu na hranici té plochy. Pokud bude víc stejně dlouhých, tak jen tu první nalezenou.