Оптимизация алгоритма принадлежности точки прямоугольнику

[altruista]

Пример:

Имеется произвольно расположенный в плоскости прямоугольник с известными координатами вершин (на рисунке выделен жирным черным). Допустим, каждая клетка - это точка с координатами (х,у). Необходимо определить все точки, принадлежащие прямоугольнику (внутри или пересекают его границы), в примере они выделены зеленым.
Есть ли какой другой способ сделать это, кроме как тупым перебором всех точек плоскости, ограничивающей искомый прямоугольник сверху, снизу, слева, справа (выделена желтым фоном)? Т.е. можно ли оптимизировать следующий алгоритм (Pascal):

      for x := leftX to rightX do      
        for y := topY to bottomY do
          if PointInRect(x, y) then AddToPointsList(x, y);

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Программирование»

[svv]

Конечно, есть. Посмотрите книгу:
Павлидис Т. Алгоритмы машинной графики и обработки изображений.
Может, и лучше книги есть, я только эту знаю.

[altruista]

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

      middleY := (topY + bottomY) div 2;

      for y := topY to middleY do begin  // проверка верхней половины сверху вниз
        for x := topX downto leftX do 
          if PointInRect(x, y) then AddToPointsList(x, y) else Break;
        for x := topX to rightX do 
          if PointInRect(x, y) then AddToPointsList(x, y) else Break;
      end;

      for y := bottomY downto middleY+1 do begin  // проверка нижней половины снизу вверх
        for x := bottomX downto leftX do 
          if PointInRect(x, y) then AddToPointsList(x, y) else Break;
        for x := bottomX to rightX do 
          if PointInRect(x, y) then AddToPointsList(x, y) else Break;
      end;

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

[demolishka]

altruista
Попробуйте применить эту идею рекурсивно: делите каждый участок на 4, пока они не станут достаточно маленькими(например пока не будут лежать в квадрате 3х3). При этом, каждый раз оптимизируйте для текущего участка возможные границы(например, после разбиения исходного прямоугольника левый верхний участок можно оптимизировать по вертикали). Нужно лишь аккуратно реализовать эту самую оптимизацию границ.

[Pavia]

Вам надо прочитать про растеризацию многоугольников. Существует несколько подходов. Поэтому предлагаю остановиться на алгоритмах основанных на сканирования линиями (ScanLine).

Для начало разобраться как это делается для треугольника, а затем будет легко расширить на четырёхугольник и чуть по сложнее на многоугольник.
Думаю можно начать от сюда.
http://www.enlight.ru/faq3d/articles/24.htm
Хотя я предпочитаю делать через дополнительный массив, для точек рёбер.
http://pmg.org.ru/basic3d/graph.htm

Шаг 1. Сортируем вершины по вертикали.
Шаг 2. Сортируем по горизонтали.
Шаг 3. Рассчитываем координаты точек рёбер нашего примитива, заносим их в массив. По аналогии с алгоритмом Брезенхэма для линий.
Шаг 4. Перебираем линии по горизонтали, извлекая данные из массива и строим горизонтальные линии по ним.