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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ну так обвести линией, а потом FloodFill
хотя если учесть что где-то в массиве наверняка хранится поле, то можно и напрямую

А если FloodFill и его аналоги недоступны по каким-то причнам ? Тогда придется закрашивать сомстоятельно. Ну а уж коли идет закраска - почему бы не посчитать пиксели мимоходом ?

Есть такое предложение. Понятно, что поле состоит из квадратов (в зависимости от размера человека, например 5х5 пикселей), каждый квадрат имеет свои координаты (например координаты у нас от 0 до 100 по 2-ум координатным прямым). Хотя это не суть важно.

Ну а дальше можно так сделать (надеюсь не сильно сложно):
1) Создаем массив из координат поля
2) Запоминаем в одномерный массив все координаты передвижения человека, кроме углов (т.е. там где менялось направление движения).
3) После того как человек повторно пересек границу поля (т.е. момент отсечения фигуры), запускаем цикл, который проверяет все координаты поля, т.е.

For y:= 1 to 100 do begin
For x:=1 to 100 do begin

Т.е. как бы проводим линии через все поле паралельно оси х-ов по каждой координате у.

При этом проверяем количество координат которые посещал игрок на каждой линии. Далее:
если координат на линии больше 1-ой, то вытираем участки поля которые находятся по координатам между 1 и2 3 и 4 5 и 6 и т.д.
если координата 1-на, то подсчитывае расстояние от начала и конца поля до координаты, т.е. Х или 100-Х, и вытираем участки поля которые оказались на меньшей стороне (т.е. либо от 0 до Х, либо от Х до 100).

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

Надеюсь понятно объяснил

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

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

Д'якон, твой алгоритм в таком виде не сработает, т.к. не сможет различить 2 таких случая:
1)
00000____00000
00000000000000
00000000000000

2)
00000____88888
00000000_88888
00000000_88888

т.е. в первом случае игрок пошел по горизонтали и вернулся наверх, а во 2м - пошел вниз и отсек поле, закрашенное 8-ми. В твоем алгоритме первая строка будет одинаковой.
Дамаю, надо, наоборот, оперировать вертикальными и горизонтальными отрезками. Идя по горизонтали надо считать кол-во пересечений вертикальных отрезков, а при переходе на след. линию учитывать пересечение горизонтального отрезка в точке x=0. Вообще, в дискретном случае получается много тонкостей:
1) Надо считать пересечения не отрезков, а полуинтервалов. Исключать либо меньшую по координате вершину отрезка, либо большую. Например, не будем учитывать пересечения большей по координате вершины.
2) Тогда, при переходе на след. строку надо менять "ориентацию" сразу, как только мы коснулись горизонтального полуинтервала.

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

Чтобы учесть то, что от области уже отрезаны какие-то куски,надо учитывать движение человека и в этих областях.

А простой алгоритм такой: находим первую незакрашенную точку и шуруем от нее чем-то типа FloodFill'а. Т.е. закрашиваем ее, просматриваем соседей и с незкраенными рекуррентно делаем то же самое. Потом так же закрашиваем 2ю часть области, а потом убираем меньшую по кол-ву точек. Скорость уменьшится максимум раз в 10.

1) А если отсечена большая часть поля ?
2) А в случае самопересечения что делать ?

Да я и сам понял, что метод не совсем полный. Но я придумал как сделать полным.

Нужно "проводить" линии во всех направлениях, учитывая при этом край поля от которого отталкиваемся за линию пересечения и один раз провести линию не учитывая края полей. В конце сравнить результаты и удалить меньшую часть. Сейчас нарисую, чтоб было понятно

Добавлено ([mergetime]1204971458[/mergetime]):
1 - это движение игрока по полю
А потом пять методов из которого выбираем меньшую площадь (т.е. меньшее кол-во координат было удалено)

считаем две площади по обе стороны и закрашиваем меньшую.
а в случае самопересечения закрашиваем тот участок и не учитываем.

//считаем две площади по обе стороны и закрашиваем меньшую.

А как посчитать?

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

А как выделить нужную часть поля. Как программа поймет какую часть нужно посчитать?

Добавлено ([mergetime]1204984484[/mergetime]):
Допустим взять мой рисунок. Как программа поймет, что там всего две фигуры?

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

я вообще не понял твоего рисунка.

волновой алгоритм? Как? Разъясни

помечаешь одну вершину каким-либо числом (обычно 0). увеличиваем счетчик на 1. все вершины смежные с вершинами, у которых метка равна счетчик-1, и не имеющие метки помечаем числом счетчик. делаем это пока можно пометить хоть что-то.

Добавлено ([mergetime]1204992873[/mergetime]):
зы. разъясни свой рисунок

Все равно не понял, что это даст.

Разъясняю рисунки.

На 1-ом рисунке, более жирной линией отмечен путь человека.

На 2-ом рисунке запускаем цикл
F:=1 - устанавливаем флаг в true
For y:=1 to 100 do begin
For x:=1 to 100 do begin

где от 1 до 100 - координаты поля (допустим!)

