 |
|
Модераторы: Poseidon |
 
|
|
[Pascal] Динамические массивы, модуль "Многоугольник" 
| KasMP |
|
|||
 Опытный  Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
С первым пунктом (вычисление периметра) все очевидно: идем по списку (состоящему из записей с тремя полями: x, y, next), накапливаем значение периметра (используя формулу расстояния между двумя точками с известными координатами: d^2=(x1-x2)^2+(y1-y2)^2); упростить процесс у меня не получилось (там же сумма корней получается, ничего с ней не сделаешь…). По части второго пункта (вычисление площади) есть тупая мысль просто взять лежащую внутри многоугольника точку, соединить ее со всеми вершинами, накапливать значение площади (складывая площади получившихся треугольников). Мне эта тупая мысль не нравится, но придумать что-то более элегантное пока не удалось. Третий пункт, проверка на выпуклось. Можно, конечно, исходить из геометрического определения выпуклости и проверять, лежит ли многоугольник по одну сторону от каждой из линий, соединяющих соседние вершины. Но интуиция мне подсказывает, что это слишком долго, нерационально и имеет мало общего с программированием  .Четвертый и пятый пункт меня пугают   .Помогите, пожалуйста  . Не бросайте студентку на произвол судьбы  !! |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
1) да.
2) не сработает, ибо ошибочно. Использовать разбиение на треугольники. 3) проверка внешних углов при каждой вершине. 4) ликвидация "впуклых" вершин по одной. 5) непонятно, о чем речь -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
вычислять площадь можно по такой формуле (то ли это формула Грина, то ли из неё выводится):
s=sum[i=1..N]( (x[i+1]-x[i])*(y[i+1]+y[i])/2 ) (ну ещё модуль взять) -------------------- qqq |
|||
|
||||
| KasMP |
|
||||||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Скажем, есть у нас три пары координат: вершины А1, А2, А3. А3 / А2 \ А1 Как посчитать угол - понятно (через скалярное произведение векторов). А вот как определить, будет посчитанный угол внешним или внутренним? Ведь возможны обе ситуации: 
(а мы пока этому комп не научили).
 .
