Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Четырехугольник

Автор: Andy 12.11.2004 22:07

Запрограммировать на Pascal:

Найти четырехугольник с вершинами в заданных точках, содержащий наибольшее число заданных точек. (Графика не нужна)

Здесь необходимо через заданные точки построить всевозможное количество четырехугольников, вычисляя количество точек, которые попадают внутрь его. Никак не могу додуматься до алгоритма построения всевозможных вариантов четырехугольника. Размышляю так: через четыре точки можно построить 24 четырехугольника, через 5 – 120, т.е. берется факториал от количества точек. Т.е. для 4 точек надо перебрать 24 комбинации, для 5 – 120. Но как это свести это в единый алгоритм? Или может, есть вариант куда проще?

Автор: APAL 12.11.2004 22:16

Что то я не врубился... почему на 4-ех точках можно построить 24 четырехугольника? Разве не ОДИН???

Автор: Andy 13.11.2004 0:16

Четырехугольник - это не параллелограмм или ромб. У него не должны быть параллельны стороны и т.п. Главное, чтобы 3 точки не лежали на одной прямой. Поэтому углы могут быть любые.
Пользователь ввел координаты 4-ех точек. Я не знаю четырехугольник это или нет. На четырх точках может быть 24 ВАРИАНТА построения четырехугольника (ведь линии между точками я могу соединять в любом направлении).
Но в итоге из них может быть четырехугольником только один (но может быть и больше, не обязательно один, так как опять же линии между точками я могу соединять в любом направлении: могу соединить точки так T1 - T2, T2 - T3, T3 - T4, T4 - T1, но могу и соединить и так T1 - T4, T4 - T3, T3 - T2, T2 - T1
:- конечено же, если данная фигура является четырехугольником (ведь основная цель задачи: найти максимальное количество точек внутри четырехугольника, т.е. рассмотреть всевозможные варианты построения четырехугольника и определить какой из них является решением)).

Автор: Altair 13.11.2004 11:17

Цитата
Что то я не врубился... почему на 4-ех точках можно построить 24 четырехугольника? Разве не ОДИН???

Я тоже...
если 4 точки и вершиины прямоугольника должны быть этими точками то один.
А если эти точки должны быть на ребрах(все равно каких) то бесконечность ...
blink.gif

Автор: Andy 13.11.2004 22:23

Цитата
если 4 точки и вершиины прямоугольника должны


Я же сказал, что у меня ЧЕТЫРЕХУГОЛЬНИК, а не прямоугольник!!( ЭТО РАЗНЫЕ ВЕЩИ! (ВЫ В ШКОЛЕ УЧИЛИСЬ? blink.gif ).

Ладно, все равно всем спасибо. Буду полностью решать задачу сам, если ни у кого нет никаких мыслей unsure.gif

Автор: Флогримм 14.11.2004 10:37

Цитата
Что то я не врубился... почему на 4-ех точках можно построить 24 четырехугольника? Разве не ОДИН???

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

если мы имеем точки n(пусть 4) 1,2,3,4 их можно соединить в разных комбинациях, кол-во которых !n

можно соединить 1-2 2-3 3-4 4-1, можно 1-3 3-4 4-2 2-1 и т.д.
просто нарисуйте и поймете
конечно многие четырехугольники будут совпадать, но будут и уникальные

приаттачил рисунок, посмотрите, что Я имею в виду
может я и ошибаюсЬ



Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Jahnerus 14.11.2004 12:28

Флогримм:

Цитата
можно соединить 1-2 2-3 3-4 4-1, можно 1-3 3-4 4-2 2-1 и т.д.
просто нарисуйте и поймете

Помойму (я конечно могу ошибаться) но вторая часть рисунка которая красная больше похожа на 2 треугольника чем на 4-ёх угольник.

Автор: xds 14.11.2004 15:38

Цитата(Andy @ 13.11.04 18:23)
Я же сказал, что у меня ЧЕТЫРЕХУГОЛЬНИК, а не прямоугольник!!( ЭТО РАЗНЫЕ ВЕЩИ! (ВЫ В ШКОЛЕ УЧИЛИСЬ? blink.gif ).

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

Автор: Andy 14.11.2004 22:57

Никак не могу найти верный алгоритм определения принадлежности точки четрехугольнику????

Автор: volvo 14.11.2004 23:10

Andy

С английским проблемы есть? Если нет, то зайди http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/. Здесь описан сам алгоритм, и есть исходники на С...

Автор: Andy 14.11.2004 23:18

С таким английским проблемы есть :p2:
Можете в общем объяснить алгоритм.

Автор: volvo 14.11.2004 23:37

Перевод:

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

Допустим, что полигон состоит из N точек (xi, yi) где i = [0 .. N-1]. Последняя
точка (xN,yN) совпадает с первой (x0,y0), то есть, полигон замкнут. Для определения состояния точки (xp,yp) допустим, что что из точки (xp,yp) горизонтально (вправо) исходит луч. Если число раз, когда этот луч пересекает линии, составляющие полигон, четно, то точка (xp,yp) лежит снаружи полигона, тогда как нечетность этого числа означает нахождение точки (xp,yp) внутри полигона. На рисунке показаны несколько примеров.

Автор: Флогримм 15.11.2004 10:01

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

Т.е. если S(1A3)+S(1A2)+S(2A4)+S(4A3)=S(1234) =>>> принадлежит
иначе нет


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Флогримм 15.11.2004 12:00

Код
program tri;
uses crt;

function len(a1,b1,a2,b2:byte):real;{длинна отрезка с коорд (a1;b1) и (a2;b2)}
begin
len:=sqrt(sqr(a1-a2)+sqr(b1-b2));
end;

function S(l1,l2,l3:real):real;{находим площадь фигуры(треугольника) по формуле Герона}
var p:real;
begin
p:=(l1+l2+l3)/2;
S:=sqrt(p*(p-l1)*(p-l2)*(p-l3));
end;

var
x1,x2,x3,x4,y1,y2,y3,y4:byte;
flag:boolean;
begin
clrscr;

write('x1,y1> ');
readln(x1,y1);

write('x2,y2> ');
readln(x2,y2);

write('x3,y3> ');
readln(x3,y3);

write('x4,y4> ');
readln(x4,y4);

flag:=
(
S(len(x1,y1,x2,y2),len(x2,y2,x3,y3),len(x3,y3,x1,y1))=
S(len(x1,y1,x2,y2),len(x2,y2,x4,y4),len(x4,y4,x1,y1))+
S(len(x2,y2,x3,y3),len(x3,y3,x4,y4),len(x4,y4,x2,y2))+
S(len(x1,y1,x4,y4),len(x4,y4,x3,y3),len(x3,y3,x1,y1))
);
writeln('[',x4,';',y4,']',flag);
end.

<_< почему не работает?
и как вычислить погрешность?

выдает:
207 Invalid floating point operation
Код
207 Invalid floating point operation(Недопустимая операция с плавающей запятой) .

Возможные причины сообщения:

аргумент функций TRUNC или ROUND не может быть преобразован в целое число, находящееся внутри диапазона типа LONGINT (от -2147483648 до +2147483647);
отрицательный аргумент функции SQRT (извлечение квадратного корня);
аргумент функции LN (логарифм) равен нулю или имеет отрицательное значение;
произошло переполнение стека сопроцессора.

Автор: volvo 15.11.2004 13:45

Флогримм
Я бы переписал функцию S по-другому...

Код

function S(l1,l2,l3:real):real;{находим площадь фигуры(треугольника) по формуле Герона}
var p:real;
begin
p:=(l1+l2+l3)/2; { по формуле Герона p - полупериметр }
S:=sqrt(abs((p-l1)*(p-l2)*(p-l3)/p)); {abs - избегаем взятия корня из отриц. числа}
end;

Автор: Флогримм 15.11.2004 20:33

Цитата
p:=(l1+l2+l3)/2; { по формуле Герона p - полупериметр }

ты прав!
я когда уже от Нета отключился, тему перечитал, обнаружил свою ошибку: надо 2, а не 3

Цитата
S:=sqrt(abs((p-l1)*(p-l2)*(p-l3)/p)); {abs - избегаем взятия корня из отриц. числа}


ты прав! :yes:
спасибо

как вычислить(учесть) погрешность?

Автор: volvo 15.11.2004 20:58

Флогримм
Какую погрешность ты хочешь вычислить?

Автор: Andy 16.11.2004 1:08

Цитата
А можно другой алгоритм(хотя менее эффективный):
с точкой(принадлежность/непринадлежность которой к данной фигуре нужно установить) соединить все вершины данной фигуры.


Вот-вот, Флогримм. Я тоже хотел через площадь решать ..но……..
Алгоритм такой. Для вычисления площади четырехугольника надо разделить четырехугольник на два треугольники и спокойно по Герону вычислить их площадь. Чтобы разделить четырехугольник я собирался брать как бы диагональ, т.е. например, верхнюю левую точку и правую нижнюю и считать. НО. Опять про тоже. Четырехугольники бывают разные. Например, такой (не знаю как прикреплять картинки, поэтому даю в точках) T1(2,2) T2( 4,3) T3(4,6) T4(6,2). По этим точкам построен четырехугольник T1-T3-T4-T2-T1. Но здесь теоретически можно взять диагональ T1->T4 – почему бы и нет, она удовлетворяет моим условиям – но это, конечно же, неверно. И все мои практически проблемы с этой задачей связаны как раз с четырехугольником такого типа, для четырехугольника на подобии прямоугольника надо считать так, для такого четырехугольника по-другому.

Автор: volvo 16.11.2004 2:08

Andy
http://www.gamedev.ru/forum/?action=showtopic&group=0&topic=2131 я нашел еще один алгоритм (правда, он на С, но это неважно...) ;)

Вот так он выглядит на Паскале.

Код

Type
 TPoint =
   Record
     X, Y: Integer;
   End;

Function min(a, b: Integer): Integer;
 Begin
   min := a;
   if b < a Then min := b
 End;

Function max(a, b: Integer): Integer;
 Begin
   max := a;
   if b > a Then max := b
 End;

Function isInside(Const a: Array Of TPoint;
        b: TPoint; n: Integer): Boolean;
 Var
   i, j, Count: Word;
   T: Double;
 Begin
   Count := 0;
   For i := 0 To Pred(n) Do
     Begin
       j := (i+1) mod n;
       If a[i].Y = a[j].Y Then Continue;

       If (a[i].Y > b.Y) and (a[j].Y > b.Y) Then Continue;
       If (a[i].Y < b.Y) and (a[j].Y < b.Y) Then Continue;
       If (max(a[i].Y, a[j].Y) = b.Y)
         Then Inc(Count)
         Else
           Begin
             If min(a[i].Y, a[j].Y) = b.y Then Continue
             Else
               Begin
                 T := (b.Y - a[i].Y) / (a[j].Y - a[i].Y);
                 If a[i].X + T * (a[j].X - a[i].X) >= b.X Then Inc(Count)
               End
           End;
     End;
   IsInside := ((Count and $0001) <> 0)
 End;

Const
 arr: Array[0 .. 3] Of TPoint =
   (
     { Точки - в порядке соединения в многоугольник !!!
        Если многоугольник = T1-T3-T4-T2-T1, то так: }
     (X:2;Y:2), {T1}
     (X:4;Y:6), {T3}
     (X:6;Y:4), {T4}
     (X:4;Y:3)  {T2}
   );

Const
 Check1: TPoint = (X:7; Y:2);
 Check2: TPoint = (X:1; Y:7);

Var
 b: Boolean;
Begin
 b := IsInside(arr, Check1, 4);
 b := IsInside(arr, Check2, 4);
End.


Я его погонял с твоими координатами - работает, вроде, правильно. Попробуй.

Автор: Andy 16.11.2004 3:07

Или алгоритм не работает, или я его не верно понимаю… Так, что, пожалуйста, объясни прогу тугоуму rolleyes.gif

Автор: Andy 16.11.2004 3:26

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

(X:1;Y:2),
(X:1;Y:4),
(X:3;Y:4),
(X:3;Y:2)

Check1: TPoint = (X:1; Y:3);

Или
Check1: TPoint = (X:1; Y:3);

Ответ b=false. А точка принадлежит.

Или я что-то не так понял в работе программы? (cм. предыдущее сообщение)

Автор: volvo 16.11.2004 3:34

Andy
sad.gif
Да, у меня тоже начало глючить (причем в самых неожиданных местах)... Значит тот алгоритм был со сбоями. Ладно, найдем другой :yes:

Автор: Andy 16.11.2004 3:49

Volvo

В принципе алгоритм с лучом (тот, который ты переводил с англ.) 100%.

Тут я, так понимаю, надо все линии записать в виде уравнений прямых, луч, кстати, тоже надо записать как прямую (т.е. все-таки его ограничить). И брать по отдельности каждую прямую четырехугольника вместе с лучом. Решить систему уравнений. Получим точку, или точки, или вообще ничего не получим и сделать соответствующие выводы после перебора всех линий четырехугольника (четное число точек пересечения => не принадлежит, нечетное => принадлежит).
Здесь вся фишка в поиске точки пересечения. Пока сложновато, если учесть, что прямая представляется в виде Ax+By+C=0… Тут, кстати тоже не решена проблема: если точка принадлежит прямой По данному алгоритму она будет считаться как лежащая вне четырехугольника. Наверное, надо будет просто определить эту принадлежность.

Вот, вроде все сформулировал к решению задачи, smile.gif но че-то все не клеится. unsure.gif

Автор: volvo 16.11.2004 4:22

Andy
проверь РМ... ;)

Добавлено

Вот та функция, о которой я говорил...


Прикрепленные файлы
Прикрепленный файл  ANDY.PAS ( 3.07 килобайт ) Кол-во скачиваний: 303

Автор: Andy 16.11.2004 16:17

Да, пока работает. Но надо еще попроверять <_< .
Я хотел узнать. Я сначала для решения этой задачи использовал алгоритм векторного произведения, т.е.:

Брал четырехугольник - это 4 вектора V(4). Причем конец каждого вектора смотрит в начало следующего. Направление обхода - против часовой стрелки. Для каждого вектора V:
1) Вычислить вектор U начало которого совпадает с V а конец с искомой точкой.
2) Векторное произведение (U,V) должно быть положитным для всех четырех случаев. Если оно отрицательно, значит точка по правую сторону от вектора V. То есть НЕ ПРИНАДЛЕЖИТ четырехугольнику.

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

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

Автор: volvo 16.11.2004 18:00

Andy

Я никогда не встречал, чтобы этот алгоритм использовали применительно к многоугольникам. Обычно его применяют после триангуляции (разбиения на треугольники) для проверки принадлежности точки к каждому треугольнику.

Автор: Andy 16.11.2004 18:47

Да, я тоже не встречал. Мне его порекомендовали и сказали, что он применим для всех многоугольников без пересечений.
Ладно, похоже что более двух дней я потерял попусту smile.gif unsure.gif

Автор: Флогримм 17.11.2004 11:37

Цитата
Какую погрешность ты хочешь вычислить?


компьютер представляет число в виде десятичной дроби, поэтому, когда мы вычисляем значение площади или длинны ребра, мы получаем именно такое значение, но ведь часть его сокращается, тем более дробь может быть с периодом и т.д. опоэтому, когда мы будем сравнивать результаты
Код
flag:=
(
S(len(x1,y1,x2,y2),len(x2,y2,x3,y3),len(x3,y3,x1,y1))=
S(len(x1,y1,x2,y2),len(x2,y2,x4,y4),len(x4,y4,x1,y1))+
S(len(x2,y2,x3,y3),len(x3,y3,x4,y4),len(x4,y4,x2,y2))+
S(len(x1,y1,x4,y4),len(x4,y4,x3,y3),len(x3,y3,x1,y1))
);

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

надеюсь понял, что я имею в виду

Автор: Флогримм 17.11.2004 11:40

Цитата
...Четырехугольники бывают разные. Например, такой (не знаю как прикреплять картинки, поэтому даю в точках) T1(2,2) T2( 4,3) T3(4,6) T4(6,2). По этим точкам построен четырехугольник...


когда создаешь тему или отправляешь сообщение на форум просто прикрепляй графическое изображение(с помощью "Прикрепить файл")

оно автоматически вставиться в конец сообщения

Автор: volvo 17.11.2004 14:47

Флогримм
Можно уменьшить погрешность вычисления площадей переходом от типа real(11-12 значащих цифр) к типу extended(19-20 значащих цифр).

Хотя практически это ничего не меняет (все вычисления и так ведутся в extended), но если описАть переменные, как extended, то не будет происходить усечение до размеров real (дополнительные 7-8 знаков после запятой добавят точности). Плюс ко всему - real очень медленный тип (он был оптимизирован для работы без сопроцессора, а если сопроцессор имеется, то его использование приведет к преобразованию real->extended, затем вычисления, а после этого - назад: extended->real)

Я думаю, точности 19 знаков после запятой должно хватить, тем более, что абсолютной точности добиться невозможно...

Автор: Guest 18.11.2004 11:39

volvo, у меня есть решение к задаче, там написано так:

Код

...
flag:=
(
1.000001*S(len(x1,y1,x2,y2),len(x2,y2,x3,y3),len(x3,y3,x1,y1))<
S(len(x1,y1,x2,y2),len(x2,y2,x4,y4),len(x4,y4,x1,y1))+
S(len(x2,y2,x3,y3),len(x3,y3,x4,y4),len(x4,y4,x2,y2))+
S(len(x1,y1,x4,y4),len(x4,y4,x3,y3),len(x3,y3,x1,y1))
);
writeln('[',x4,';',y4,'] - ',flag);
...


