Zakładając, że twoje duszki zajmują zestawy płytek, które są prostokątami (jeśli zajmują dowolne zestawy, to w ogóle nie możesz narysować poprawnie w ogóle), problem polega na tym, że nie ma całkowitej relacji między elementami, więc nie możesz sortować używając metody sortowania, która spowodowałaby porównania O (nlogn).
Zauważ, że dla dowolnych dwóch obiektów A i B albo A należy narysować przed B (A <- B), B należy narysować przed A (B <- A) lub można je narysować w dowolnej kolejności. Tworzą częściowe zamówienie. Jeśli narysujesz sobie kilka przykładów z 3 nakładającymi się obiektami, możesz zauważyć, że chociaż pierwszy i trzeci obiekt mogą się nie nakładać, a zatem nie mają bezpośredniej zależności, ich kolejność rysowania zależy od drugiego obiektu, który jest między nimi - w zależności od tego, jak umieścisz go, otrzymasz różne zamówienia rysowania. Dolna linia - tradycyjne rodzaje nie działają tutaj.
Jednym z rozwiązań jest użycie porównania (wspomnianego przez Dani) i porównanie każdego obiektu ze sobą w celu ustalenia ich zależności i utworzenia wykresu zależności (który będzie DAG). Następnie wykonaj sortowanie topologiczne na wykresie, aby określić kolejność rysowania. Jeśli nie ma zbyt wielu obiektów, może to być wystarczająco szybkie (to jest O(n^2)
).
Innym rozwiązaniem jest użycie (do równoważenia - pseudo ) drzewa quad i przechowywanie w nim prostokątów wszystkich obiektów.
Następnie iteruj przez wszystkie obiekty X i użyj drzewa quadów, aby sprawdzić, czy w pasku nad obiektem X znajdują się obiekty Y, które zaczynają się od skraju lewej i kończą skrajnym prawym narożnikiem obiektu X - dla wszystkich takich Y, Y < - X. W ten sposób nadal będziesz musiał utworzyć wykres i sortować topologicznie.
Ale możesz tego uniknąć. Używasz listy obiektów Q i tabeli obiektów T. Powtarzasz wszystkie widoczne szczeliny od mniejszych do większych wartości na osi x (jeden rząd), przechodząc rząd po rzędzie na osi y. Jeśli w tym gnieździe znajduje się dolny róg obiektu, wykonaj powyższą procedurę, aby określić zależności. Jeśli obiekt X zależy od jakiegoś innego obiektu Y, który jest częściowo nad nim (Y <- X), a każde takie Y jest już w Q, dodaj X do Q. Jeśli istnieje jakieś Y, które nie jest w Q, dodaj X do T i oznaczają, że Y <- X. Za każdym razem, gdy dodajesz obiekt do Q, usuwasz zależności obiektów oczekujących w T. Jeśli wszystkie zależności zostaną usunięte, obiekt z T jest przenoszony do Q.
Zakładamy, że duszki obiektów nie wystają ze swoich szczelin na dole, z lewej lub z prawej strony (tylko u góry, jak drzewa na zdjęciu). To powinno poprawić wydajność dla dużej liczby obiektów. Takie podejście znów będzie O(n^2)
, ale tylko w najgorszym przypadku, który obejmuje przedmioty o dziwnych rozmiarach i / lub dziwne konfiguracje obiektów. W większości przypadków tak jest O(n * logn * sqrt(n))
. Znajomość wysokości twoich duszków może wyeliminować sqrt(n)
, ponieważ nie musisz sprawdzać całego paska powyżej. W zależności od liczby obiektów na ekranie możesz spróbować zastąpić drzewo quadów tablicą wskazującą, które miejsca są zajęte (ma to sens, jeśli jest wiele obiektów).
Na koniec zachęcamy do sprawdzenia tego kodu źródłowego pod kątem niektórych pomysłów: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala