  |
|
| ° Forum ° Rejestracja ° Szukaj ° | |
| Auto giełda ° wnętrzowe stacje transformatowe |
 |
Matma / srodek i pole okregu zawierajacego n punktow?? |
| << . 1 . 2 . 3 . |
| Autor | Wiadomość |
| bartekLTG
|
Posted: 8 Wrz 2008 17:54:31 Witam, prosilbym o mala pomoc. Problem polega na tym ze mam napiac program, ktory bedzie wczytywal wspolrzedne punktow a nastepnie bedzie znajdowal srodek i promien najmniejszego okregu zawierajacego te punkty. Znajduje punkty najbardziej oddalone od siebie, odcinek je łączący to średnica okręgu. Okazuje się, że problem jest znacznie bardziej skomplikowany, niż się na pierwszy rzut oka wydaje. Na szczęście ma znane rozwiązanie: http://www.delphiforfun.org/programs/circle_covering_points.htm http://en.wikipedia.org/wiki/Smallest_circle_problem Algorytm jest kwadratowy. Zawsze mozna najpierw wyznaczyc wypukla otoczke, wtedy mamy n log(n) + m^2 (m-puntktow w otoczce). Czy dla wypuklej otoczki nie da sie znalesc w czasie liniowym najwiekszej przekatnej? Jesli tak, to znajdujemy taka i od teraz, jesli nie pokrywamy wszystkich,bawimy sie tylko trojkami punktow. To oczywiscie tylko heurystyka i pesymistycznie nadal pozosteje m^2. A jakby punkty wybierac z otoczki w jakis szczegolny sposob, albo losowo? pozdr bartekltg |
| A.L.
|
Posted: 16 Wrz 2008 16:19:47 On Sat, 6 Sep 2008 13:52:00 -0700 (PDT), Smutny Witam, prosilbym o mala pomoc. Problem polega na tym ze mam napiac
program, ktory bedzie wczytywal wspolrzedne punktow a nastepnie bedzie znajdowal srodek i promien najmniejszego okregu zawierajacego te punkty. Hmmm jakies sugestie?/ Mnie chodzi cos po glowie ze mozna to zrobic jakos z regresji czyli znalesc taki punkt aby suma kwadratow odleglosci pomiedzy kazdym z punktow byla jak najmniejsza. Problem tylko w tym ze znalazlemw necie tylko wzory na regresje liniowa, a jak to zrobic z kolem?? No chyba zemacie jakis inny sposob, ale od razu mowie zepodstawienie wsplrzednych punktow do rownania okregu i rozwiazanie n rownan nie wchodzi w gre Ciekawe ze tylu specjalistow sie wypowiada w tym watku, a zadanemu nie chcialo sie pogoglowac. Problem jest znany od wiekow http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm http://valis.cs.uiuc.edu/~sariel/papers/03/min_disk/min_disk.pdf http://www.delphiforfun.org/programs/circle_covering_points.htm http://www.eng.clemson.edu/~pmdrn/Dearing/location/minimax.pdf i jeszcze 25 milionow innych ciekawych linkow A.L. |
| << . 1 . 2 . 3 . |