Сергей-4030: Все сообщения за 24 Апреля 2007 года

>>А, ведь, на глаз задача решается как правило легко Каким же, интересно, алгоритмом?
AidarM> Мысленным закрашиванием всей области куда попали точки, последовательным выделением и отбрасыванием области, где точек явно нет. А потом - тщательное рассмотрение по краям неотброшенной области.

"Точек явно нет"? А как именно это узнать?

Лично мне кажется, что метод номер один - просто поиск в глубину. Чуть быстрее, чем перебирать все возможные варианты, хотя, конечно, не качественно быстрее. Это если
точек немного. Если много, предлагаю такой метод:

1. Исходная позиция - массив точек.

2. На основе всех наличествующих точек рисуем сетку из непересекающихся треугольников (разбиение не единственное, но "внешний контур" - единственный, заметьте).

3. Берем внешний контур получившейся сетки, отделяем ее от остальных. Для оставшихся точек повторяем процесс, снова берем контур и т.п. пока не будет набор контуров.

4. Идем из центра, "пробиваем дыры" из контура в контур (по принципу наименьшей площади "дыры"). Все, приехали.

Разумеется, полное решение нам такой способ не даст (если не пробовать все разбиения). Но, ИМХО, хорошее приближение.

•  3
•  инфо
•  инструменты
• Ответить на сообщение

>>"Точек явно нет"? А как именно это узнать?
AidarM> Увидеть. Balancer спросил про алгоритм, по которому наши мозги работают.

А хрен знает, работают ли они в эту сторону. Пример, который я предложил выше - я и сам не очень-то знал, куда чего рисовать. Боюсь, если точек будет несколько сотен, наши мозги вполне могут и запутаться.

•  инфо
•  инструменты
• Ответить на сообщение

>>На основе всех наличествующих точек рисуем сетку из непересекающихся треугольников (разбиение не единственное, но "внешний контур" - единственный, заметьте).
AidarM> А как вы быстро отслеживаете непересечение?

Быстро - никак. Просто отслеживаю непересечение двух отрезков. Т.е. процесс "конечноэлементизации" будет относительно долгий. Но много быстрее, тем не менее, чем случайный поиск. А ничего другого мне просто на ум не идет.

•  инфо
•  инструменты
• Ответить на сообщение