VPF::[Borland C++] Четырёхугольник - Форум программистов

Forpost

Дата 7.10.2009, 18:45 (ссылка)

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

Загрузка ...

Новичок

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

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

Здравствуйте, уважаемые программисты.
Подскажите пожалуйста, как решить задачу:
Четырехугольник ABCD задан координатами своих вершин на плоскости: : А(ха,уа), В(хb,уb), С(хс,ус), D(xd,yd). Проверить, является ли он выпуклым. Замечание. Есть несколько способов проверки выпуклости: анализ линейных неравенств, задаваемых сторонами; разбиение четырехугольника на треугольники со сравнением сумм их площадей и другие.

Заранее огромное спасибо.

Это сообщение отредактировал(а) Forpost - 7.10.2009, 18:45

t_gran

Дата 8.10.2009, 09:30 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

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

Код


#include <iostream>

using namespace std;

struct TPoint
{
   int x, y;
};

//----------------------------------------------//
bool Intersection (TPoint start1, TPoint start2, TPoint end1, TPoint end2)
{
   TPoint dir1= {end1.x - start1.x, end1.y - start1.y};
   TPoint dir2= {end2.x - start2.x, end2.y - start2.y};

   //считаем уравнения прямых проходящих через отрезки
   float a1= -dir1.y;
   float b1= +dir1.x;
   float d1= -(a1*start1.x + b1*start1.y);

   float a2= -dir2.y;
   float b2= +dir2.x;
   float d2= -(a2*start2.x + b2*start2.y);

   //подставляем концы отрезков, для выяснения в каких полуплоскотях они
   float seg1_line2_start= a2*start1.x + b2*start1.y + d2;
   float seg1_line2_end= a2*end1.x + b2*end1.y + d2;

   float seg2_line1_start= a1*start2.x + b1*start2.y + d1;
   float seg2_line1_end= a1*end2.x + b1*end2.y + d1;

   //если концы одного отрезка имеют один знак, значит он в одной полуплоскости и пересечения нет.
   if (seg1_line2_start * seg1_line2_end >= 0 || seg2_line1_start * seg2_line1_end >= 0) 
      return false;

   return true;
}
//----------------------------------------------//
int main (int argc, char **argv)
{
   TPoint a= {1, 1};
   TPoint b= {5, 1};
   TPoint c= {5, 3};
   TPoint d= {1, 5};
   cout << (Intersection(a, b, c, d) ? "Выпуклый" : "Вогнутый") << endl;
   return 0;
}

Работает по принципу нахождения пересечения диагоналей. Функция взята отсюда.

Это сообщение отредактировал(а) t_gran - 8.10.2009, 10:28

--------------------

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