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

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

10.08.2013, 13:45. Показов 1458. Ответов 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
2799 / 1845 / 202
Регистрация: 05.06.2011
Сообщений: 5,357
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
2799 / 1845 / 202
Регистрация: 05.06.2011
Сообщений: 5,357
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
Ответ Создать тему
Новые блоги и статьи
Контейнеризация React приложений с Docker
Reangularity 03.04.2025
Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .
Свой попап в SwiftUI
mobDevWorks 03.04.2025
SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .
Антипаттерны микросервисной архитектуры
ArchitectMsa 03.04.2025
Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .
std::mutex в C++: Советы и примеры использования
bytestream 03.04.2025
std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
Метод с двумя буферами (или double buffering) или ping-pong buffering
Hrethgir 02.04.2025
Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .
На любовном киберфронте
Alexander-7 01.04.2025
Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
Как работает Node.js изнутри
run.dev 29.03.2025
Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
Моки в Python: Mock Object Library
py-thonny 29.03.2025
Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
JavaScript: Управление памятью и улучшение производительности
run.dev 29.03.2025
В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер