Добрый день.
Разрабатываю 2Д РПГ.
Решаю задачу области видимости.

Итак:
2х мерная система координа.
есть области невидимости. Каждая описана 3мя уравенениями вида
у*а+х*в+с>0
Эти области могут налазить одна на другую
Есть геометрические фигуры: многогранники, круги, линии
многогранники описаны координатами вершин, круг - координатами центра и радиусом, линии - координатами начала и конца.

Нужно разработать алгоритм определения находится ли фигура полностью на зонах невидимости или нет.

А в чем проблема? Область невидимости у тебя - полуплоскость; определение - видима ли конкретная точка - тривиально: она должна быть вне всех областей невидимости... Видимость фигур определяется тоже через точки. Для ускорения можно сначала проверить видимость охватывающих фигуры прямоугольников. В зависимости от числа областей невидимости и\или частоты их изменения возможно есть смысл пересчитать их в видимые полигоны.

Это настоящее мастерство - написать заумный текст, но на вопрос не ответить вообще.
Я тут ничего ни от кого не требу.
И одолжений никто ни кому не делает.
Кто хочет, то решает задачку.

А такие ответы это флуд чистой воды.
Минусы надо за такие ответы ставить.

Это сообщение отредактировал(а) СЭНСЭЙ - 30.7.2011, 11:03

СЭНСЭЙ, это не очень эффективный подход к поиску ответа

когда содержимое ответа непонятно, есть два варианта:
1. объявить его "заумным", "водой", лишенным смысла и ждать следующего ответа
2. попытаться уточнить детали и проверить, а действительно ли там нет смысла, или его просто сложно разглядеть

Иногда люди действительно пытаются просто показаться умными и "льют воду", однако, если предполагать это всегда, когда текст непонятен, можно пропустить много полезного.

Второй вариант поведения, как правило, позволяет получить ответ гораздо быстрее.

В данном случае Earnest дала почти полный ответ (по крайней мере для многогранников).

Я попытаюсь написать пояснения, которые могли бы появиться после уточняющих вопросов:


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


Для проверки видимости одной точки просто просчитываем неравенство невидимых областей. Если бы хотя бы одно выполнилось - точка невидима.


Если у нас многогранник на 10000 вершин, можно сначала вписать его в какую-нибудь простую бОльшую фигуру (квадрат, например) и проверить её точки (4). Если бОльшая фигура не видна, нам не нужно пробегаться по всем очкам многогранника и считать неравенства.


Это сообщение отредактировал(а) maxim1000 - 30.7.2011, 11:50

Хм, ну да, возможно мой ответ был слишком кратким... ну там жара и т.д.  
Кроме того, когда задают вопросы такого сорта, хочется как-то очертить проблему, а не расписывать все и вся от Адама. Может, автору просто в голову не пришли простые вещи, и его нужно просто пнуть в нужном направлении (тем более, когда ник такой скромный  ).
В общем, maxim все правильно расписал за меня; если остались вопросы - уточняй.

Товарищи. Не поймите меня не правильно...
Когда идет посик ответов на такие сложные вопросы действительно расписывать все с нуля не правильно.
Это будет нагромождение текста.
Естественно если я говорю про наложение плогонов, описанных уравнениями, то уж попадание точки в зоны
для меня должно быть тривиальной задачей. Давайте говорить на одном языке.

Естественно вариант вписать фигуры в квадрат и проверить попадание его вершин
само собой разумеющийся.

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

Я исписал уже пару десятков А4. Думаю на форуме не стоит плодить столько текста.

Итак еще раз вопрос:

2х мерная система координа.
есть области невидимости. Каждая описана 3мя уравенениями вида
у*а+х*в+с>0
Эти области могут налазить одна на другую
Есть геометрические фигуры: многогранники, круги, линии
многогранники описаны координатами вершин, круг - координатами центра и радиусом, линии - координатами начала и конца.

Нужно разработать алгоритм определения находится ли фигура полностью на зонах невидимости или нет.

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

Понятно, что есть некоторая сложность, как представить "открытые" области - т.е. стороны, неотсеченные никакой плоскостью. Здесь возможны, видимо, разные подходы, но самое простое - просто ограничить рассматриваемое пространство - ведь оно наверняка и так ограничено. Скажем, это может быть охватывающий прямоугольник всех проверяемых фигур. Этот же подход дает и ответ на вопрос, как построить полигон видимости из полуплоскостей: начинаем с квадрата и по очереди рассекаем его каждой полуплоскостью, оставляя только видимую часть.

многоугольники выпуклые?

Earnest - не совсем. Вся ли фигура попала в зонЫ.
Вы почти правильно поняли.
Только вы расписываете проблему, а я ищу математическое решение.
Статью на эту тему напишем после.

На данный момент работаю над графическим, дискретным решением.

maxim1000 - можете прокомментировать свой вопрос?

если у многоугольника все углы направлены внутрь, он выпуклый
http://s2.ipicture.ru/uploads/20110802/fzToVSRN.png

у них есть свойство, полезное в данной ситуации: если от выпуклого многоугольника отсечь часть прямой, останется один кусок, для невыпуклых может быть много

Мы еще не подошли к тому моменту когда это может быть принципиальным,
но
предполагается что все многоугольники будут 4 сторонними.
Скорее всего будут только прямоугольники, но хочу что бы решение было универсальным хотя бы выпуклых для 4гранников

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

TPolygon - полигон
TArea - невидимая область
TVertex - вершина полигона
TArea::Contains(vertex) - проверяет содержится ли точка в области
TPolygon::NextVertex(vertex) - находит вершину, следующую за vertex
TArea::BorderVertex(vertex1,vertex2) - находит точку пересечения отрезка [vertex1,vertex2] и прямой, которая ограничивает невидимую область

А меня есть получше алгоритм:
написать программу{З: Задумка; И:Инструмент}
{
for нафига 
{
писать;
}
else
{
оставить как есть;
}
}

Еще есть анекдот, как программиста нашли мертвым в душе.
В руке он держать флакон с шампунем, а на флаконе было написано:
"Нанести на руку, растереть, повторить".


Короче решил пока что так:
Расставил все фигуры в порядке удаленности от наблюдателя,
Описал зону невидимости от первой фигуры,
Перебираю остальные фигуры по очереди,
Беру на периметре фигуры 12 точек, получить координаты которых не составляет труда.
Проверяю попадание каждой точки на зоны невидимости. Если все 12 точек попали хоть на одну из зон, то фигура невидимая.
Если фигура видимая, то вычисляется ее зона невидимости и добавляется в список зон.
12 точек вполне достаточно для моей задумки, учитывая что я делаю Рогалик.
В крайнем случае можно взять 24 или 32.
Работает быстро.

http://brainstream-dev.blogspot.com/2010/0...og-post_30.html
PS тред не читал   

Прочитал.
Но мой случай довольно отличается.
И мое решение на данный момент на много проще.
Возьму на заметку.

Спасибо тебе!!!!