Mam siatkę płytek o znanym skończonym rozmiarze, która tworzy mapę. Niektóre kafelki na mapie są umieszczane w zestawie zwanym terytorium. Terytorium to jest połączone, ale nic nie wiadomo o jego kształcie. Przez większość czasu byłby to dość regularny kropelka, ale może być bardzo wydłużony w jednym kierunku i potencjalnie może mieć nawet dziury. Jestem zainteresowany znalezieniem (zewnętrznej) granicy terytorium.
To znaczy, chcę listę wszystkich kafelków, które dotykają jednego z kafelków na terytorium, nie będąc na tym terytorium. Jaki jest skuteczny sposób na znalezienie tego?
Dla dodatkowej trudności zdarza się, że moje kafelki są heksami, ale podejrzewam, że to nie robi zbyt wielkiej różnicy, każda płytka jest nadal oznaczona liczbą całkowitą współrzędną xiy, a biorąc pod uwagę płytkę, mogę łatwo znaleźć sąsiadów. Poniżej kilka przykładów: czerń to terytorium, a niebieska granica, którą chcę znaleźć.
To samo w sobie nie jest trudnym problemem. Jednym z prostych algorytmów tego, w pseudo-python, jest:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)Jest to jednak powolne i chciałbym coś lepszego. Mam pętlę O (n) nad terytorium, kolejną pętlę (krótką, ale nadal) nad wszystkimi sąsiadami, a następnie muszę sprawdzić członkostwo na dwóch listach, z których jedna ma rozmiar n. To daje okropne skalowanie O (n ^ 2). Mogę zredukować to do O (n), używając zestawów zamiast list dla granicy i terytorium, dzięki czemu członkostwo można szybko sprawdzić, ale nadal nie jest świetne. Oczekuję, że będzie wiele przypadków, w których terytorium jest duże, ale granica jest mała ze względu na proste skalowanie obszaru względem linii. Na przykład, jeśli terytorium ma heks o promieniu 5, ma rozmiar 91, ale granica ma tylko rozmiar 36.
Czy ktoś może zaproponować coś lepszego?
Edytować:
Aby odpowiedzieć na niektóre z poniższych pytań. Terytorium może mieć wielkość od około 20 do około 100. Zestaw kafelków tworzących terytorium jest atrybutem obiektu i to ten obiekt potrzebuje zestawu wszystkich kafelków granicy.
Początkowo terytorium jest tworzone jako blok, a następnie najczęściej zdobywa kafelki jeden po drugim. W tym przypadku prawdą jest, że najszybszym sposobem jest po prostu utrzymanie zestawu granicy i aktualizowanie go tylko na zdobytym kafelku. Czasami może się zdarzyć duża zmiana na terytorium - dlatego trzeba będzie go w pełni ponownie obliczyć.
Jestem teraz zdania, że wykonanie prostego algorytmu znajdowania granic jest najlepszym rozwiązaniem. Jedyna dodatkowa złożoność, którą to powoduje, polega na ponownym obliczeniu granicy za każdym razem, gdy zajdzie taka potrzeba, ale nie więcej. Jestem przekonany, że można to zrobić niezawodnie w moich obecnych ramach.
Jeśli chodzi o czas, w moim obecnym kodzie mam pewne procedury, które muszą sprawdzać każdy kafelek terytorium. Nie na każdym kroku, ale na stworzeniu, a czasem potem. Zajmuje to ponad 50% czasu działania mojego zestawu kodu testowego, mimo że jest to bardzo niewielka część całego programu. Dlatego chciałem zminimalizować wszelkie powtórzenia. JEDNAK kod testowy wymaga znacznie więcej tworzenia obiektów niż normalne uruchomienie programu (oczywiście), więc zdaję sobie sprawę, że może to nie być bardzo istotne.