Endijs Posted October 7, 2008 Report Share 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ā? Link to comment Share on other sites More sharing options...
v3rb0 Posted October 7, 2008 Report Share 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 Link to comment Share on other sites More sharing options...
Endijs Posted October 7, 2008 Author Report Share 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 Link to comment Share on other sites More sharing options...
Kavacky Posted October 7, 2008 Report Share 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 Link to comment Share on other sites More sharing options...
Aleksejs Posted October 7, 2008 Report Share 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 :) Link to comment Share on other sites More sharing options...
Aleksejs Posted October 7, 2008 Report Share 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. Link to comment Share on other sites More sharing options...
Endijs Posted October 7, 2008 Author Report Share 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 Link to comment Share on other sites More sharing options...
bubu Posted October 7, 2008 Report Share 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. Link to comment Share on other sites More sharing options...
Roze Posted October 7, 2008 Report Share 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 Link to comment Share on other sites More sharing options...
v3rb0 Posted October 7, 2008 Report Share 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 Link to comment Share on other sites More sharing options...
Recommended Posts