Видимость полигонов с ребра

Question

дано 2D с полигонами. Мне нужно выяснить полигоны, видимые в перпендикулярной прямой видимости от заданного отрезка, лежащего в этой области. например,

• Далее

  Какими могут быть оптимизации, когда полигоны имеют только вертикальные и горизонтальные ребра.

Answer 1

Я бы предложил следующее ...

• Поверните проблему так, чтобы ваш сегмент прямой видимости выровнялся по оси x.
• Найдите (выровненный по оси) ограничительный прямоугольник (BR) каждого многоугольника.
• Сортировка полигонов по координате Y нижнего края каждого BR
• Создайте обрезной «буфер диапазона», чтобы отметить участки сегмента просмотра, которые больше не будут видны.
• Для каждого многоугольника C (текущего) в отсортированном списке выполните ...
  1. Используйте левую и правую границы С в качестве начального диапазона отсечения.
  2. Обрезать диапазон отсечения C с диапазоном, уже помеченным как обрезанный в «буфере диапазона».
  3. Теперь для каждого последующего многоугольника S одинаковой глубины (т. Е. Там, где нижний край BR у S начинается ниже верхнего края BR у C) ...
     • цикл до следующего S, если он не перекрывается по горизонтали с C
     • определить, перекрывается ли S слева или справа (например, сравнивая горизонтальные средние точки BR S и C). Если S перекрывается с правой стороны, а крайняя левая вершина S находится ниже самой правой вершины C, то соответственно обрежьте диапазон отсечения C. (Аналогично, если S перекрывается слева.)
  4. Если остаточный диапазон отсечения не пустой, то по крайней мере часть C видна из вашего сегмента просмотра. Теперь добавьте остаточный диапазон отсечения C в «буфер диапазона».