Java PathIterator - Как мне найти правильный периметр области?
Помещение
Я случайно генерирую двумерную структуру, похожую на мази. Это сводится к случайному генерированию группы комнат в сетке, затем случайным образом соединяет эти комнаты с коридорами, используя A*. В комнатах есть стены, которые занимают всю площадь в сетке. У меня проблема с созданием этих стен.
Чтобы решить, где разместить случайно сгенерированные комнаты, я сначала делю сетку на кучу прямоугольных ячеек разных размеров, эти ячейки соседствуют друг с другом, используя ячейки с размером 1, чтобы заполнить оставшиеся промежутки между ними. После этого я выбираю случайную группу этих ячеек, чтобы они оказались комнатами. Если любая из выбранных ячеек находится рядом друг с другом, они объединяются в одну комнату. До этого момента алгоритм работал отлично.
пример
Проблема
У меня возникает проблема, когда я хочу перебрать каждый квадрат, определяющий стену одной из комнат. What happens now is, I create an Area for each room, and add every cell required to that room's Area. I successfully used the PathIterator to iterate through the Area's outline. The only problem is that the result of that iterator is not the result I want.
For example, suppose a rectangle with coördinate (5, 5), and size (4, 6). The resulting points I would want to iterate over are the following:
- Line 1 from (5, 5) to (8, 5)
- Line 2 from (8, 5) to (8, 10)
- Line 3 from (8, 10) to (5, 10)
- Line 4 from (5, 10) to (5, 5)
Instead, I end up with the following:
- Line 1 from (5, 5) to (9, 5)
- Line 2 from (9, 5) to (9, 11)
- Line 3 from (9, 11) to (5, 11)
- Line 4 from (5, 11) to (5, 5)
In other words, every line that can be considered to be above or to the left of the inside of the Area, are inclusive to the Area, and every line considered below or to the right of the Area, are exclusive to the Area (as returned by the Area.contains function).
Now fixing this may seem trivial when dealing with simple squares, but once I started trying to fix this for an Area in general, all sorts of annoying special cases started popping up from every angle I tried fixing it.
Some stuff I tried or considered:
- Graham's Scan algorithm. Failed when I realized what 'convex hull' means and how my rooms are not that
- Рассмотрите каждую последовательную линию на пути, проверьте, находится ли она в значительной степени внутри или снаружи Района, если она находится снаружи, переместите ее на одну единицу. Ошибка при попытке выполнить с наименьшими возможными строками (длина 2 - 3)
- Рассмотрите каждый последовательный набор из 3 точек на пути, проверьте, какой тип угла они делают (в каком направлении + это вогнутый или выпуклый угол), затем адаптируйте середину этих трех точек в зависимости от типа угла. Не удалось, потому что я не могу найти надежный метод проверки того, какой угол составляют точки
Поэтому мне интересно, есть ли что-то очевидное, что я здесь полностью упускаю? Это то, что я просто не смогу сделать с помощью PathIterator, и мне нужно реализовать собственный алгоритм "создания полигонов"? Если так, есть ли что-нибудь подобное? Я уже несколько дней ломаю голову над этим. Кажется, я не могу найти никакой помощи в Интернете.
Хорошо, я просто подумал о чем-то настолько невероятно очевидном, что мне немного стыдно за то, как сложно я пытался это сделать. Я думаю, что просто смотрю на это с закрытыми глазами.
- Итерировать по всем точкам ограничивающего прямоугольника
- Если многоугольник содержит точку, создайте переведенную версию точки в каждом направлении.
- Если многоугольник не содержит одну из переведенных точек, это означает, что точка является частью стены многоугольника.
Это невероятно очевидный и простой механизм, который означает, что, по крайней мере, я пока что спасен, но он явно ужасно неэффективен, поэтому, если у кого-то есть лучший алгоритм, он все равно очень приветствуется!