Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Pascal] Динамические массивы, модуль "Многоугольник" 
V
    Опции темы
KasMP
Дата 7.5.2008, 18:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата
Разработать модуль «Многоугольник» на основе динамического массива вершин.
Реализовать
  •  вычисление периметра;
  •  вычисление площади;
  •  проверку на выпуклость;
  •  овыпукление многоугольника (т. е. построение наименьшего по площади выпуклого многоугольника, содержащего заданный);
  •  пересечение двух выпуклых многоугольников, проверку принадлежности точки многоугольнику (возможно, невыпуклому).
Input/Output в/из файл(а).

С первым пунктом (вычисление периметра) все очевидно: идем по списку (состоящему из записей с тремя полями: x, y, next), накапливаем значение периметра (используя формулу расстояния между двумя точками с известными координатами: d^2=(x1-x2)^2+(y1-y2)^2); упростить процесс у меня не получилось (там же сумма корней получается, ничего с ней не сделаешь…).

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

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

Помогите, пожалуйста smile . Не бросайте студентку на произвол судьбы smile !!
PM MAIL   Вверх
Akina
Дата 10.5.2008, 22:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
1) да.
2) не сработает, ибо ошибочно. Использовать разбиение на треугольники.
3) проверка внешних углов при каждой вершине.
4) ликвидация "впуклых" вершин по одной.
5) непонятно, о чем речь


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
maxim1000
Дата 10.5.2008, 22:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
вычислять площадь можно по такой формуле (то ли это формула Грина, то ли из неё выводится):
s=sum[i=1..N]( (x[i+1]-x[i])*(y[i+1]+y[i])/2 ) (ну ещё модуль взять)



--------------------
qqq
PM WWW   Вверх
KasMP
Дата 11.5.2008, 00:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Akina @  10.5.2008,  22:08 Найти цитируемый пост)
3) проверка внешних углов при каждой вершине.

Скажем, есть у нас три пары координат: вершины А1, А2, А3.
    А3
    /
А2
    \
     А1
Как посчитать угол - понятно (через скалярное произведение векторов).
А вот как определить, будет посчитанный угол внешним или внутренним? Ведь возможны обе ситуации:
user posted image

Цитата(Akina @  10.5.2008,  22:08 Найти цитируемый пост)
4) ликвидация "впуклых" вершин по одной.
Для этого надо уметь определять "впуклые" вершины smile (а мы пока этому комп не научили).
Цитата(Akina @  10.5.2008,  22:08 Найти цитируемый пост)
5) непонятно, о чем речь 
Пока можно подумать о "проверке принадлежности точки многоугольнику (возможно, невыпуклому)". А про пересечение я уточню smile .


Цитата(maxim1000 @  10.5.2008,  22:32 Найти цитируемый пост)
вычислять площадь можно по такой формуле (то ли это формула Грина, то ли из неё выводится):
s=sum[i=1..N]( (x[i+1]-x[i])*(y[i+1]+y[i])/2 ) (ну ещё модуль взять)
Если я правильно поняла, то вершина 1 и вершина (i+1) совпадают.
Т.е. если смотреть со стороны периметра и площади, то нам больше всего подходит циклический способ организации динамического массива (проще говоря, мы должны указатель последней записи направить на первую).
Да smile ?!
(большое спасибо за хорошую, очень удобную формулу smile !)
PM MAIL   Вверх
maxim1000
Дата 11.5.2008, 15:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата(KasMP @  11.5.2008,  00:01 Найти цитируемый пост)
Т.е. если смотреть со стороны периметра и площади, то нам больше всего подходит циклический способ организации динамического массива (проще говоря, мы должны указатель последней записи направить на первую).

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


Цитата(KasMP @  11.5.2008,  00:01 Найти цитируемый пост)
А вот как определить, будет посчитанный угол внешним или внутренним? Ведь возможны обе ситуации

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

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

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

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


