Loading...
krasi070 avatar krasi070 22 Точки

[Exercise] Data Structures - Advanced Tree Structures - Part II - QuadTree

Всичките Unit - тестове ми минават без един(този с random елементите). Вече трети ден се чуде къде ми е грешката и най-накрая реших до поискам помощ.

Ако се съди от името на теста, грешката би трябвало да е някъде в Report метода или някой от неговите помощни методи.

Ето и самото дърво: 

https://github.com/krasi070/DataStructures/tree/master/09.AdvancedTreeStructuresPartTwo/Exercise/02.QuadTreeCore

Предварително благодаря за помощта!

Тагове:
2
Структури от данни и алгоритми 23/03/2016 20:48:57
a_rusenov avatar a_rusenov 1103 Точки
Best Answer

Както при повечето колеги си пропуснал в ShouldSplit на Node да провериш дали вече не е сплитнато. :) В случая става така, че всеки път, когато в един нод се вкарат 4 върха, той презаписва в/у съществуващите си деца нови 4 нода. А това трябва да става само първия път - когато все още няма деца.

7
butanfire avatar butanfire 32 Точки

Привет Наско!
И аз да отбележа, че имах доста проблеми със някои от тестовете, и сега като сверих някои стойности с тези на Краси и тези от от упражнението и ми се стори странно следното :

1) За  GetQuadrant функциите :
Заместих Top/Bottom quadrant стойностите, с тези от лаба ... и фейлнаха тестовете?

2) За Split-a функцията - Children[0] и Children[1] (top right/top left)

Заместих стойностите с тези от лаба и фейлнаха тестовете.

3) За Split функцията : 

Не разбирам разликата между :

    for (int i = 0; i < currentNode.Items.Count;)
            {
                var item = currentNode.Items[i];
                int quadrant = this.GetQuadrant(currentNode, item.Bounds);
                if (quadrant != -1)
                {
                    currentNode.Items.Remove(item);
                    currentNode.Children[quadrant].Items.Add(item);
                }
                else
                {
                    i++;
                }

и слагането на итерацията във for statement-a :

    for (int i = 0; i < currentNode.Items.Count;i++)
            {
                var item = currentNode.Items[i];
                int quadrant = this.GetQuadrant(currentNode, item.Bounds);
                if (quadrant != -1)
                {
                    currentNode.Items.Remove(item);
                    currentNode.Children[quadrant].Items.Add(item);
                }

понеже фейлват тестовете ако не се изкара итератора в Else statement-a?

Ако правилно отгатвам е че колекцията се променя като се трият елементи и се пренареждат индексите.

Но тогава не разбирам защо примера във лаба е даден по този начин? Или аз нещо се бъркам?

 

Иначе, към @krasi

Имаше парче код за Insert функцията, може лесно да си спестиш код с това :

if (quadrant != -1)
                {
                    currentNode = currentNode.Children[quadrant];
                    depth++;
                }

Поздрави,

Владо

 

0
a_rusenov avatar a_rusenov 1103 Точки

Не разбрах кое си заместил и са фейлнали тестовете. Най-добре качи линк към кода и да видим.

Иначе вцикъла на Split както е в лаба трябва при триене i да намаля. Честно казано твоят вариант е по-умен, няма причина да е така.

0
yuletodim avatar yuletodim 37 Точки

Здравей!

И на мен този лаб ми се оказа най-проблематичен. GetQuadrant и Split  от лаба са коректни.

Колкото до for-цикъла аз го въртях от (currentNode.Items.Count -1)  до 0, за да не излизам от range-a на индексите и дълго се чудих възможно ли е да стане по начинът написан в лаба.

И аз бях пропуснала в ShouldSplit да проверя дали node-a няма вече  деца.

Като цяло курсът много ми хареса и обогати знанията ми. Искам да благодаря на Наско за положените усилия.

Успех на изпита на всички!

2
butanfire avatar butanfire 32 Точки

Привет Наско!

Общо взето , примерните формули дадени за горните 2 квадранта (1 и 0) , както и за децата които попадат там (1 и 0) , сметките май са грешни.

=>Ако заместя стойностите за GetQuadrant и Split функцията с тези от лаб документа - тестовете фейлват.

Ето го и кода + коментара и стойностите.

http://pastebin.com/GWqQZ0PZ
Хубаво е да не разчитаме на лаба, а сами да си го правим , съгласен съм, просто да търсиш къде е грешката е по-гадно от това да си го напишеш сам :))))

 

Поздрави,

Владо

0
Innos avatar Innos 419 Точки

Гледам ти кода и намирам няколко грешки, предполагам си решил да обърнеш isTopQuadrant и isBottomQuadrant, защото ти е минал някой тест така? Тестовете са достатъчно семпли да може да хванеш някой по чист късмет от хак, но със сигурност логиката на isTop и isBottom както си ги написал сега не е правилна, то е очевидно ако я проследиш че така проверките ти са наобратно - isTop проверява дали е в долния, а isBottom дали е в горният. Тук е добър момент да се отбележе че Y-а в програмирането нараства надолу, а не нагоре както в стандартна координатна система, може би объркването идва от това? Другото което забелязвам е че не намаляш i при пренасяне на елемент в детето му като сплитнеш:
 

for (int i = 0; i < currentNode.Items.Count; i++)
            {
                var item = currentNode.Items[i];
                int quadrant = this.GetQuadrant(currentNode, item.Bounds);
                if (quadrant != -1)
                {
                    currentNode.Items.Remove(item);
                    currentNode.Children[quadrant].Items.Add(item);
                }
            }

В тази ситуация ако пренесем item в детето му (currentNode.Items.Remove(item);) общият брой на елементи в currentNode.Items ще спадне, и ще пропуснеш следващият елемент (защото той ще дойде на индекса който току що си обходил).

2
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.