Регистрирайте сеРегистрирайте се

Определяне последователността на точки съставляващи контур


 
   Форум за математика Форуми -> Kомпютърни изчисления
Предишната тема :: Следващата тема  
Автор Съобщение
carnophage
Начинаещ


Регистриран на: 10 May 2009
Мнения: 2


МнениеПуснато на: Sun May 10, 2009 7:15 pm    Заглавие: Определяне последователността на точки съставляващи контур

Здравейте, имам следния въпрос:

Имам затворена фигура с неправилна форма (представете си очертания на различни континенти страни и т.н. всякакви обекти) като знам точното положение в координатната система на всяка една точка съставяща ограждащата линия (линията е пикселна, демек знам положението на всеки пиксел в линията). Проблемът е, че точките не са подредени последователно, ето картинка, която грубо илюстрира 'последователността':



Въпросът е как мога да подредя точките в тази последователност?

Съжалявам, ако това не е правилната секция от форума за въпроса ми, кажете коя е правилната и ще преместя темата там.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Sun May 10, 2009 8:10 pm    Заглавие:

Ето моята идея:
1. Хващаш една произволна точка и и слагаш номер 1.
2. Намираш разстоянието между тази точка и останалите, това разстояние се намира по формулата [tex]\Del r=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}[/tex], където х1, х2, у1 и у2 са координатите на две точки, които сравняваш. След като намериш всички тези разстояния избираш най-малкото от тях и по този начин намираш точка номер 2.
3. Продължаваш по същата процедура като не взимаш на предвид вече номерираните точки.

Така би ли станало?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Fed
VIP


Регистриран на: 24 May 2007
Мнения: 1136
Местожителство: София (Русе)
Репутация: 113.3
гласове: 33

МнениеПуснато на: Sun May 10, 2009 9:36 pm    Заглавие:

Не...не става така, представи си (че не ми се рисува) лъжица, избери 1 да е краят на дръжката (краят, който е откъм по-обемната част на лъжицата). Тогава 2 ще е срежуположната точка спрямо оста на симетрия...а не трябва да е тя. Ако не си разбрал утре ще напиша по-ясно, че сега трябва да лягам, че имам влак в 6 Laughing . Правилният алгоритъм за този случай не е толкова лесен, колкото предложеното от теб, но не е и труден. Мисля, че ще го разбереш. Погледни тук: http://fmi.wikidot.com/okg10
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Sun May 10, 2009 10:34 pm    Заглавие:

Fed, май нещо не те разбирам, може ли да обясниш Shocked
Впрочем аз не работя с разстоянието между точка и началото на координатната система, а направо с разстоянието между точките(примерно в моята формула от горния пост ако търсиш разстоянието между две точки те са с координати А[tex](x_1, y_1)[/tex] и В[tex](x_2, y_2)[/tex].
Ако точките са симетрично на началото на коорд. с-ма то разстоянието между тях ще е половината дръжка, докато на две съседни точки от контура на лъжицата разстоянието ще е само 1 пиксел, тоест би избрало съседните точки, или по-точно тези, които са най-близо една до друга. Сега е достатъчно да си избереш една точка от контура и да дадеш посока на движение(това с посоката не знам как ще стане, на практика трябва да кажеш коя е първата и коя втората точка) и след това то автоматично би трябвало да намери най-близката точка №2.

Все пак не е ли така Confused Confused Embarassed
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
carnophage
Начинаещ


Регистриран на: 10 May 2009
Мнения: 2


МнениеПуснато на: Mon May 11, 2009 6:53 pm    Заглавие:

Мерси, martosss, работи по твоя начин и стана системата, ама като имам 500+ точки и процесорът сгъва баницата..

Начинът описан в лекцията или не го схванах или не го използвам както трябва, защото ако приемем че minPoint ми е 0, 0 и формулата става:


Код:
points.sort(distSort);
function distSort(pA:Point, pB:Point):int
{
   return pA.y * pB.x - pB.y * pA.x;;
}


Което не подрежда точките една след друга в коректната последователност.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя
krainik
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Mon May 11, 2009 7:15 pm    Заглавие:

Марто, откъде знаеш, че произволна избраната от тебе точка ще е най-лявата или най-дясната...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Mon May 11, 2009 7:23 pm    Заглавие:

krainik написа:
Марто, откъде знаеш, че произволна избраната от тебе точка ще е най-лявата или най-дясната...
Ми ... избираш внимателно Very Happy пък и да не е най-лявата(дясната) пак би трябвало да стане.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Fed
VIP


Регистриран на: 24 May 2007
Мнения: 1136
Местожителство: София (Русе)
Репутация: 113.3
гласове: 33

МнениеПуснато на: Tue May 12, 2009 8:40 am    Заглавие:

martosss написа:
Fed, май нещо не те разбирам, може ли да обясниш Shocked
Впрочем аз не работя с разстоянието между точка и началото на координатната система, а направо с разстоянието между точките(примерно в моята формула от горния пост ако търсиш разстоянието между две точки те са с координати А[tex](x_1, y_1)[/tex] и В[tex](x_2, y_2)[/tex].
Ако точките са симетрично на началото на коорд. с-ма то разстоянието между тях ще е половината дръжка, докато на две съседни точки от контура на лъжицата разстоянието ще е само 1 пиксел, тоест би избрало съседните точки, или по-точно тези, които са най-близо една до друга. Сега е достатъчно да си избереш една точка от контура и да дадеш посока на движение(това с посоката не знам как ще стане, на практика трябва да кажеш коя е първата и коя втората точка) и след това то автоматично би трябвало да намери най-близката точка №2.

Все пак не е ли така Confused Confused Embarassed

Да, да, прав си, извинявай...не бях забелязал, че контурът е дискретизиран и че всеки пиксел от него реално ще е дадена точка. Confused
(Това, което следва, ако искаш не го чети) Иначе и алгоритъмът, който ти дадох ще свърши работа и май ще е по-бърз от твоя...твоя е със сложност O(n2), а това, което ти дадох би следвало да е със сложността на сортиращия алгоритъм, т.е. би могло да се достигне O(n.lgn). Laughing
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Kомпютърни изчисления Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.