--------------------
qqq
PM WWW   Вверх
KasMP
Дата 11.5.2008, 19:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(maxim1000 @  11.5.2008,  15:41 Найти цитируемый пост)
нужно выбрать направление обхода вершин (вполне естественно взять то, в котором задан многоугольник) и для каждого угла выяснить, вправо он поворачивает или влево

Определить это через скалярное произведение не получается: его знак говорит о том, что угол острый/прямой/тупой, а направление никак не задействовано.
Если считать угол между векторами, то тоже не получается: arccos(x) - мы можем повернуть на x в любу сторону.
Если считать изменение координат (например, абсцисса увеличилась и ордината уменьшилась, абсцисса и ордината увеличились, т.п.), то придется сначала искать крайние точки (нижнюю, левую, верхнюю, правую), потому что при переходе через эти точки изменение координат меняют значение: находимся между крайней левой и крайней верхней точками, увеличение абсциссы и ординаты - поворот вправо; находимся между крайней правой и крайней левой точками, увеличение абсциссы и ординаты - поворот влево.
Как это определить? smile 
Цитата(maxim1000 @  11.5.2008,  15:41 Найти цитируемый пост)
ну а вообще, в будущем я бы советовал создавать по одной теме на каждый вопрос, тогда и заголовок можно точнее написать, что увеичит вероятность захода в тему человека, которому это интересно

Учту на будущее smile .
Цитата(maxim1000 @  11.5.2008,  15:41 Найти цитируемый пост)
ну а кроме того, по этим вопросам можно поискать, что уже есть на форуме
если мне не изменяет память, то определение площади и выпуклости уже где-то проскакивало 

Уже пробовала smile . Попробую еще smile .
PM MAIL   Вверх
maxim1000
Дата 11.5.2008, 21:57 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата(KasMP @  11.5.2008,  19:07 Найти цитируемый пост)
Определить это через скалярное произведение не получается: его знак говорит о том, что угол острый/прямой/тупой, а направление никак не задействовано.

для этого можно использовать векторное произведение
точнее - определитель, т.к. векторное произведение определяется в 3d

ax*by-ay*bx будет иметь разный знак в зависимости от того, в какую сторону направлен угол между a и b


--------------------
qqq
PM WWW   Вверх
KasMP
Дата 11.5.2008, 22:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(maxim1000 @  11.5.2008,  21:57 Найти цитируемый пост)
для этого можно использовать векторное произведение
точнее - определитель, т.к. векторное произведение определяется в 3d

ax*by-ay*bx будет иметь разный знак в зависимости от того, в какую сторону направлен угол между a и b 

Точно!
Да и я сама вспомнила про векторное произведение, хотела открыть тетрадку и проверить, а вместо этого пошла на кухню делать ужин и так и забыла smile .
Спасибо еще раз smile .
PM MAIL   Вверх
KasMP
Дата 13.5.2008, 11:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Akina @  10.5.2008,  22:08 Найти цитируемый пост)
5) непонятно, о чем речь

Итак, мы уточнили smile .

Пересечение двух выпуклых многоугольников.
Пересечение - часть, принадлежащая обоим многоугольникам, вершины которых задаются с помощью двух координат.
Например,
1) ((-5,-1),(2,7),(2,-1))*((-1,-1),(-1,2),(2,2),(4,0),(2,-3)) = ((-1,-1),(-1,2),(2,2),(2,-1))- многоугольник;
2) ((0,0),(0,1),(1,1),(1,0))*(0,0) = (0,0)- точка;
3) ((0,0),(0,1),(1,1),(1,0))*(5,5) = пустое множество;
4) ((0,0),(0,1),(1,1),(1,0))*((0,0),(0,5),(5,5),(5,0)) = ((0,0),(0,1),(1,1),(1,0))- первый многоугольник.

Проверка принадлежности точки многоугольнику (возможно, невыпуклому).
Тут все понятно smile .
(в смысле, задание понятно... а как делать - нефига непонятно!!!)

