Алгоритмы и формулы Опции

[gamecreator]

Выкладываем сюда сабж.

Формула для поиска координат вершины треугольника по координатам двух других и двум углам:

Получим координаты точек С1 и С2.

Отдельная благодарность МаКаКу за предоставленный материал и Нильсу Фабиану Хельге фон Коху за тему для размышлений.

[izrukvruki]

Нужен алгоритм поиска площади следующей фигуры:

есть игра: есть зеленое прямоугольное поле и обочина - по ним ездят Комбайны (2) - они ничего не делают. никаких следов не оставляют, на обочине стоит Человек (1) - он может бегать по полю и "отсекать от него" куски, уменьшая площадь поля. Когда площадь уменьшится до некого числа - человек выигрывает и преходит на следующий уровень. Пока он бегает по полю - комбайн старается его задавить - если комбайн наедет на человека или на его СЛЕД (черным цветом отметил) то игра проиграна...

Думаю в эту игру многие играли на Спектрумах...

Вопрос вот в чем: как высчитать площадь зеленой фигуры (в общем виде - не конкретно в том в котором у меня изображено), после нескольких произвольных отсеканий (число отсеканий конечно)?

[Bourn]

один из методов я могу предложить, так как поле - это картинка (допустим) а картинка состоит из набора пикселей - это просто двухмерный массив байт - текущая площадь = 1, отсеченная = 0 можно пробежаться по массиву и посчитать число 1 или 0

[gamecreator]

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

[Azure]

подобную задачу решали ( возможна решают еще ) програмисты ЧПУ.
немножко не такая, скажем выщитать оптимальный алгоритм по раскройке листа метала, трикотажного полотна с площадью в N, произвольной формы.
Гдето встречал подобные алгоритмы, на их основе развивали другие, подобные игровым. Даже примеры на канве под Борландоские дельфы/билдеры.

Поищи, погугли.

[Guevara-chan]

Думаю в эту игру многие играли на Спектрумах...

А я вот на PC в нее играла . Что насчет алогритма... Вместо двоичного массива, наверное, лучше использовать пиксели самого спрайта поля. Оставшуюся же площадь дейстивтельно удобнее считать через вычитание кол-ва убранных пикселей.

[Bourn]

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

[Guevara-chan]

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

Ну да, но цветой код прозрачности по умолчанию все равно = 0.

[izrukvruki]

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

А как расчитывать площадь убранных пикселей?

[Guevara-chan]

А как расчитывать площадь убранных пикселей?

Так кусок же прямоугольный убирается ?

[izrukvruki]

Где сказано что прямоугольный??? Человек может бегать по ломанной - смотри правый верхний кусок - как будто это и есть единый оттяпанный кусок...

[Guevara-chan]

Где сказано что прямоугольный??? Человек может бегать по ломанной - смотри правый верхний кусок - как будто это и есть единый оттяпанный кусок...

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

[izrukvruki]

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

Предположу что поле имеет размеры n*m
тогда движение человека по этому полю можно описать последовательностью
{(xi,yi)k| xi,yi принадлежат {-1,0,1} (идет против оси, не движется, идет по оси), |xi|+|yi|=1 (по диагонали не может ходить), k=1..n*m - количество движений}

далее я не могу ничего сообразить...

[Diplomat]

Подсчет пикселей не самый рациональный вариант: если детализация картинки-поля относительно велика, производительность упадет ниже уровня шумов.

1. Можно испольовать фейк: двухмерный массив с детализацией заведомо более низкой, чем детализация поля. Далее два пути его использования:
- либо по количеству отсеченных/оставшихся "клеток" массива, можно будет приблизительно определить количество отсеченных/оставшихся пикселей поля;
- либо отсекать части картинки-поля только по квадратам, соответствующим элементам-"клеткам" массива по принципу плиток или мозаики, и тогда количество отсеченных пикселей будет прямо пропорционально количеству отсеченных "клеток" массива.

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

P.S. Подсчет площади отсекаемого многоугольника методами прямоугольников и трапеций считаю нецелесообразным в случае, если отсекаемая фигура имеет сложную произвольную форму.

[Guevara-chan]

Вот, Oxid тут еще предложил разбиение фигуры отсечения на трегольники, но это, ИМХО, не лучший вариант. Лучше все-таки последовательно считать отсекаемые пиксели.

[Darth_Beleg]

Подсчитать площадь для простого многоугольника (без самопересечений) просто, формула в enwiki: http://en.wikipedia.org/wiki/Polygon#Area_and_centroid
Для "сложного" многоугольника определить, что такое площадь, можно разными способами.

[Guevara-chan]

Подсчитать площадь для простого многоугольника (без самопересечений) просто, формула в enwiki: http://en.wikipedia.org/wiki/Polygon#Area_and_centroid
Для "сложного" многоугольника определить, что такое площадь можно разными способами.

Его же потом еще закрасить придется .

[Darth_Beleg]

Кого закрасить?

[gamecreator]

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

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

[Guevara-chan]

Кого закрасить?

Многоугольник.