Професионална програма
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