Это сообщение отредактировал(а) KasMP - 18.5.2008, 16:19
PM MAIL   Вверх
KasMP
Дата 18.5.2008, 16:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Люди, ну помогите, пожалуйста, с принадлежностью точки многоугольнику!
Если с определением выпуклости я как-то справлюсь (примерно понятно, что и как делать), то с принадлежностью вообще все очень туго!!!

 smile  smile 
PM MAIL   Вверх
Fortop
Дата 18.5.2008, 16:34 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
Подожди, почему туго.
Принадлежность точки треугольнику ты можешь определить?

Добавлено через 1 минуту и 52 секунды
Да, вот тебе статья навскидку
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B8%D0%BA%D0%B5

Добавлено через 2 минуты и 52 секунды
Вот тебе вторая статья
http://algolist.manual.ru/maths/geom/belong/poly2d.php


--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
KasMP
Дата 18.5.2008, 16:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Fortop @  18.5.2008,  16:34 Найти цитируемый пост)
Принадлежность точки треугольнику ты можешь определить?

Не знаю, сейчас подумаю...

Добавлено через 47 секунд
Цитата(Fortop @  18.5.2008,  16:34 Найти цитируемый пост)
Да, вот тебе статья навскидку
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B8%D0%BA%D0%B5 

О! Там, похоже, что-то стоящее smile . Посмотрю попозже, спасибо за хорошую ссылку smile .

Добавлено через 2 минуты и 43 секунды
Кстати, с пересечением тоже дела не очень... smile
Пожалуйста, не бросайте на растерзание судьбы smile беззащитную студентку smile .
PM MAIL   Вверх
KasMP
Дата 18.5.2008, 16:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Wikipedia)
Для проверки принадлежности точки треугольнику (а также выпуклому многоугольнику с любым числом вершин) можно применить и другой алгоритм. Заданная точка соединяется отрезками с вершинами треугольника. Если площадь исходного треугольника равна сумме площадей образовавшихся трёх треугольников, то считается, что точка принадлежит треугольнику.

Гм, и неужели нельзя изобрести такой треугольник и такую непринадлежащую ему точку, что указанная сумма площадей будет равно площади треугольника?
Имхо если постараться, то может получиться smile !
(а с многоугольником точно должно получиться изобрести!)

Это сообщение отредактировал(а) KasMP - 18.5.2008, 16:56
PM MAIL   Вверх
Fortop
Дата 18.5.2008, 16:58 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
KasMP, 
С пересечением тоже можно поискать ссылки smile

Не думая, алгоритмически я бы сделал так.

Взял бы каждую сторону многоугольников и проверил бы на пересечение с каждой стороной другого.
Если есть, то найти точки пересечения и определив направление обхода, бежал бы последовательно по узлам.
Например.
Если первое пересечение находится на стороне А1А2 и Б2Б3, а следующее А5А6 Б4Б5,то необходимо пробежаться по все фигуре
от точки пересечения  А1А2-Б2Б3 через А2А3, А4А5 до точки пересечения А5А6-Б4Б5 и назад через Б3Б4 до точки пересечения  А1А2-Б2Б3.

Хотя надо еще проверять выпуклость и впуклость.

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

А вообще smile пару запросов в Гугль, и думаю, там будут более оптимальные варианты, чем предложенный мной smile

Добавлено @ 17:00
Цитата(KasMP @  18.5.2008,  16:55 Найти цитируемый пост)
Гм, и неужели нельзя изобрести такой треугольник и такую непринадлежащую ему точку, что указанная сумма площадей будет равно площади треугольника?
Имхо если постараться, то может получиться  !
(а с многоугольником точно должно получиться изобрести!)

нет.

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

Добавлено через 4 минуты и 4 секунды
KasMP, если что-то не можешь понять - нарисуй на бумаге smile Так бывает гораздо проще.

А треугольник или многоугольник - разницы большой в этом случае нет.

Это сообщение отредактировал(а) Fortop - 18.5.2008, 17:01


