Posted By: TopGun (TopGun) on 'CZscience' Title: Re: Prumer konvexniho polygonu Date: Mon Jan 11 12:40:41 1999 > > potreboval bych algoritmus, ktery najde prumer konvexniho polygonu v > > rovine > > v linearnim case vzhledem k poctu vrcholu. (Prumer je vzdalenost > > nejvzdalenejsich vrcholu). Staci slovne popsat, nepotrebuju implementacni > > detaily. > > > A ja uz to vim :) > > Najde se vrchol s minimalni a maximalni y-ovou souradnici, temi se vedou > rovnobezky tak, aby byly kolme na spojnici techto vrcholu a pak se otaci > polygonem po smeru hodinovych rucicek tak, aby se vzdy jedne z rovnobezek > dotkl dalsi vrchol. Pak se spocita vzdalenost vrcholu, ktere se dotykaji a > vybere se z ni maximum. > > Koho to zajima, at si to rozmysli, nemam vic casu na podrobnosti. > > Gekon /----- Funguje to ?? A nezaabera ti to "otacanie privela casu ?? Neskusal som, ale napadlo ma nieco jednoduchsie: 1. Zober lubovolny vrchol. 2. Prejdi ostatnych N-1 a najdi najvzdialenejsi. Oznac ho X 3. Prejdi ostatnych N-2 a najdi najvzdialenejsi od X. Oznac ho Y. 4. XY by moohol byt priemer. Ale moznoze to nefunguje stale.. Keby hej, tak je to celkom dobry algoritmus. Viditelne ma narocnost (2N-3), cize linearna. BYe !! Zena - najlepsi priatel cloveka TopGun