Endijs Posted October 7, 2008 Report Posted October 7, 2008 Esmu ticis līdz man īsti neatkožamam sortēšanas algoritmam. Proti - ir dotas virsotnes, kuras jāsakārto pulksteņrādītāja kustības virzienā. It kā atradu http://www10.dcccafe.com/ng/article.php?id...hics.algorithms algoritmu, bet ir gadījumi, kad man viņš nestrādā. Piemēram, ja punkti ir no Latvijas kontūrām. Viss ir normāli, līdz jāprecizē ir, piemēram, Rīgas līci. Tad tas algoritms iedomājas, ka punkts pie Jūrmalas ir nevis punkts pēc Kolkas, bet pēc Pāvilostas. Ir gadījumi, kad viss strādā kā vajag. Pieļauju, ka problēma ir centra punkta izvēlē. To izvēlos vienkarši noskaidrojot min+max/2 (gan pa X gan pa Y). Bet laikam Latvijas gadījumā tas īsti neder. Tad nu jautājums - ir kāds saprātīgs veids, kā punktus sakārtot pulksteņrādītāja kustības virzienā?
v3rb0 Posted October 7, 2008 Report Posted October 7, 2008 (edited) man liekas, ka centra x būs average(x1, x2 ... xn) un y savukārt average(y1, y2.. yn); nevis vidējais starp "maximālo" un "minimālo" punktu Edited October 7, 2008 by v3rb0
Endijs Posted October 7, 2008 Author Report Posted October 7, 2008 (edited) Arī tādu variantu biju iedomājies, bet tas nenostrādāja. Taču pamēģināšu vēlreiz. Ja nu iepriekš kaut ko ne tā uzrakstīju. Update: Pamēģināju vēlreiz - v3rb0 tavs variants neder. Visas cerības uz bubu, ka viņš kā spēļu koderis zinās šīs ģeometriskās lietas atrisināt :) Edited October 7, 2008 by Endijs
Kavacky Posted October 7, 2008 Report Posted October 7, 2008 (edited) sin & cos ir tavs draugs, nosakot lenķus ( arccos un arcsin, precīzāk ;) un tos jau sakārtot ir viegli. Edited October 7, 2008 by Kavacky
Aleksejs Posted October 7, 2008 Report Posted October 7, 2008 Es laikam uzdevumu formulētu šādi: 1) Atrast smaguma centru. 2) pārvērst polārajās koordinātās visu punktu koordinātas. 3) sasortēt pēc leņķa φ 4) optimizēt 1-3 soli :)
Aleksejs Posted October 7, 2008 Report Posted October 7, 2008 Vēl var apsvērt soli - pārveidot oriģinālo daudzstūri par izliektu daudzstūri un tad veikt manis minētos soļus.
Endijs Posted October 7, 2008 Author Report Posted October 7, 2008 Tagad nožēloju, ka ģeometriju nemācijos tik cītīgi kā vajadzēja. Skatos uz tām figūrām, leņķiem un netopu gudrs. Laikam ka jau nav tādas domāšanas tad nav. Bet neko darīt - vajadzēs vai nu pazīlēt vai arī uzmeklēt kādu funkciju. Domāju, ka jābūt kaut kam +- gatavam jau.. tikai kur šams slēpjas :D
bubu Posted October 7, 2008 Report Posted October 7, 2008 Kautkas šāds neder? http://geometryalgorithms.com/Archive/algo...orithm_0109.htm Bet vispār Alekseja teiktas man šķiet pietiekami prātīgs algoritms. Leņķa dabūšana vektoriem (no smaguma centra līdz taviem dotajiem punktiem) ir diezgan vienkārša - atan2(y,x), kur y un x ir vektora komponentes.
Roze Posted October 7, 2008 Report Posted October 7, 2008 Jautājums - kāpēc kaut kas tāds ir vajadzīgs - Proti tā sortēšana? Lai zīmētu kaut poligonus (u.c. darbības)? Tad faktiski imho to ir vienkāršāk darīt jau ar gatavām geo fīčām un konkrēti MapScript piemēram ( http://www.maptools.org/php_mapscript/ ) -> http://www.maptools.org/php_mapscript/inde...lass-guide.html
v3rb0 Posted October 7, 2008 Report Posted October 7, 2008 (edited) ar atan2() un vidējo punktu ar average sanāca šitā http://paste.php.lv/8131?lang=javascript Edited October 7, 2008 by v3rb0
Recommended Posts