--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
KasMP
Дата 18.5.2008, 17:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Fortop @  18.5.2008,  16:58 Найти цитируемый пост)
А вообще smile пару запросов в Гугль, и думаю, там будут более оптимальные варианты, чем предложенный мной smile

Да, но ведь нормальный программист должен хотя бы раз додуматься до всего этого сам.
(или хотя бы поразмышлять на эту тему, чтобы понять все нюансы и всю красоту оптимального варианта, понять свои ошибки и сделать вывод на будущее)
Цитата(Fortop @  18.5.2008,  16:58 Найти цитируемый пост)
нет.

Смотри. так как ты соединяещся с каждой вершиной. То площадь многоугольника ты захватишь в любом случае.
Но если точка лежит вне, то ты захватишь еще и лишнего smile 
И действительно smile  smile  .
(я уже нарисовала  smile )
PM MAIL   Вверх
Fortop
Дата 18.5.2008, 23:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
Цитата(KasMP @  18.5.2008,  17:07 Найти цитируемый пост)
Да, но ведь нормальный программист должен хотя бы раз додуматься до всего этого сам.
(или хотя бы поразмышлять на эту тему, чтобы понять все нюансы и всю красоту оптимального варианта, понять свои ошибки и сделать вывод на будущее)

Это классно smile Но кто из нас двоих собирается быть нормальным программистом? smile


--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
KasMP
Дата 20.5.2008, 07:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Я вчера наконец-то отошла от раздумий над алгоритмами и приступила к написанию программы.

Решила создать модуль, в котором будут нужные ВА.
В модуле были созданы типы для списка и некоторые переменные:
Код

type    TPointer=^TCoordinate;
        TCoordinate=record
            x, y: integer;
            next: TPointer;
            end;
var    start, step, finish: TPointer;
        num: integer; {число вершин многоугольника}


После процедур считывания первой вершины и всех остальных идут периметр и площадь (это мне удалось достаточно быстро и легко). Прошу каких-нибудь рекомендаций, замечаний.
Код

function Perimeter (var start: TPointer; var num: integer): real;
    var    i: integer;
        tempSum: real;
        tempStep, tempNext: TPointer;
        tempX, tempY: integer;
    begin
    tempSum:=0; tempStep:=start; tempNext:=start^.next;
    for i:=1 to num do
        begin
        tempX:=(tempStep^.x-tempNext^.x)*(tempStep^.x-tempNext^.x);
        tempY:=(tempStep^.y-tempNext^.y)*(tempStep^.y-tempNext^.y);
        tempSum:=tempSum+SQRT(tempX+tempY);
        tempNext:=tempNext^.next; tempStep:=tempStep^.next;
        end;
    Perimeter:=tempSum;
    end;

Код

function Square (var start: TPointer; var num: integer): real;
    var    i: integer;
        tempSum: real;
        tempStep, tempNext: TPointer;
        tempX, tempY: integer;
    begin
    tempSum:=0; tempStep:=start; tempNext:=start^.next;
    for i:=1 to num do
        begin
        tempX:=tempNext^.x-tempStep^.x;
        tempY:=tempNext^.y+tempStep^.y;
        tempSum:=tempSum+tempX*tempY;
        tempNext:=tempNext^.next; tempStep:=tempStep^.next;
        end;
    Square:=tempSum*0.5;
    end;

Дальше идет определение принадлежности точки многоугольнику: точка последовательно соединяется со всеми соседними вершинами, накапливается сумма площадей полученных треугольников (площадь каждого отдельного треугольника считается по формуле Герона); если накопленная сумма площадей равна площади многоугольника, то точка принадлежит многоугольнику (иначе не принадлежит, это понятно).
Очевидно, что при подсчете площадей двух соседних треугольников длина одной и той же стороны будет нужна 2 раза. Это учтено: длина каждой стороны считается один раз, а в цикле просто переводятся указатели.
Мне удалось найти у себя несколько ошибок: периметр вместо полупериметра, непереведенные на вершину вперед указатели и т.п.. Но функция по прежнему всегда выдает false.

