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

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

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

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

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

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

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

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

4
2736 / 1816 / 200
Регистрация: 05.06.2011
Сообщений: 5,253
10.08.2013, 16:07 2
Ну, либо квадраты пересекаются и расстояние равно нулю, либо минимум расстояния достигается в вершинах.
Как проверить, что квадраты пересекаются... Такое чувство, что при этом вершина одного лежит внутри другого. Доказать пока не получается. Просто интуиция.
0
4527 / 3521 / 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
2736 / 1816 / 200
Регистрация: 05.06.2011
Сообщений: 5,253
11.08.2013, 04:37 5
Таки про непересекающиеся я тоже чушь написал. Надо проверить не 16 расстояний между вершинами, а честно искать расстояние от вершины одного квадрата до каждой стороны другого.
Касательно проверки пересечения. Алгоритм Моцкина-Бургера, конечно, страшен, но у нас задача несколько попроще. Искомая разделяющая прямая задаётся тремя параметрами; можем параллельно сдвинуть, чтобы она прошла через одну из вершин, скажем, первого квадрата. Останется два параметра. Получается, в общем, четыре задачи на пересечение семи полуплоскостей. Муторно, конечно, но решаемо, имхо.
1
11.08.2013, 04:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.08.2013, 04:37
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru