2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Оптимизация алгоритма принадлежности точки прямоугольнику
Сообщение07.05.2014, 10:49 
Пример:
Изображение
Имеется произвольно расположенный в плоскости прямоугольник с известными координатами вершин (на рисунке выделен жирным черным). Допустим, каждая клетка - это точка с координатами (х,у). Необходимо определить все точки, принадлежащие прямоугольнику (внутри или пересекают его границы), в примере они выделены зеленым.
Есть ли какой другой способ сделать это, кроме как тупым перебором всех точек плоскости, ограничивающей искомый прямоугольник сверху, снизу, слева, справа (выделена желтым фоном)? Т.е. можно ли оптимизировать следующий алгоритм (Pascal):
Код:
      for x := leftX to rightX do     
        for y := topY to bottomY do
          if PointInRect(x, y) then AddToPointsList(x, y);

 
 
 
 Posted automatically
Сообщение07.05.2014, 11:47 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Программирование»

 
 
 
 Re: Оптимизация алгоритма принадлежности точки прямоугольнику
Сообщение07.05.2014, 12:24 
Аватара пользователя
Конечно, есть. Посмотрите книгу:
Павлидис Т. Алгоритмы машинной графики и обработки изображений.
Может, и лучше книги есть, я только эту знаю.

 
 
 
 Re: Оптимизация алгоритма принадлежности точки прямоугольнику
Сообщение07.05.2014, 14:46 
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;

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

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

 
 
 
 Re: Оптимизация алгоритма принадлежности точки прямоугольнику
Сообщение07.05.2014, 20:21 
Аватара пользователя
Вам надо прочитать про растеризацию многоугольников. Существует несколько подходов. Поэтому предлагаю остановиться на алгоритмах основанных на сканирования линиями (ScanLine).

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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group