Hlavní navigace

Jak spočítat přeponu trojúhelníka

30. 5. 2011 9:27 (aktualizováno) | Josef Pavlík

Jak spočítat přeponu trojúhelníka? Zdánlivě banální otázka. Od Pythagorových dob je na ni poměrně jednoduchá odpověď. c2=a2+b2. Ovšem Pythagoras netušil, že odmocnina je pro malé procesory velký problém.

Při hraní si s firmwarem k reprapu jsem se dostal k zajímavému zjednodušení tohoto problému. Firmware totiž musí spočítat, jaká je vzdálenost, kterou musí ujet hlavička mezi body (x1,y1) a (x2,y2). Ve zdrojových kódech jsem našel tento zajímavý link: 

http://www.flipcode.com/ar­chives/Fast_Approximate_Dis­tance_Functions.shtml

V zásadě jde o náhradu Pythagorovského výpočtu přepony pouze sčítáním a násobením.
Trochu jsem tento výpočet upravil, abych dosáhl vyšší přesnosti při zachování jednoduchosti algoritmu.

Jako první operace se udělá absolutní hodnota souřadnic X a Y a porovná se, která souřadnice (t.j. strana trojúhelníka) je větší. Pokud je Y vetší než X, souřadnice se navzájem přehodí. Na délku přepony to samozřejmě nemá vliv, ovšem zaručili jsme, že jakákoliv kombinace souřadnic se transformuje na trojúhelník se úhlem menším nebo rovném 45 stupňům.

Pokud si zvolíme stranu X například 100 a stranu Y od 0 do 100, délka přepony jako funkce délky strany Y je křivka, která se dá poměrně úspěšně proložit dvěma přímkami se zlomem v polovině.
V následujícím kroku se tedy zjistí, jestli je strana Y menší než polovina strany X, to znamená, jestli je úhel menší než přibližně 27 stupňů a podle výsledku testu se použije jedna nebo druhá kombinace konstant pro výpočet délky přepony. Nakonec se připočítá 128 kvůli zaokrouhlování a zrotujeme 8 krát doprava, protože konstanty pro násobení jsou násobeny právě 256ti (reálně jsou všechny menší než 1).

Trochu jsem si pohrál s těmito konstantami a našel jsem hodnoty o které se s vámi chci podělit.

Celá funkce se dá napsat takto:

int32_t prepona(int32_t a, int32_t b)
{
  if (a<0) a=-a;
  if (b<0) b=-b;
  if (a<b) { int32_t x=a; a=b; b=x; } // make A greater than B
  if (a>(b<<1)) return (253*a+ 58*b+128)>>8;
  else          return (208*a+152*b+128)>>8;
}

Algoritmus používá pouze rotace, násobení a sčítání. Žádné dělení ani odmocňování není zapotřebí, takže je ideální pro mikrocontrollery. Přesnost algoritmu samozřejmě není závratná, ale pro žádný trojúhelník, který je dostatečně velký, aby se neprojevila chyba quantizace integeru, není chyba výpočtu větší než 1.5%, směrodatná odchylka je 0.66%.

Samozřejmě, že pokud bych počítal přeponu příliš malého trojúhelníka, například a=1, b=1, výsledek bude úplně mimo – bude 1 nebo 2, protože pracujeme s integery. V takovém případě ovšem stačí vynásobit obě souřadnice stejnou hodnotou, například 256 a dostaneme výsledek s maximální přesností algoritmu, samozřejmě zase vynásobený stejnou hodnotou, v tomto případě 256.

graf chyby při výpočtu délky přepony

Toto je graf chyby výpočtu v závislosti na poměru stran a,b.


Na základě komentářů a taky díky tomu, že jsem o problematice dále přemýšlel, ještě jsem algoritmus dále vylepšil.

Rozdělil jsem první polovinu na další 2 části. Výsledek má několik zajímavých vlastností.

  1. největší chyba se snížila na přibližně 0.6%, směrodatná odchylka je nyní 0.33%
  2. trojúhelník s nulovým úhlem = stav kdy hlavička jede horizontálně nebo vertikálně se vypočítává s absolutní přesností
  3. v případě, že má trojúhelník větší poměr stran než 1:4 se dokonce ušetří jedno násobení, protože konstanta pro stranu A je 256 (reálně 1.000000)

graf relativní chyby výpočtu přepony s upraveným algoritmem

A teď už konečně ten upravený program:

int prepona(int a, int b)
{
  if (a<0) a=-a;
  if (b<0) b=-b;
  if (a<b) { int x=a; a=b; b=x; }
  if (a>=(b<<2)) return a+((25*b+128)>>8);
  if (a>=(b<<1)) return (240*a+ 92*b+128)>>8;
  else           return (208*a+152*b+128)>>8;
}

Kdo si chce hrát, tady si může stáhnout tabulku kterou jsem používal na hledání koeficientů.

prepona-3parts.ods Musíš jenom přejmenovat file na cokoliv.ods. Musel jsem to nahrát jako obrázek png, protože tenhle blogovací site neumožňuje nahrát cokoliv jiného než obrázky. Na cokoliv jiného to vyhlásí, že je ten file nebezpečný. :-(