Вписать выпуклый многоугольник в квадраты

Похожие темы: Алгоритм пересечения отрезка с выпуклым многоугольником.

проходим по периметру, красим квадратики, заливаем внутреннюю часть, радуемся успеху.

заливаем внутреннюю часть

внутренняя часть - от самого нижнего квадратика вверх.

вершины многоугольника на узлах сетки, или не обязательно?

не обязательно.

А на векторную алгебру надо было ходить, да.

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

Это навскидку, так как нужно учитывать граничные условия (например, попадание вершины многоугольника на границу квадратов и прочее), но для старта хватит.

о это волнующее ощущение, будто опять оказался в школе. пойду спать.

1) Ищем макс размеры многоугольника по Y (перебирая все вершины), скажем он занимает от y1 до y2.

2) пересчитываем y1 и y2 в номера строк iy1 и iy2.

3) проходим все строки от iy1 до iy2,

3.1) для каждой строки находим вершины многоугольника попадающие по y в строку, для этих вершин находим минимальную и максимальную координаты по х, скажем x1 и x2;

3.2) подправляем x1 и x2 за счет сторон многоугольника у которых хотя бы одна вершина попала в строку

3.3) проходим по строке в цикле от ix1 до ix2 и отмечаем все встретившиеся квадраты.

Да, но задача по нахождению пересечения отрезка и ячеек сетки довольно гнусная. В идеале ее нужно решать находя пересечение отрезка со стороной ячейки, потом переходим в эту ячейку и т.д.

http://en.m.wikipedia.org/wiki/Marching_squares

Не?

Я даже не знаю, как сформировать запрос для гугла. Подскажите алгоритмы.

Тебе нужен алгоритм построчной заливки (заполнения) многоугольника.

AIv его примерно описал, но как-то не очень внятно.

Если количество квадратиков (и углов у многоугольника) небольшое, можно сделать простым перебором

1. Бьем многоугольник на треугольники

2. Как написал AIv ограничиваем фигуру прямоугольником

3. Проходим по узлам сетки прямоугольника, для каждого смотрим попадает ли он в многоугольник (хотя бы в один треугольник). Если узел в многоугольнике, помечаем все четыре смежных квадратика как накрытые

не совсем.

да, судя по всем это заливка и есть. thanks cdslow AIv.

Пусть у тебя есть функция принадлежности точки многоугольнику. Тогда с помощью простейшего Монте-Карло ты можешь найти все квадраты.