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