Код

function PointInPolyhedron (var start: TPointer; var num: integer; var x, y: integer): boolean;
    var    i: integer;
        tempSum: real; {накопление суммы площадей треугольников}
        tempStep, tempNext: TPointer;
        difX, difY, difStepX, difStepY, difNextX, difNextY: integer;
        len, lenStep, lenNext: real;
        tempP: real; {полупериметр каждого получевшегося реугольника}
    begin
    {для разностей и длин::
     Step - точка и текущая вершина;
     Next - точка и следующая вершина;
     [ничего] - текущая и следующая вершины}
    tempSum:=0; tempP:=0; tempStep:=start; tempNext:=start^.next;
    difStepX:=(x-tempStep^.x)*(x-tempStep^.x);
    difStepY:=(y-tempStep^.y)*(y-tempStep^.y);
    lenStep:=SQRT(difStepX+difStepY);
    for i:=1 to num do
        begin
        {расстояние от текущей вершины до следующей}
        difX:=(tempNext^.x-tempStep^.x)*(tempNext^.x-tempStep^.x);
        difY:=(tempNext^.y-tempStep^.y)*(tempNext^.y-tempStep^.y);
        len:=SQRT(difX+difY);
        {расстояние от точки до следующей вершины}
        difNextX:=(tempNext^.x-x)*(tempNext^.x-x);
        difNextY:=(tempNext^.y-y)*(tempNext^.y-y);
        lenNext:=SQRT(difNextX+difNextY);
        {полупериметр}
        tempP:=(len+lenStep+lenNext)*0.5;
        tempSum:=tempSum+SQRT(tempP*(tempP-len)*(tempP-lenStep)*(tempP-lenNext));
        {переносим длины текущей стороны
         сдвигаем указатели на  одну вершину вперед}
        lenStep:=lenNext; tempStep:=tempNext; tempNext:=tempNext^.next;
        end;
    {сумма площадей равно площади многоугольника?}
    PointInPolyhedron:=(Square(start,num)=tempSum);
    end;

В упор не могу найти еще ошибки (помогите, пожалуйста).

Ну и сама программа, в которой все это тестируется, выглядит так:
Код

uses Module;

var    input: text;
    i: integer;
    x, y: integer;

begin
{создание списка из вершин­}
assign(input, 'C:\in.txt'); reset(input);
MReadFirst(input,num,start,step);
for i:=1 to (num-1) do MRead(input,step);

{закольцовывание списка}
finish:=step; finish^.next:=start;

writeln(Perimeter(start,num):2:2);
writeln(Square(start,num):2:2);
readln(x,y); writeln(PointInPolyhedron(start,num,x,y));
readln;
end.


Это сообщение отредактировал(а) KasMP - 20.5.2008, 07:59
PM MAIL   Вверх
KasMP
Дата 20.5.2008, 14:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
 smile  smile  smile 
Я вместо массива организовала динамический список smile !
PM MAIL   Вверх
skyboy
Дата 20.5.2008, 16:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


неОпытный
****


Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 5
Всего: 260
я так понял, у тебя сравниваются площади "строго равно". все же у тебя дробный тип данных.
воспользуйся сравнением "отлиается на некую погрешность".
Цитата(KasMP @  20.5.2008,  06:58 Найти цитируемый пост)
 Но функция по прежнему всегда выдает false.

ну, так отладь функции в отдельности.
корми тестовые данные, смотри дебаггером текущие значения переменных. сравнивай с ожидаемым.
когда функции в отдельности будут отлажены и проверены по мере сил, приходи к тестированию программы в целом.
а то даже с помощью целого форума искать ошибку в непростом коде - вещь небыстрая, малоинтересная и низкоинформативная smile
PM MAIL   Вверх
KasMP
Дата 20.5.2008, 19:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
skyboy, smile !
(очень рада тебя видеть!!!)

Цитата(skyboy @  20.5.2008,  16:43 Найти цитируемый пост)
я так понял, у тебя сравниваются площади "строго равно". все же у тебя дробный тип данных.
 smile 
Цитата(skyboy @  20.5.2008,  16:43 Найти цитируемый пост)
воспользуйся сравнением "отлиается на некую погрешность"
 smile  smile 
Т.е., другими словами, взять модуль разности суммы площадей треугольников и площади многоугольника, а затем сравнить этот модуль с какой-то положительной величиной?
Цитата(skyboy @  20.5.2008,  16:43 Найти цитируемый пост)
ну, так отладь функции в отдельности.
корми тестовые данные, смотри дебаггером текущие значения переменных. сравнивай с ожидаемым.
когда функции в отдельности будут отлажены и проверены по мере сил, приходи к тестированию программы в целом.

Я так и делаю smile . Видимо, сказывается недостаток опыта smile .
PM MAIL   Вверх
Fortop
Дата 21.5.2008, 01:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
Цитата(KasMP @  20.5.2008,  19:19 Найти цитируемый пост)
Т.е., другими словами, взять модуль разности суммы площадей треугольников и площади многоугольника, а затем сравнить этот модуль с какой-то положительной величиной?

Если в Delphi нет специальной функции, то алгоритм описан правильно smile
главное чтобы эта положительная величина была достаточно мала smile



--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
KasMP
Дата 21.5.2008, 10:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(Fortop @  21.5.2008,  01:25 Найти цитируемый пост)
главное чтобы эта положительная величина была достаточно мала

Подумаем, сколько это должно быть...

Только проблема в том, что функция проверки принадлежности точки многоугольнику выдает false даже тогда, когда результаты всех вычислений, всех извлечений корней целочисленны smile . Буду дальше искать и сравнивать... smile
PM MAIL   Вверх
Fortop
Дата 21.5.2008, 22:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
KasMP, 
А что тут искать?

бери треугольник со сторонами 3, 4, 5

переведи на листике его в векторы и точку где-нибудь внутри.

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


--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
KasMP
Дата 21.5.2008, 22:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
О smile !
Сегодня запустила тот же самый код на другом компе - функция работала идеально smile . Сейчас запустила у себя - тоже идеально smile .

Как такое может быть smile  smile ?
(может память надо чаще очищать smile  smile ?)
PM MAIL   Вверх
KasMP
Дата 22.5.2008, 09:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Сделала все кроме пересечения двух многоугольников (вторым "многоугольником" может быть точка). Про пересечение буду читать вот это.
Сдавать в классе мы уж не успеваем, поэтому буду писать на e-mail. Я попробовала прокомментировать модуль и саму программу так, чтобы преподаватель понял, откуда что взялось.

Не могли бы вы оценить то, насколько понятно получилось?
Помогите, пожалуйста, своей оценкой. Я нисколько не хочу, чтобы преподаватель увяз в дебрях переменных, связей между ними и т.п.. Хочется, чтобы ему было не очень сложно и чтобы он не мучился слишком сильно...
(видимо, придется посылать два варианта: с комментариями и без - уж слишком много их получилось)
PM MAIL   Вверх
THandle
  Дата 22.5.2008, 09:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372
KasMP, покажи что у тебя получилось, почитаю smile 
PM   Вверх
KasMP
Дата 22.5.2008, 09:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Сейчас smile .

Добавлено через 2 минуты и 44 секунды
Эм...
Если открыть *.pas в блокноте, выбрать шрифт "Terminal", скопировать и вставить сюда, то вместо кириллицы получается абракадабра. Если выбирать не "Terminal", то получается абракадабра и в блокноте, и здесь... smile

Добавлено через 3 минуты и 58 секунд
Как перенести кириллицу из *.pas (т.е. из-под MSDOS) сюда (т.е. в Windows)?
PM MAIL   Вверх
THandle
Дата 22.5.2008, 09:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372
KasMP, прикрепи сам файл smile 
PM   Вверх
KasMP
Дата 22.5.2008, 09:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Так не все будут качать... Кто-то по ссылке до статьи дойти не может, а тут тем более...



Присоединённый файл ( Кол-во скачиваний: 4 )
Присоединённый файл  Polyhedron.rar 8,66 Kb
PM MAIL   Вверх
KasMP
Дата 22.5.2008, 09:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Там 5 файлов: модуль с комментариями и без, программа с комментариями и без, формула для площади многоугольника.

Добавлено через 7 минут и 44 секунды
Я вспомнила, что забыла очистить память!!!!!!
Добавлю потом... Считайте, что память очищена smile .

Добавлено через 10 минут и 54 секунды
Да, кстати, вам потребуется файл входных данных. Можете взять этот:
Цитата

4 -6 0 -6 2 -4 3 -4 -2
3 0 0 0 -3 -2 0
5 2 1 2 5 4 5 4 1 3 3
6 2 -3 5 -3 5 -4 7 -4 5 -5 3 -5


Присоединённый файл ( Кол-во скачиваний: 3 )
Присоединённый файл  Polyhedron.rar 8,66 Kb
PM MAIL   Вверх
KasMP
Дата 22.5.2008, 10:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Если кому-то интересно, то с этими входными данными
Цитата
4 -6 0 -6 2 -4 3 -4 -2
3 0 0 0 -3 -2 0
5 2 1 2 5 4 5 4 1 3 3
6 2 -3 5 -3 5 -4 7 -4 5 -5 3 -5
получаются вот такие многоугольники (~120Кб).
PM MAIL   Вверх
THandle
Дата 22.5.2008, 10:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Хранитель Клуба
Group Icon
Награды: 1



Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372
KasMP, ну в общем все чем мог помочь написал в ПМ, для форума это особой ценности не представляет smile 
PM   Вверх
KasMP
Дата 22.5.2008, 11:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(THandle @  22.5.2008,  10:56 Найти цитируемый пост)
KasMP, ну в общем все чем мог помочь написал в ПМ

 smile  smile 
PM MAIL   Вверх
KasMP
Дата 22.5.2008, 11:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Так, пересечение smile ...
Цитата(Скворцов @  Обзор алгоритмов построения оверлеев многоугольников)
user posted image

Посидев над этой табличкой, я выбрала алгоритм О'Рурка для выпуклых многоугольников (а случай с многоугольником и точкой рассмотрю отдельно, на это много ума не надо...).
Цитата(Скворцов @  Обзор алгоритмов построения оверлеев многоугольников)
user posted image

Честно говоря smile, я очень плохо представляю, как можно это реализовать smile...
PM MAIL   Вверх
KasMP
Дата 23.5.2008, 18:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Люди, ну помогите пожалуйста разобраться с алгоритмом О'Рурка!
(моя тема чем-то хуже остальных?)
PM MAIL   Вверх
Fortop
Дата 23.5.2008, 20:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

Репутация: 1
Всего: 42
KasMP, судя по всему он очень похож на то, что я тебе предлагал в самом начале.

Перебирать все ребра и проверять пересекаются ли они между собой.

или посмотри эту ссылку
http://progs-maker.narod.ru/algor.html


--------------------
Мир это Я.
Живее всех живых.
PM MAIL   Вверх
volvo877
Дата 23.5.2008, 20:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 34
Всего: 116
Цитата(KasMP @  23.5.2008,  18:09 Найти цитируемый пост)
ну помогите пожалуйста разобраться с алгоритмом О'Рурка!
Наверное, лучше всего обратиться к первоисточнику - книге О'Рурка "Вычислительная геометрия на С". Вот тут лежат исходники из этой книги: http://maven.smith.edu/~orourke/books/ftp.html (тебе нужен Int Conv Poly)
PM MAIL   Вверх
Страницы: (3) [Все] 1 2 3 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1510 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.