|
Вопрос # 6 150/ вопрос решён / |
|
Здравствуйте, эксперты!
Помогите с написанием программы в Delphi с использованием технологии структурного программирования, т.е. код в виде иерархической системе блоков.
Среди треугольников с вершинами в заданном множестве точек на плоскости узнать такой, стороны которого содержат максимальное число точек заданного множества.
Если код никто не сможет написать, то хотя бы по решению, по алгоритму помогите...
 |
Вопрос задал: smokergo (статус: Посетитель)
Вопрос отправлен: 21 мая 2012, 22:55
Состояние вопроса: решён, ответов: 1.
|
Ответ #1. Отвечает эксперт: Вадим К
Здравствуйте, smokergo!
Код будет не сложный. Ввод координат точек - не сложная задача.
А вот дальше интереснее. Вначале смотрим тут http://www.cyberforum.ru/pascal/thread111985.html алгоримт, который умеет проверять, находится ли точка внутри треугольника.
Дальше делам тройной вложенный цикл по точкам, проверяем, что выбрали разные точки и внутри него запускаем 4 (!!) цикл, который, для каждой оставшейся точки проверит, находиться ли она внутри треугольника, считает их кол-во. Дальше задача сводиться к классической задачи поиска максимума.
Но у этого алгоритма большая сложность - уже при 10 точках, получаем 10*9*8 = 720 треугольников, для которых нужно проверить 7 точек (для каждого).
 |
Ответ отправил: Вадим К (статус: Академик)
Время отправки: 23 мая 2012, 16:40
Оценка за ответ: 5
|
Мини-форум вопроса
Всего сообщений: 2; последнее сообщение — 26 мая 2012, 12:19; участников в обсуждении: 2.
|
Толяныч (статус: 4-ый класс), 24 мая 2012, 10:49 [#1]:
>> стороны которого содержат
Насколько я понял, точки должны лежать не внутри треугольника, а на его сторонах.
|
|
Drinkenz (статус: 1-ый класс), 26 мая 2012, 12:19 [#2]:
За основу взят Вопрос #5838 и ответ Егора.
{
вначале по исходным 4 точкам строю 3 треугольника,
используя две вершины тругольника и точку.
проверяю у полученных треугольников направление обхода (по/против часовой).
если направление всех тругольников совпали то точка лежит внутри треугольника,
если треугольники обходятся в разном направлении - снаружи.
}
function sign(x: extended): integer;
begin
if x=0 then result:=0
else result:=round(x/abs(x));
end;
function inTreug(x,y: array of extended): boolean;
var i: integer;
f1,f2,f3: integer;
begin
f1:=sign((x[1]-x[0])*(y[3]-y[1])-(x[3]-x[1])*(y[1]-y[0]));
f2:=sign((x[2]-x[1])*(y[3]-y[2])-(x[3]-x[2])*(y[2]-y[1]));
f3:=sign((x[0]-x[2])*(y[3]-y[0])-(x[3]-x[0])*(y[0]-y[2]));
i:=0; // cколько точек лежит на прямых
if f1=0 then inc(i);
if f2=0 then inc(i);
if f3=0 then inc(i);
case i of
0: result:=not((f1=-f2)or(f1=-f3)or(f2=-f3));
1: result:=not((f1=-f2)or(f1=-f3)or(f2=-f3)); // лежит на прямой, которой принадлежит сторона треуг.
2: result:=true;// точка совпала с вершиной
3: result:=true;// совпали все 4 точки =)
end;
end;
|
20 июня 2012, 21:12: Вопрос перемещён из тематического раздела Delphi » Общие вопросы по программированию в раздел Delphi » Алгоритмы, преобразования модератором Ерёмин А.А.
20 июня 2012, 21:13: Статус вопроса изменён на решённый (изменил модератор Ерёмин А.А.): Кажется, решено.
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
