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

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

10.08.2013, 13:45. Показов 1444. Ответов 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
2786 / 1833 / 201
Регистрация: 05.06.2011
Сообщений: 5,334
10.08.2013, 16:07 2
Ну, либо квадраты пересекаются и расстояние равно нулю, либо минимум расстояния достигается в вершинах.
Как проверить, что квадраты пересекаются... Такое чувство, что при этом вершина одного лежит внутри другого. Доказать пока не получается. Просто интуиция.
0
4528 / 3522 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
10.08.2013, 18:08 3
Цитата Сообщение от iifat Посмотреть сообщение
Такое чувство, что при этом вершина одного лежит внутри другого.
Необязательно: взять квадрат и повернуть его вокруг центра на τ/8, где т = 2π.

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


Кликните здесь для просмотра всего текста
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
2786 / 1833 / 201
Регистрация: 05.06.2011
Сообщений: 5,334
11.08.2013, 04:37 5
Таки про непересекающиеся я тоже чушь написал. Надо проверить не 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
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Сайт компании Red-Star-Soft переехал на новый хостинг!
Etyuhibosecyu 06.03.2025
Как и советовал Rius, я покинул хостинг от "Ru-Center" и перенес сайт red-star-soft. com на хостинг с более позитивными отзывами (спойлер: найти его было далеко не просто) (чтобы прочитать текст,. . .
Альтернативная сериализация в Java: сравнение Kryo, Protobuf и Avro
Jamaican 06.03.2025
Сериализация — один из краеугольных процессов в Java-разработке. Превращение объектов в поток байтов для хранения или передачи по сети с последующим восстановлением звучит просто, но реализация этого. . .
Битва Java-кешей: Сравниваем Ehcache, Caffeine и Hazelcast
Jamaican 06.03.2025
Производительность — вечный Святой Грааль для Java-разработчиков. Мы оптимизируем алгоритмы, настраиваем JVM, распараллеливаем процессы, но неизменно приходим к одному и тому же средству ускорения —. . .
Параметры подтверждения сообщения Kafka
Jamaican 06.03.2025
Среди распределённых систем и высоконагруженных приложений Apache Kafka занимает особое место. Эта платформа потоковой обработки данных давно стала стандартом де-факто для организаций, которым. . .
Оптимизация времени запуска Spring Boot
Jamaican 06.03.2025
Вы когда-нибудь сидели, барабаня пальцами по столу, пока ваше Spring Boot приложение медленно поднимается? Этот момент, когда вы успеваете сходить за кофе, пообщаться с коллегами и вернуться, а. . .
Деплой Kubernetes в Java: масштабирование Spring Boot приложений
Jamaican 06.03.2025
Когда ваше Spring Boot приложение внезапно получает всплеск трафика или требует плавного обновления без простоя — традиционные методы деплоя часто пасуют. Именно здесь на сцену выходит Kubernetes —. . .
Бессерверные приложения Java: сравнение AWS Lambda и Azure Functions
Jamaican 06.03.2025
Что такое "бессерверные приложения" и почему они так привлекательны? Вопреки названию, серверы никуда не исчезли — просто теперь управление инфраструктурой перекладывается на плечи облачного. . .
Безопасность микросервисов с OAuth2 и OpenID Connect
Jamaican 06.03.2025
С ростом популярности микросервисов растут и проблемы, связанные с их безопасностью. В отличие от монолитных приложений, где безопасность можно было обеспечить централизованно, микросервисная. . .
Структурное логирование в Spring Boot
Jamaican 06.03.2025
Представьте, что вы управляете сотней микросервисов в продакшн-среде. Внезапно один из сервисов начинает давать сбои, и вам нужно срочно выяснить причину. Вы открываете логи и видите бесконечные. . .
Предотвращение XSS, CSRF и SQL-инъекций в JavaScript
bytestream 05.03.2025
В эпоху цифровизации безопасность веб-приложений становится не просто рекомендацией, а жизненной необходимостью. Если вы разрабатываете приложения на JavaScript, вам наверняка знакома эта. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru