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

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

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

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


Гость






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

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

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


Смотрю...
*****

Группа: Пользователи
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

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


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


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

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

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


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


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

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


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

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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

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

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


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


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

Ладно, все равно всем спасибо. Буду полностью решать задачу сам, если ни у кого нет никаких мыслей unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

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

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


Цитата
Что то я не врубился... почему на 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 и т.д.
просто нарисуйте и поймете
конечно многие четырехугольники будут совпадать, но будут и уникальные

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


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

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


Уникальный
**

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

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


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

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


--------------------
Век живи, век учи С © by Jahnerus
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


N337
****

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

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


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

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


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

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

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


Никак не могу найти верный алгоритм определения принадлежности точки четрехугольнику????
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Andy

С английским проблемы есть? Если нет, то зайди вот сюда. Здесь описан сам алгоритм, и есть исходники на С...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

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

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


С таким английским проблемы есть :p2:
Можете в общем объяснить алгоритм.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Перевод:

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

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


Бывалый
***

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

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


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

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


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

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


Бывалый
***

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

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


Код
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 (логарифм) равен нулю или имеет отрицательное значение;
произошло переполнение стека сопроцессора.


Сообщение отредактировано: Флогримм -


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


Гость






Флогримм
Я бы переписал функцию 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;
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Бывалый
***

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

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


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

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

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


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

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

Сообщение отредактировано: Флогримм -


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


Гость






Флогримм
Какую погрешность ты хочешь вычислить?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

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

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


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


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


Гость






Andy
Вот здесь я нашел еще один алгоритм (правда, он на С, но это неважно...) ;)

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

Код

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.


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

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

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

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


Или алгоритм не работает, или я его не верно понимаю… Так, что, пожалуйста, объясни прогу тугоуму rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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