Т.е. если смотреть со стороны периметра и площади, то нам больше всего подходит циклический способ организации динамического массива (проще говоря, мы должны указатель последней записи направить на первую). Да ?!(большое спасибо за хорошую, очень удобную формулу  !) |
||||||||
|
|||||||||
| maxim1000 |
|
||||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
да, просто забыл уточнить по смыслу там просто идёт суммирование по отрезкам, ну а т.к. последний отрезок соединяет последнюю и первую вершины, то и получается циклический доступ
рассматривая отдельно взятый угол, определить внешний он или внутренний не получится нужно выбрать направление обхода вершин (вполне естественно взять то, в котором задан многоугольник) и для каждого угла выяснить, вправо он поворачивает или влево если везду происходит поворот в одну и ту же сторону - многоугольник выпуклый, иначе - нет Добавлено через 1 минуту и 53 секунды ну а вообще, в будущем я бы советовал создавать по одной теме на каждый вопрос, тогда и заголовок можно точнее написать, что увеичит вероятность захода в тему человека, которому это интересно ну а кроме того, по этим вопросам можно поискать, что уже есть на форуме если мне не изменяет память, то определение площади и выпуклости уже где-то проскакивало -------------------- qqq |
||||
|
|||||
| KasMP |
|
||||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Определить это через скалярное произведение не получается: его знак говорит о том, что угол острый/прямой/тупой, а направление никак не задействовано. Если считать угол между векторами, то тоже не получается: arccos(x) - мы можем повернуть на x в любу сторону. Если считать изменение координат (например, абсцисса увеличилась и ордината уменьшилась, абсцисса и ордината увеличились, т.п.), то придется сначала искать крайние точки (нижнюю, левую, верхнюю, правую), потому что при переходе через эти точки изменение координат меняют значение: находимся между крайней левой и крайней верхней точками, увеличение абсциссы и ординаты - поворот вправо; находимся между крайней правой и крайней левой точками, увеличение абсциссы и ординаты - поворот влево. Как это определить? 
Учту на будущее .
Уже пробовала . Попробую еще . |
||||||
|
|||||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
для этого можно использовать векторное произведение точнее - определитель, т.к. векторное произведение определяется в 3d ax*by-ay*bx будет иметь разный знак в зависимости от того, в какую сторону направлен угол между a и b -------------------- qqq |
|||
|
||||
| KasMP |
|
|||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Точно! Да и я сама вспомнила про векторное произведение, хотела открыть тетрадку и проверить, а вместо этого пошла на кухню делать ужин и так и забыла .Спасибо еще раз  . |
|||
|
||||
| KasMP |
|
|||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Итак, мы уточнили .Пересечение двух выпуклых многоугольников. Пересечение - часть, принадлежащая обоим многоугольникам, вершины которых задаются с помощью двух координат. Например, 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))- первый многоугольник. Проверка принадлежности точки многоугольнику (возможно, невыпуклому). Тут все понятно .(в смысле, задание понятно... а как делать - нефига непонятно!!!) Это сообщение отредактировал(а) KasMP - 18.5.2008, 16:19 |
|||
|
||||
| KasMP |
|
|||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Люди, ну помогите, пожалуйста, с принадлежностью точки многоугольнику!
Если с определением выпуклости я как-то справлюсь (примерно понятно, что и как делать), то с принадлежностью вообще все очень туго!!!  |
|||
|
||||
| Fortop |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 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 -------------------- Мир это Я. Живее всех живых. |
|||
|
||||
| KasMP |
|
||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Не знаю, сейчас подумаю... Добавлено через 47 секунд
О! Там, похоже, что-то стоящее  . Посмотрю попозже, спасибо за хорошую ссылку  .Добавлено через 2 минуты и 43 секунды Кстати, с пересечением тоже дела не очень...  Пожалуйста, не бросайте на растерзание судьбы  беззащитную студентку . |
||||
|
|||||
| KasMP |
|
|||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Гм, и неужели нельзя изобрести такой треугольник и такую непринадлежащую ему точку, что указанная сумма площадей будет равно площади треугольника? Имхо если постараться, то может получиться !(а с многоугольником точно должно получиться изобрести!) Это сообщение отредактировал(а) KasMP - 18.5.2008, 16:56 |
|||
|
||||
| Fortop |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 2200 Регистрация: 13.11.2007 Где: Донецк Репутация: 1 Всего: 42 |
KasMP,
С пересечением тоже можно поискать ссылки Не думая, алгоритмически я бы сделал так. Взял бы каждую сторону многоугольников и проверил бы на пересечение с каждой стороной другого. Если есть, то найти точки пересечения и определив направление обхода, бежал бы последовательно по узлам. Например. Если первое пересечение находится на стороне А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. Хотя надо еще проверять выпуклость и впуклость. Плюс здесь же будет проверка вырожденого случая. Если один многоугольник целиком внутри другого. А вообще пару запросов в Гугль, и думаю, там будут более оптимальные варианты, чем предложенный мной Добавлено @ 17:00
нет. Смотри, так как ты соединяешся с каждой вершиной. То площадь многоугольника ты захватишь в любом случае. Но если точка лежит вне, то ты захватишь еще и лишнего Добавлено через 4 минуты и 4 секунды KasMP, если что-то не можешь понять - нарисуй на бумаге Так бывает гораздо проще.А треугольник или многоугольник - разницы большой в этом случае нет. Это сообщение отредактировал(а) Fortop - 18.5.2008, 17:01 -------------------- Мир это Я. Живее всех живых. |
|||
|
||||
| KasMP |
|
||||
|
Опытный Профиль Группа: Завсегдатай Сообщений: 586 Регистрация: 8.8.2006 Репутация: 1 Всего: 30 |
Да, но ведь нормальный программист должен хотя бы раз додуматься до всего этого сам. (или хотя бы поразмышлять на эту тему, чтобы понять все нюансы и всю красоту оптимального варианта, понять свои ошибки и сделать вывод на будущее)
 .(я уже нарисовала ) |
||||
|
|||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0909 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |