Случайно размещать объекты, используя карту альфа

Question

Я хочу размещать объекты случайным образом, используя альфа-карту (только черный цвет, а не в оттенках серого). Черные области на карте используются, чтобы определить, где мы МОЖЕМ разместить объект.

Почему я хочу это сделать? Например, у нас есть местность с рекой. Мы хотим случайным образом разместить сундук в этой местности, и дело в том, что мы хотим, чтобы наш сундук НЕ БЫЛ В РЕКЕ. У нас есть специальное место для размещения этого сундука, и это место может иметь очень сложную структуру.

Простая карта с озером и рекой:

Черно-белая карта места размещения объектов:

Конечно, мы можем просто взять случайные точки с помощью Random.Range() и проверить каждую точку, сравнив ее со значениями пикселей: "Точка находится в черной области?" НО, если бы у нас была очень маленькая (<10% от общей площади) и сложная "доступная" область (например, острова в болоте), тогда было бы очень большое количество "мусорных" точек. Поэтому это очень неэффективный метод.

Существует ли быстрая и эффективная техника для получения желаемого количества "доступных" очков?

Answer 1

Теоретически вы могли бы сегментировать альфа-карту по цвету, чтобы получить геометрическое многоугольное представление областей, затем вы могли бы сгенерировать точку алгоритмически внутри набора черно-белых полигонов. Но если вы хотите обменять память на скорость, есть гораздо более простое решение: просто представьте альфа-карту в виде двух массивов (черно-белых) координат пикселей и затем случайным образом выберите точку из необходимого массива.