VPF::[C++] Точки и минимальная окружность

UnlaR

Дата 22.11.2010, 19:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 22.11.2010

Репутация: нет
Всего: нет

Само задание: Для множества точек на плоскости найти круг минимального радиуса, содержащий все эти точки. Язык C++.
Главное сделать с использованием структур или классов.
С геометрией у меня туго еще со школы smile

Код


#include <iostream>
#include <stdlib.h> // Отсюда берём rand()
#include <time.h> // Здесь находится time()

using namespace std;
void horisontal();  //функция горизонтальной линии
void line(int x);   //функция вывода данных в виде таблицы
void vivod();       //Общая функция вывода
void sort(int x);
void sort_all();

struct circle {            //объявление структуры данных
    int coord[2][10];      //объявление массива точек X и У
    int centrX;
    int centrY;
    }cicl;

circle* pcenter = &cicl;    //инициализируем указатель

int main()
{
    srand((unsigned)time(NULL));    //ради rand()
    for (int i = 0 ; i!=2; i++)
        for (int j = 0 ; j!=10; j++)
        {
            (*pcenter).coord[i][j]=rand() % 40 - 20;
        };
   vivod();        //вывод полученных данных
/*--- Сортировка методом пузыря----*/
sort_all();


    return 0;
}

void sort_all()
{
sort (0);
vivod();        //вывод полученных данных
sort (1);
vivod();        //вывод полученных данных
}

void sort(int x)
{
    bool t = true;
    while (t==true)
    {
        t=false;
        for (int i = 0 ; i<9 ; i++)
        {
            int temp=0;
            if ((*pcenter).coord[x][i]>(*pcenter).coord[x][i+1])
            {
                temp = (*pcenter).coord[0][i+1];
                (*pcenter).coord[0][i+1] = (*pcenter).coord[0][i];
                (*pcenter).coord[0][i] = temp;
                temp = (*pcenter).coord[1][i+1];
                (*pcenter).coord[1][i+1] = (*pcenter).coord[1][i];
                (*pcenter).coord[1][i] = temp;
                t = true;
            }
        }
    }
}

//---------вывод полученных данных------
void vivod()
{
    horisontal();
    line(0);
    horisontal();
    line(1);
    horisontal();
    cout << "\n";
}
void horisontal()
{
    for (int j = 0 ; j!=52; j++) cout << "_"; cout << "\n";
};
void line(int x)
{
    cout <<  (x == 0 ? "x= " : "y= ");
    for (int j = 0 ; j!=10; j++) cout << (*pcenter).coord[x][j] << " | "; cout << "\n";
}

Очень прошу оказать содействие. достаточно правильного пинка под зад.
Как думал действовать дальше:
1. Найти максимально удаленные точки.
2. Далее найти точку при которой угол треугольника будет максимально тупым.
3. Эта точка будет центром минимальной окружности. Радиус будет длинной максимального катета.

Или есть другое и более правильное решение?

Это сообщение отредактировал(а) UnlaR - 22.11.2010, 19:54

sQu1rr

Дата 22.11.2010, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

В разделе прикреплены интересные ссылки... "Что бы не изобретать велосипед" или чтото в этом роде
http://algolist.manual.ru/maths/geom/misc/mincircle.php

UnlaR

Дата 23.11.2010, 11:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 22.11.2010

Репутация: нет
Всего: нет

Не очень понял...
1. Перетряхивание массива можно изобразить 1 проходом скажем пузырьковой сортировки.
2. Проверку на принадлежность точки можно изобразить

Код


int pow(int val)
    {
    int r = val;
   r = r*val;
   return r;
    }


bool PointInCircle(int x, int y)
{
    return pow(x-(*pcenter).centrX)+pow(y-(*pcenter).centrY) <= pow ((*pcenter).Rad);
}

3. Расширение окружности?
Программа выглядит так:
)строим окружность срез две эти точки(находим центр между этими двумя точками и этот отрезок является диаметром)
) проверяем принадлежность следующей точки к окружности
) если не принадлежит, то строим окружность по треугольнику Вики
)после одного прохода по массиву перетряхиваем массив и проверяем снова.

Если не прав - поправьте меня пожалуйста.
Решение http://algolist.manual.ru/maths/geom/misc/mincircle.php
Я не понимаю пункта 2 в программе MINDISC1
Как его сделать?

Это сообщение отредактировал(а) UnlaR - 23.11.2010, 14:28

UnlaR

Дата 26.11.2010, 10:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 22.11.2010

Репутация: нет
Всего: нет

Как именно "расширить окружность". Я не могу найти формулы, теоремы, выкладки, правила...

sQu1rr

Дата 27.11.2010, 00:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата(UnlaR @ 22.11.2010, 19:26

)

1. Найти максимально удаленные точки.
2. Далее найти точку при которой угол треугольника будет максимально тупым.
3. Эта точка будет центром минимальной окружности. Радиус будет длинной максимального катета.

1. Дело в том что что поиск максимально удаленных точек n! операций по вычислению их расстояния :( А это не есть гуд. Оптимизировать это глупо, решение на той ссылке проще.
2. Если найдены 2 максимально отдаленные точки, то радиус окружности ( минимальной ), это расстояние между ними поделенное на 2, ведь эти 2 точки и есть решение: Круг меньше построить нельзя, круг больше строить нет смысла ( все точки и так в него входят )
Это легко реализовать но дорого

И да: у тупоугольного треугольника нету катетов smile

http://www.personal.kent.edu/~rmuhamma/Com...r/centercli.htm
Вот тут можно почитать про множество алгоритмов на эту тему, включая и тот, что выполняется O(n)

Это сообщение отредактировал(а) sQu1rr - 27.11.2010, 01:10

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »