IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V < 1 2  
 Ответить  Открыть новую тему 
> Четырехугольник
сообщение
Сообщение #21


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


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

(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м. предыдущее сообщение)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #22


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


Volvo

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

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

Вот, вроде все сформулировал к решению задачи, smile.gif но че-то все не клеится. unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #24


Гость






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

Добавлено

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

Сообщение отредактировано: volvo -


Прикрепленные файлы
Прикрепленный файл  ANDY.PAS ( 3.07 килобайт ) Кол-во скачиваний: 239
 К началу страницы 
+ Ответить 
сообщение
Сообщение #25


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


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

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

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

Вопрос такой: этот алгоритм применим для любых многоугольников (значит, я все-таки в чем-то ошибся при вычислении) без пересечений или нет (значит надо подальше выбросить эту чушь из головы)?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #26


Гость






Andy

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


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


Да, я тоже не встречал. Мне его порекомендовали и сказали, что он применим для всех многоугольников без пересечений.
Ладно, похоже что более двух дней я потерял попусту smile.gif unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #28


Бывалый
***

Группа: Пользователи
Сообщений: 253
Пол: Мужской

Репутация: -  4  +


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


компьютер представляет число в виде десятичной дроби, поэтому, когда мы вычисляем значение площади или длинны ребра, мы получаем именно такое значение, но ведь часть его сокращается, тем более дробь может быть с периодом и т.д. опоэтому, когда мы будем сравнивать результаты
Код
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х треугольников, которые образуются при соединении четвертой точки и вершин треуголика,
поэтому нужно найти погрешность и сравнить как-то по-другому

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


--------------------
Я не буду жить с этой злобой внутри / Я не буду частью смертельной цепи / Я не буду потребителем твоих идей / Я не буду никогда убивать зверей (Unconform)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #29


Бывалый
***

Группа: Пользователи
Сообщений: 253
Пол: Мужской

Репутация: -  4  +


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


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

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


--------------------
Я не буду жить с этой злобой внутри / Я не буду частью смертельной цепи / Я не буду потребителем твоих идей / Я не буду никогда убивать зверей (Unconform)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #30


Гость






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

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

Я думаю, точности 19 знаков после запятой должно хватить, тем более, что абсолютной точности добиться невозможно...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #31


Гость






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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #32


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


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

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

Сообщение отредактировано: Andy -


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #33


Гость






Andy

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

Заметь: «А», «Б», «В» - невыпуклые, т.е. надо проверять на выпуклость...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #34


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


А именно? Там должно, наверное, свойство выпуклости какое-то существовать. Я что-то не припоминаю.... :p2:
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #35


Гость






Andy
Смотри вот тут... По-моему, алгоритм должен работать, но если не будет - говори, найдем ошибки lol.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #36


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


Спасибо, всем участникам. Я позавчера все-таки написал эту программу, используя алгоритм от 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;


Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V < 1 2
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 9.12.2021 11:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name