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