Форум программистов, компьютерный форум, киберфорум
Математика
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 16.01.2013
Сообщений: 14

Задача на нахождение наикратчайшего расстояния между квадратами

10.08.2013, 13:45. Показов 1460. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
На входе 4 точки первого квадрата и 4 от второго. Задача: найти наикратчайшего расстояния между квадратами. Второй день не могу рещить это, помогите плз.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
10.08.2013, 13:45
Ответы с готовыми решениями:

Задача на нахождение угла между двумя плоскостями
Точка М(-5; 16; 12), через которую проведены две плоскости: одна из них содержит ось ОХ, другая ОY. Вычислить угол между плоскостями. не...

Задача на нахождение расстояния между автомобилями, движущимися с разной скоростью
скорость первого автомобиля v1км\ч,второго v2 км/ч. определить расстояние между ними через t часов. если автомобили удаляются друг от...

Нахождение расстояния между точками
Четыре точки заданы своими координатами X(x1, x2), Y(y1, y2), Z(z1, z2), P(p1, p2). Выяснить, какие из них находятся на максимальном...

4
2800 / 1846 / 202
Регистрация: 05.06.2011
Сообщений: 5,360
10.08.2013, 16:07
Ну, либо квадраты пересекаются и расстояние равно нулю, либо минимум расстояния достигается в вершинах.
Как проверить, что квадраты пересекаются... Такое чувство, что при этом вершина одного лежит внутри другого. Доказать пока не получается. Просто интуиция.
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
10.08.2013, 18:08
Цитата Сообщение от iifat Посмотреть сообщение
Такое чувство, что при этом вершина одного лежит внутри другого.
Необязательно: взять квадрат и повернуть его вокруг центра на τ/8, где т = 2π.

Добавлено через 5 минут
В принципе, вопрос о непустоте пересечения выпуклых многоугольников сводится к совместности системы линейных неравенств. Но это как-то тяжко. Алгоритм Моцкина—Бургера...
2
0 / 0 / 0
Регистрация: 16.01.2013
Сообщений: 14
10.08.2013, 18:55  [ТС]
Для решения задачи написал код нижу, однако, закралась ошибка в формулы, помогите найти.


Кликните здесь для просмотра всего текста
C# Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 static float GetClosestDistanceToHero(GameObject obj)
        {
            if (HERO.hero == null) return float.MaxValue;
            return GetClosestDistBetwin_SQUARE_rectangles(HERO.hero, obj);
        }
        static float GetClosestDistBetwin_SQUARE_rectangles(GameObject o1, GameObject o2)
        {
            //это наборы точек двух квадратов
            var points_1 = GetBarrierVertexes(o1);
            var points_2 = GetBarrierVertexes(o2);
 
            float closestPoints = float.MaxValue;
            if (points_1 == null | points_2 == null) return closestPoints;
 
 
            float CLOSEST = float.MaxValue;
 
            for (int i = 0; i < points_1.Count; ++i)
            {
                Vector2 segmentONE_1, segmentONE_2;
                //точки первого отрезка
                segmentONE_1 = points_1[i];
                int one_2 = (i == points_1.Count - 1) ? 0 : i + 1;
                segmentONE_2 = points_1[one_2];
 
                for (int i2 = 0; i2 < points_2.Count; ++i2)
                {
                    Vector2 segmentTWO_1, segmentTWO_2;
 
                    //точки второго отрезка
                    segmentTWO_1 = points_2[i2];
                    int two_2 = (i2 == points_2.Count - 1) ? 0 : i2 + 1;
                    segmentTWO_2 = points_2[two_2];
 
 
                    //найти кратчайшее расстояние между отрезками
                    float d = GetClosestDistBetwinTwo_SEGMENTS(segmentONE_1, segmentONE_2, segmentTWO_1, segmentTWO_2);
                    if (d < CLOSEST) CLOSEST = d;
                }
            }
 
            return CLOSEST;
        }
        static float GetClosestDistBetwinTwo_SEGMENTS(Vector2 segmentONE_1, Vector2 segmentONE_2, Vector2 segmentTWO_1, Vector2 segmentTWO_2)
        {
            float va1 = GetClosestDistBetwin_SEGMENT_AND_POINT(segmentONE_1, segmentONE_2, segmentTWO_1);
            float va2 = GetClosestDistBetwin_SEGMENT_AND_POINT(segmentONE_1, segmentONE_2, segmentTWO_2);
 
            if (va1 <= va2) return va1; else return va2;
        }
        static float GetClosestDistBetwin_SEGMENT_AND_POINT(Vector2 segmentONE_1, Vector2 segmentONE_2, Vector2 point)
        {
            float distance = float.MaxValue;
 
            double A = GetDistBetwin_POINTS(segmentONE_1, point);
            double B = GetDistBetwin_POINTS(segmentONE_2, point);
            double C = GetDistBetwin_POINTS(segmentONE_1, segmentONE_2);
 
            double skobki = Math.Pow(((B * B - A * A + C * C) / (2 * C)), 2);
 
            double h = Math.Sqrt(B * B - skobki);
            return (float)h;
        }
        static float GetDistBetwin_POINTS(Vector2 p1, Vector2 p2)
        {
            double pow1 = Math.Pow((double)(p1.X - p2.X), 2);
            double pow2 = Math.Pow((double)(p1.Y - p2.Y), 2);
            float d = (float)Math.Sqrt(pow1 + pow2);
            return d;
        }


 Комментарий модератора 
Здесь нужны сами формулы. Код программы и поиск ошибок в нём - для других веток форума.
0
2800 / 1846 / 202
Регистрация: 05.06.2011
Сообщений: 5,360
11.08.2013, 04:37
Таки про непересекающиеся я тоже чушь написал. Надо проверить не 16 расстояний между вершинами, а честно искать расстояние от вершины одного квадрата до каждой стороны другого.
Касательно проверки пересечения. Алгоритм Моцкина-Бургера, конечно, страшен, но у нас задача несколько попроще. Искомая разделяющая прямая задаётся тремя параметрами; можем параллельно сдвинуть, чтобы она прошла через одну из вершин, скажем, первого квадрата. Останется два параметра. Получается, в общем, четыре задачи на пересечение семи полуплоскостей. Муторно, конечно, но решаемо, имхо.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
11.08.2013, 04:37
Помогаю со студенческими работами здесь

Нахождение расстояния между точками
Помогите пожалуйста решить задание! Даны две точки в n-мерном пространстве X=(х1, х2, ..., хn), Y=(y1, y2, ...,yn). Написать программу...

Нахождение расстояния между точками
Вводится количество точек, потом их координаты. Программа должна вывести общее расстояние между ними. Помогите с решением.

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

Нахождение наибольшего расстояния между точками
Здравствуйте.помогите пожалуйста.у меня такая задача. на форме должны размещаться Image, StringGrid1, StringGrid2, Edit1,...

Нахождение расстояния между двумя точками
Коллеги помогите пожалуйста решить данную задачу по паскалю. Или просто объясните алгоритм действия в данной ситуации, т.к. логически...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
std::vector в C++: от основ к оптимизации производительности
NullReferenced 05.04.2025
Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .
Реляционная модель и правила Кодда: фундамент современных баз данных
Codd 05.04.2025
Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .
Асинхронные операции в Django с Celery
py-thonny 05.04.2025
Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .
Использование кэшей CPU: Максимальная производительность в Go
golander 05.04.2025
Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .
Создаем Telegram бот на TypeScript с grammY
run.dev 05.04.2025
Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .
Паттерны распределённых транзакций в Event-Driven микросервисах
ArchitectMsa 05.04.2025
Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .
Работа с объемным DOM в javascript
Htext 04.04.2025
Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .
Оптимизация производительности Node.js с помощью кластеризации
run.dev 04.04.2025
Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .
Управление зависимостями в Python с Poetry
py-thonny 04.04.2025
Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .
Мониторинг с Prometheus в PHP
Jason-Webb 04.04.2025
Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер