Toto je starší verze dokumentu!

Tomu, komu přišel ten Felkelův návod na binární vyhledávání trochu zmatený a nesrozumitelný, posílám vícuc z naší vzájemné korespondence, kde to vysvetlil trochu vice polopaticky. Snad to někomu pomůže.

Felkel napsal:

1. spočítáte si extrémní bod ze všech zadaných bodů - bude určitě ležet v jedné z podmnožin, ale to není teď podstatné

2. pro každou podmnožinu si vypočítáte KO a uložíte si ji, tj. její body si nastrkáte do vektoru (já si udělal vektor referencí na tyto vektory s konvexními obálkami)

Pro další postup tedy znáte několik „malých“ KO a startovací bod (který patří jedné z nich)

Pak ke každé malé KO najdete tečný bod procházenící bodem start. To uděláme binárním vyhledáváním - viz dále. Z těchto tečen (jedna na každou malou KO) vyberete tu, která bude mít nejmenší CCW úhel otočení. Při hledání nejmenšího úhlu porovnáváte vzájemně dvojice tečen pomocí ch_traits.less_rotate_ccw_2 - viz poslední stránka typů, kde z tečen PR a PQ vyberu PQ. Jakoby zapíchnete konec polopřímky do bodu start a otáčíte jí proti směru hod ručiček (CCW). Hledáte takový tečný bod, do kterého narazí tato polopřímka jako první.

Nalezený tečný bod přidáte do výsledné KO. Posunete start do právě nalezeného bodu a jedete znova, dokud nevyčerpáte počet pokusů a nebo nedorazíte zpět do bodu start.

To je převyprávěný Chanův algoritmus z přednášek

A teď ten problém - jak najít tečný bod pro malou KO, když mám zakázáno její body sekvenčně projít? Binárním vyhledáváním.

V prvním kroce označím jako L bod z s indexem 0 a jako bod R bod s indexem m-1, kde m je počet bodů malé KO. To je singulární případ, kdy rozdělíme celou malou KO na dvě části.

      1. Ta od bodu R k bodu L (postupuji CCW po vrcholech malé KO) obsahuje jen jedinou orientovanou úsečku - a to RL
      2. Ta druhá od bodu L k bodu R obsahuje všechny body KO, resp všechny úsečky malé KO kromě úsečky RL.

Já potřebuji zjistit, jestli není hledaným tečným bodem buď L, nebo R. To by znamenalo, že tečný bod leží v té první malinkaté části Pokud to není ani L, ani R, znamená to, že je hledaný tečný bod někde mezi R a L, tj. na 2. části malé KO.

Algoritmus tedy pokračuje dál, pokud tečný bod leží ve 2. oblouku

A teď klasické půlení. Rozdělím si ten dlouhý oblouk bodem M na dvě půlky LM a MR a zjistím, ve které z nich tečný bod leží - viz kapitola 2. v tipech.

Pokud leží v části mezi L a M, zahodím oblouk MR a rozpůlím LM (vypočtu novou pravou mez R = M-1 a pak nový bod M v půlce mezi L a R) To dělám tak dlouho, dokud není oblouk moc krátký - pro krátký umím určit výsledek - to je ta moje délka 7 bodů…