обрати внимание: умножаем на некий коэффициент(почему именно такой?) и прверяем не на равенство, а на то, какая величина больше

почему? в упор не понимаю...

вот весь код моей проги:
Код
program tri;
uses crt;

function len(a1,b1,a2,b2:byte):real;
begin
len:=sqrt(sqr(a1-a2)+sqr(b1-b2));
end;
function S(l1,l2,l3:real):real;
var p:real;
begin
p:=(l1+l2+l3)/2;
S:=sqrt(abs(p*((p-l1)*(p-l2)*(p-l3)));
end;

var
x1,x2,x3,x4,y1,y2,y3,y4:byte;
flag:boolean;
begin
clrscr;

write('x1,y1> ');
readln(x1,y1);

write('x2,y2> ');
readln(x2,y2);

write('x3,y3> ');
readln(x3,y3);

write('x4,y4> ');
readln(x4,y4);

flag:=
(
1.000001*S(len(x1,y1,x2,y2),len(x2,y2,x3,y3),len(x3,y3,x1,y1))<
S(len(x1,y1,x2,y2),len(x2,y2,x4,y4),len(x4,y4,x1,y1))+
S(len(x2,y2,x3,y3),len(x3,y3,x4,y4),len(x4,y4,x2,y2))+
S(len(x1,y1,x4,y4),len(x4,y4,x3,y3),len(x3,y3,x1,y1))
);
writeln('[',x4,';',y4,'] - ',flag);
end.

Автор: Andy 18.11.2004 22:54

Кстати, все те кто решает через площадь! Вы находите площадь четырехугольника, предварительно, разделив его на треугольники. Но см. рис. Случай “Г”. Здесь соединяешь диагональ 1 – 3 (или 2 – 4) и находишь площадь треугольника. А вот в случае «А», «Б», «В» такой способ деления на треугольники не подходит. Т.К. для случая «А» верна диагональ только 2 – 4 (а, не 1 – 3),
для случая «Б» верна диагональ только 1– 4 (а, не 2 – 3), для случая «В» верна диагональ только 3– 4 (а, не 1 – 2).

Как можно распознавать такие четырехугольники (случаи «А», «Б», «В»)


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: volvo 18.11.2004 23:04

Andy

Цитата
Как можно распознавать такие четырехугольники

Заметь: «А», «Б», «В» - невыпуклые, т.е. надо проверять на выпуклость...

Автор: Andy 19.11.2004 0:53

А именно? Там должно, наверное, свойство выпуклости какое-то существовать. Я что-то не припоминаю.... :p2:

Автор: volvo 19.11.2004 0:55

Andy
Смотри http://pasc.al.ru/www/exampl20.htm... По-моему, алгоритм должен работать, но если не будет - говори, найдем ошибки lol.gif

Автор: Andy 21.11.2004 1:09

Спасибо, всем участникам. Я позавчера все-таки написал эту программу, используя алгоритм от Volvo (мои особые благодарности).
Единственное, что смущает: никак толком полностью не могу уловить смысл этой функции PointInSidebar (алгоритм работы).
Буду очень признателен, если подскажите.
Вот эта функция:

Код

Function PointInSidebar(Const SideBar: Array Of TPoint;
        p: TPoint; Count: Integer): Boolean;
 Var
   x1,y1,x2,y2: Double;
   x0, y0, sum, divisor: Double;
   i: integer;
 Begin
   sum := 0;
   y0 := p.y;
   x0 := p.x;
   For i := 0 to Pred(count-1) do
     Begin
       x1:=sidebar[i].x;
       y1:=sidebar[i].y;
       x2:=sidebar[i+1].x;
       y2:=sidebar[i+1].y;

       divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
       divisor := divisor + 1.0E-10;

       Sum := sum + (
       -arctan( (-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2 )/divisor)+
       arctan( (-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0 )/divisor)
       );
     End;

   x1:=sidebar[count-1].x;
   y1:=sidebar[count-1].y;
   x2:=sidebar[0].x;
   y2:=sidebar[0].y;

   divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
   divisor := divisor + 1.0E-10;
   Sum := sum + (
   -arctan((-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2)/divisor)+
   arctan((-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0)/divisor)
   );

   pointinsidebar := not (abs(Sum) < 0.0001)
 End;


Спасибо.