Если при прохождении цикла координата X;Y - совпадет с координатой на которой был человек флаг устанавливается в 0. При этом каждая координата проходит проверку на удаление. Если F=1, то координата удаляется. Если опять попали на координату игрока, то F=1.

Стрелочки на линии показвают направление в котором мы запускаем цикл.

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

И 5-ый рисунок. Запускаем сразу в двух направлениях по х и по у, но с начальным флагом 0. И там где пересекутся удаленные координаты в двух направлениях, те и удаляем (рисунок немного не правильный, извеняюсь). В принципе 5-ый цикл нужен для проверки самопересечений.

Понятно?

неа

Хорошо, давай так. Флаг F=true, говорит нам о том, что координату нужно удалить.

Рассмотрим рисунок№2

Представь, что ты ведешь прямую линию СЛЕВА НАПРАВО паралельно оси Х, с координатой по у=20 (как линия на рисунке примерно).
Переходишь на координату 1;20 , проверяешь равено ли F единице, если да, то уделяешь эту координату. Дальше 2;20, то же самое. И так до тех пор пока координато на который ты в данный момент не совпадет с координатой на которой был игрок, т.е. где-то 85;20. Ставишь флаг в 0. И продолжаешь до конца поля тем же макаром.

На 3-рисунке, Справа Налево, 4-ый - сверху вниз, 5-ый снизу вверх.

А на 6-ом в двух направлениях, но с начальным флагом 0

вот вам. разбирайтесь.
http://gcr.by.ru/game01.7z

Д'якон, нифига не понял. Как я понял, речь о чем-то медленном и вряд ли работающем.
В любом случае алгоритм должен вначале считать площади, а потом что-либо удалять.

То, про что говорит Гамодел - это, похоже, тот же простой алгоритм, о котором говорил я.


1) Я имел в виду, что это алгоритм разбития поля на первую часть и вторую. Мы их помечаем в массиве (скажем, 1 и 2ками) и попутно считаем кол-во клеток в каждой. А потом уж удалить меньшую - дело техники.
2) В оригинале игрок при этом, кажется, умирал. Но если они допустимы, то надо продолжать так же - если находим непомеченную точку, заливаем все прилежащие точки 3ками. Наименьшую по площади фигуру удаляем. По сути, алгоритм от этого не усложняется.
А вот тот алгоритм, который писал Д'якон и я, рассчитан исключительно на отсутствие самопересечений.

//Д'якон, нифига не понял. Как я понял, речь о чем-то медленном и вряд ли работающем.

ну напиши его чтобы мы могли увидеть код и по коду понять. я ведь для тебя написал

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

Кажется, начинаю понимать, но как тут получить результирующие площяди 2 фигур?

Игрок идет по полю (размером 100х100) и сохраняет координаты передвежения в масссивах Koordх и Koordy с кол-вом записей n

Pol#x и Pol#y - массивы, в которых сохраняются посчитанные координаты.
kol# - кол-во подсчитанных координат
(можно конечно использовать двухмерные массивы)


1) При пересечении игроком края поля:

Запускаем цикл обработки поля
(может где-то пропустил begin или end. Короче к синтаксису сильно не придерайтесь)

//первый цикл

For y:=1 to 100 do begin
F:=1
For x:=1 to 100 do begin
For i:=1 to n do begin

If Koordx[i] = x then begin

If Koordy[i]=y then
If F=0 then
F:=1 else
F:=0;
end
else
kol1:=kol1+1;
Pol1x[kol1]:=x;
Pol1y[kol1]:=y;
end;
end;
end;

//второй цикл

For x:=1 to 100 do begin
F:=1
For y:=1 to 100 do begin
For i:=1 to n do begin

If Koordx[i] = x then begin

If Koordy[i]=y then
If F=0 then
F:=1 else
F:=0;
end
else
kol2:=kol1+1;
Pol2x[kol2]:=x;
Pol2y[kol2]:=y;
end;
end;

//третий цикл

For x:=1 to 100 do begin
F:=1
For y:=100 to 1 do begin
For i:=1 to n do begin

If Koordx[i] = x then begin

If Koordy[i]=y then
If F=0 then
F:=1 else
F:=0;
end
else
kol3:=kol1+1;
Pol3x[kol3]:=x;
Pol3y[kol3]:=y;
end;
end;

//четвертый цикл

For y:=1 to 100 do begin
F:=1
For x:=100 to 1 do begin
For i:=1 to n do begin

If Koordx[i] = x then begin

If Koordy[i]=y then
If F=0 then
F:=1 else
F:=0;
end
else
kol4:=kol4+1;
Pol4x[kol1]:=x;
Pol4y[kol1]:=y;
end;
end;
end;


Долее сравниваем kol1 kol2 kol3 kol4 и выбрав наименьшее удаляем координаты хранящиесе в массивах Pol#x и Pol#y - соответственно

2) При пересечении игроком своего пути:

Если я правильно понял последнюю фразу в 1), то на твоей картинке удалится маленький кусочек справа, являющийся частью одной из областей...
Сам код не читал.

нет

А, все наоборот - kol1, kol2, kol3 и kol4 - это то, что на картинке заштриховано?
Тогда неправильно отработает случай, когда внешняя часть суммарно больше внутренней.

Почему?