Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Фигура на плоскости к площади всей плоскости 
V
    Опции темы
OverBug
Дата 26.12.2006, 17:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 84
Регистрация: 13.4.2006
Где: г.Пенза, Пензенск ой обл.

Репутация: нет
Всего: 1
Здраствуйте! Нужна помощь в решении следующей задачи... требуется выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках. Как можно ее решить? Использовать двумерный массив или решить уравнение подставляя в него нужные значения....
PM MAIL ICQ   Вверх
SoWa
Дата 26.12.2006, 21:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Ни то и ни другое. Задача на графы. Обход графа за минимальную/максимиальную стоимость. За стоимость можешь брать расстояние между точками.

А вообще приходит такая мысль. Все множество точек обводишь квадратом. Ищешь точки в квадрате самые близкие к вершинам. Итого 3 варианта треугольников. Ищем нужный.


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
OverBug
Дата 27.12.2006, 09:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 84
Регистрация: 13.4.2006
Где: г.Пенза, Пензенск ой обл.

Репутация: нет
Всего: 1
а как определить что какая-то конкретная точка находится в нашем треугольнике, т.е. находится по ту или другую сторону отрезка с координатами (х1,у1,х2,у2)?

а про графы я не понял.... smile  как с их помощью можно решить данную задачу? и какой это будет граф?
PM MAIL ICQ   Вверх
SoWa
Дата 27.12.2006, 15:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Какой граф... орграф smile
Берем точку-центр. Относительно нее сичитаем расстояния до всех точек. Составляем ребра от каждой к каждой, причем если расстояние от двух точек до центра большое, то и вес ребра будет большой. Только формулу придумать надо.

А то, как точки проверить на принадлежность полигону- сто раз обсуждалось и приводились исходники. Юзай Машину Тьюринга(с) esperant0


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
Aloha
Дата 27.12.2006, 20:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.
**


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

Репутация: 4
Всего: 165
OverBug
Цитата
а как определить что какая-то конкретная точка находится в нашем треугольнике

Можно придумать много разных способов сделать это, кое что уже обсуждалось на форуме. Придумался такой способ:

user posted image
user posted image

PS. Судя по всему, данный алгоритм будет работать для любого выпуклого многоугольника, главное вначале упорядочить вершины.


Это сообщение отредактировал(а) Aloha - 6.1.2007, 15:13

Присоединённый файл ( Кол-во скачиваний: 15 )
Присоединённый файл  _977700.gif 84,69 Kb
PM   Вверх
SoWa
Дата 28.12.2006, 04:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Сразу видим любителя векторов smile

Вообще полигон можно описать системой неравенств, каждое из которых будет описывать полуплоскость. Проверяешь точку в каждом неравенстве, и если все выполнились- то точка внутри полигона. Именно этот алгоритм реализован на ТурбоРассоле.


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
OverBug
Дата 28.12.2006, 11:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 84
Регистрация: 13.4.2006
Где: г.Пенза, Пензенск ой обл.

Репутация: нет
Всего: 1
Прикольно на векторах!!!! Блин!!! Так просто...  smile  smile   smile 
Все гениальное просто......
PM MAIL ICQ   Вверх
OverBug
Дата 20.3.2007, 20:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 84
Регистрация: 13.4.2006
Где: г.Пенза, Пензенск ой обл.

Репутация: нет
Всего: 1
Выложу пожалуй исходник на С++...   мож кому интересно будет

Код

#include <iostream>
#include <iomanip>
#include <tchar.h>

using namespace std;

struct POINT// структура опис. точку на плоскости
{
    int x ,y;
};

struct ATTEMPT//структура попытки выбора треугольника
{
    int mas[3];
    int s;
    int col_in, col_out;
};

int IsInTriangle(int i, POINT *pt, int mas[3])//проверяет находится точка в треугольнике или нет
{
    int c1,c2,c3,sign;
    c1 = c2 = c3 = 0;
    if(pt)
    {
        sign= (pt[mas[1]].x - pt[mas[0]].x)*(pt[mas[2]].y - pt[mas[1]].y) - (pt[mas[2]].x - pt[mas[1]].x)*(pt[mas[1]].y - pt[mas[0]].y);
        c1 = sign*((pt[mas[0]].x - pt[i].x)*(pt[mas[1]].y - pt[i].y) -    (pt[mas[1]].x - pt[i].x)*(pt[mas[0]].y - pt[i].y));
        c2 = sign*((pt[mas[1]].x - pt[i].x)*(pt[mas[2]].y - pt[i].y) -    (pt[mas[2]].x - pt[i].x)*(pt[mas[1]].y - pt[i].y));
        c3 = sign*((pt[mas[2]].x - pt[i].x)*(pt[mas[0]].y - pt[i].y) -    (pt[mas[0]].x - pt[i].x)*(pt[mas[2]].y - pt[i].y));

        if( c1 >0 && c2 >0 && c3 >0) return 1;// in triangle;/*в треугольнике*/

        sign = c1 + c2 + c3;

        if( sign == c1 || sign == c2 || sign == c3 ) return 3;//is a top of triangle;/*явл. вершиной треугольника*/

        if( c1 == 0 || c2 == 0 || c3 == 0) return 2;//on side of triangle;/*на стороне треунольника*/
    }
    return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Enter point's count (min 5 point's): ";
    int num; cin >> num;
    POINT *pt = (POINT *) malloc(sizeof(POINT)*num);
    cout << "Size of place is 20x20 symbol's." << endl;
    for(int i = 0; i<num; i++)
    {
        do
        {
            cout << "X" << i+1 << "=";
            cin >> pt[i].x; 
        }
        while(pt[i].x>20);

        do
        {
            cout << "Y" << i+1 << "=";
            cin >> pt[i].y; 
        }
        while(pt[i].y>20);
    }
    
    ATTEMPT *att = (ATTEMPT *) calloc(1,sizeof(ATTEMPT));
    int size = 1;
    int mas[3];
    int sign;
    /*чтобы исключить повторное исп. одного и того же треугольника циклы должны быть такими*/
    for(int a= 0; a<num; a++)
    {
        for(int b = a; b<num; b++)
        {
            for(int c = b; c<num; c++)
            {
                if(a != b && b != c && c !=a)//чтобы выбранные три точки на плоскости не совпадали
                {
                    mas[0] = a; mas[1] = b; mas[2] = c;
                    att[size-1].mas[0] = a;
                    att[size-1].mas[1] = b;
                    att[size-1].mas[2] = c;
                    att[size-1].col_in = 0;
                    att[size-1].col_out = 0;
                    for(int j = 0; j<num; j++)
                    {
                        sign = IsInTriangle(j, pt, mas);
                        if (sign == 1)
                            att[size-1].col_in+= 1;
                        if (sign == 0)
                            att[size-1].col_out+= 1;
                    }
                    size++;
                    att = (ATTEMPT *) realloc(att,sizeof(ATTEMPT)*size);
                }
            }
        }
    }

    cout.setf(ios::right);
    cout << setw(4) << "A" 
         << setw(4) << "B"
         << setw(4) << "C"
         << setw(7) << "Col_in" 
         << setw(7) << "Col_out" 
         << endl << endl;

    for(int a = 0; a<size;a++)
        if(att[a].col_in > 1)
            cout << setw(4) << att[a].mas[0] 
                << setw(4) << att[a].mas[1]
                << setw(4) << att[a].mas[2]
                << setw(7) << att[a].col_in 
                << setw(7) << att[a].col_out 
                << endl    << endl;
    cin >> sign;
    return 0;
}
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1819 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.