Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Направление ввода полигона  (Прочитано 26524 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« : 24-12-2010 05:18 » 

Имеется вот такая задача: определить направление (по ЧС или против ЧС), в котором были введены вершины полигона. Собственно, нужено чётко различить знак, а само понятие направления тут довольно условно. Вводится полигон так: мышью щёлкаем по окну, вводя последовательно точки-вершины. Я по своим догадкам попытался решить так (но, видимо, неправильно): беру первую вершину в качестве начала всех радиус-векторов, затем считаю сумму векторных произведений для всех смежных пар векторов по очереди. Каждый вектор суммы имеет знак в зависимости от направления вращения первого вектора ко второму, а чтобы не учитывалась длина исходных векторов, вектор-результат для каждой пары делится на произведение их модулей - как-будто полигон состоит из единичных векторов (хотя, не полностью уверен, что правильно так поступать). Все значения векторных произведений суммирую, получается итоговый "момент", по его знаку различаю направление ввода полигона

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

вот код:
Код:
//определить, по часовой стрелке направление или нет
bool CGrafics::Poligon_GetDirIsClock(CPoint* points,int count)const
{
if(!points || count<3)return true;

//считаем первую точку началом радиус-вектора

const LONG& x0=points[0].x;
const LONG& y0=points[0].y;

//остальные вершины представляют собой концы радиус-вектора
// для всех по очереди считаем векторное произведение
// и суммируем со знаком
double vecSumm=0;

LONG x1=points[1].x;
LONG y1=points[1].y;

for(int i=2;i<count; i++)
{
LONG x2=points[i].x;
LONG y2=points[i].y;

if(x1==x0 && y1==y0 || x2==x0 && y2==y0)
{
//одна из точек совпала с начальной точкой
}
else
{
//модуль вектора поворота надо будет разделить на произведения
//модулей векторов, чтобы не учитывалась длина векторов
LONG module1=sqrtl((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
LONG module2=sqrtl((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0));

if(module1 && module2)
{
vecSumm+=(x1*y2-y1*x2)*1.0/(module1*module2);
}
}

x1=x2;
y1=y2;
}

//знак суммы покажет направление вращения
return vecSumm>0;
}


Подскажите, кто знает, по какому алгоритму определить направление ввода полигона
« Последнее редактирование: 24-12-2010 05:20 от Алексей1153++ » Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 24-12-2010 06:44 » 

Есть такая книга "Математика и САПР", двухтомник, написали несколько французов.

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

Посмотреть смогу только дома, вряд ли она есть у меня на работе в виде скана.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #2 : 24-12-2010 07:27 » 

Dale, если не трудно, посмотри. Очень сильно нужно. Хотя бы странички с этим методом. Спасибо заранее )
Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 24-12-2010 17:18 » 

"Математика и САПР", Москва, "Мир", 1988, стр. 15:

A = 1/2*S(xi*yi+1 - xi+1*yi) + xN*y1 - x1*yN

Знак S означает "сумма по i от 1 до N-1".

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

P.S. Я бы на всякий случай проверил эту формулу. Книгу читал давным-давно, выводил формулу сам, но уже не помню, совпала ли с книгой. Скопировал полностью, но интуиция подсказывает, что на 2 следует делить все выражение.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 24-12-2010 17:41 » 

Dale,

Спасибо огромное Улыбаюсь Причём по правильности на правду больше похожа формула

A = S(xi*yi+1 - xi+1*yi) + xN*y1 - x1*yN

- ведь мне только знак нужен. Так что, всё-таки, деление на 2 - общее
Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 24-12-2010 18:08 » 

Если нужен только знак, конечно, можно обойтись и без деления. Хоть и мизерная, но экономия.

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 24-12-2010 18:32 » 

Dale, а я после цикла сделал хвостик с i и 0 индексами. А можно наоборот - до цикла сделать
Записан

sss
Специалист

ru
Offline Offline

« Ответ #7 : 27-12-2010 01:59 » 

Алексей1153++, для ускорения, можно проанализировать знак только для первых 3 точек полигона, не лежащих на одной прямой( S > 0)..
« Последнее редактирование: 27-12-2010 02:05 от sss » Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 27-12-2010 07:00 » 

Три отдельно взятые точки ничего не говорят о направлении контура в целом.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #9 : 27-12-2010 08:33 » 

Dale, гм.. поспорим? Почему не значат... Первый же входящий треугольник имеет направление обхода.. Если у последующих треугольников направление измениться - значит нет однозначности в определении обхода всего полигона..

Да... И почему именно три отдельно взятые? Последовательные по порядку точки конечно же..
« Последнее редактирование: 27-12-2010 08:36 от sss » Записан

while (8==8)
sss
Специалист

ru
Offline Offline

« Ответ #10 : 27-12-2010 08:46 » 


Решил все таки показать свой код..

Код:

#define EPSYLON                 ((real) 0.000000001)

typedef double                    real;

// Множество осей
enum CoordsAxis { xAxis = 0, yAxis, zAxis};

// Направления обхода
enum PolygonDetourMode{ dmAuto = 0, dmCW, dmCCW};

PolygonDetourMode CPolygon::DetectDetour( CoordsAxis a1, CoordsAxis a2) const throw ( EMathsssError*)
{
  CVertexPair side;
  VERTEX      Triangle[3];
  real        a1_d1, a1_d2, a2_d1, a2_d2, r, minL, t;
  bool        bCW( false), bCCW( false);

  for ( long lIdx = 0; lIdx < m_lCount; lIdx++)
  {
    for ( long i = 0; i < 3; i++)
      Triangle[i] = m_pVertexes[(lIdx + i) % m_lCount];

    //Выяснение "масштаба нуля"
    side.V[0] = Triangle[0];
    side.V[1] = Triangle[1];
    minL = side.Length;

    side.V[0] = Triangle[1];
    side.V[1] = Triangle[2];
    t = side.Length;
    if ( t < minL) minL = t;

    side.V[0] = Triangle[2];
    side.V[1] = Triangle[0];
    t = side.Length;
    if ( t < minL) minL = t;
    minL *= EPSYLON;

    a1_d1 = Triangle[1].Coords[a1] - Triangle[0].Coords[a1];
    a2_d1 = Triangle[1].Coords[a2] - Triangle[0].Coords[a2];

    a1_d2 = Triangle[2].Coords[a1] - Triangle[1].Coords[a1];
    a2_d2 = Triangle[2].Coords[a2] - Triangle[1].Coords[a2];
    r = (a1_d1 * a2_d2) - (a1_d2 * a2_d1);

    if ( fabs( r) > fabs( minL)) //Засчитываем попытку
    {
      if ( r < 0)
      {
        if ( bCCW)
        {
          throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
        }
        bCW = true;
      }
      else
      {
        if ( bCW) throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
        bCCW = true;
      }
    }
  }
  if ( bCW) return dmCW;
  else
  if ( bCCW) return dmCCW;
  throw new __EMathsssError( ERROR_DETOUR_DETECT_FAILED);
}

P.S.: Некоторые сложности с выяснением "масштаба нуля" возникают при реальных измерениях огромных полигонов..
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 27-12-2010 08:53 » 

Извольте.

Вот три последовательные точки некоего полигона:



Определите направление его обхода - по часовой стрелке либо же против.

* 3point.png (1.43 Кб - загружено 1060 раз.)
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #12 : 27-12-2010 08:55 » 

Не понял.. По часовой..
Записан

while (8==8)
yudjin
Помогающий

ua
Offline Offline
Пол: Мужской

« Ответ #13 : 27-12-2010 09:00 » 

извините за вторжение - а так?

* 3point.png (6.75 Кб - загружено 1226 раз.)
Записан
sss
Специалист

ru
Offline Offline

« Ответ #14 : 27-12-2010 09:01 » 

yudjin, у этого полигона неоднозначность.. Немного глубже провал - и даже общая площадь поменяет знак.. Или будет равна нулю..


И стоит ли тогда напрягать алгоритм???
« Последнее редактирование: 27-12-2010 09:04 от sss » Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 27-12-2010 09:03 » 

yudjin, абсолютно верно Улыбаюсь
Именно это я и не успел нарисовать.

sss, какая неоднозначность? Вы действительно не видите, что контур на самом деле обходится против часовой стрелки?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #16 : 27-12-2010 09:05 » 

Dale,мы говорим об методе, применимом только для выпуклых многоугольников. Хватит передергивать!!!
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 27-12-2010 09:07 » 

Dale,мы говорим об методе, применимом только для выпуклых многоугольников. Хватит передергивать!!!

Давайте внимательно прочитаем постановку задачи от Алексей1153++ и поищем там слово выпуклый. Лично у меня не получилось. Может, вам больше повезет?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #18 : 27-12-2010 09:08 » 

-
« Последнее редактирование: 27-12-2010 09:13 от sss » Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #19 : 27-12-2010 09:10 » 

Dale, откуда вы взяли метод, подсказанный вами.. Может быть прочитаете?

Пожалуйста:

"Математика и САПР", Москва, "Мир", 1988, стр. 15.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #20 : 27-12-2010 09:13 » 

Ну и что.. Там не написано, что этот метод подходит только для выпуклых многоугольников?
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #21 : 27-12-2010 09:15 » 

Конечно, нет. Выпуклость здесь не играет никакой роли.

Добавлено через 1 минуту и 20 секунд:
К тому же тогда понадобился бы алгоритм для предварительного определения выпуклости контура, чтобы исключить ошибочное применение данной формулы.
« Последнее редактирование: 27-12-2010 09:16 от Dale » Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #22 : 27-12-2010 09:32 » 

Читаю.. И не понимаю как можно было предложить эту ссылку... Нахождение площади и все..  Понятие направления обхода для невыпуклых полигонов - нонсенс!
« Последнее редактирование: 27-12-2010 09:33 от sss » Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #23 : 27-12-2010 09:33 » 

Можно посмотреть ссылку, по которой читаете? У меня эта книга в бумажном варианте.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #24 : 27-12-2010 09:34 » 

http://reslib.com/book/Matematika_i_SAPR__kniga_1
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #25 : 27-12-2010 09:36 » 

Первая сноска внизу стр. 15.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #26 : 27-12-2010 09:38 » 

Вы подумайте - если первый треугольник введен по часовой стрелке, второй против - какой "общий" обход полигона и почему??
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #27 : 27-12-2010 09:39 » 

Понятие направления обхода для невыпуклых полигонов - нонсенс!

Отнюдь. Полигон имеет некоторую внутреннюю область. При обходе контура эта область постоянно находится либо только справа, либо только слева. Где именно - зависит от направления обхода. Выпуклость в данном случае не имеет никакого значения.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Kivals
Команда клуба

us
Offline Offline
Пол: Мужской

WWW
« Ответ #28 : 27-12-2010 09:41 » 

... Понятие направления обхода для невыпуклых полигонов - нонсенс!
Не соглашусь. Нонсенсом было бы понятие обходя для многосвязных (вроде так называются?) полигонов. Возьмите класическую звездочку - это есть невыпуклый полигон, при этом направление определяется однозначно.

Dale, +1 Улыбаюсь
Записан
sss
Специалист

ru
Offline Offline

« Ответ #29 : 27-12-2010 09:42 » 

Dale, первый треугольник введен по часовой стрелке, второй против - какой "общий" обход.. Ответь пожалуйста? У кого площадь больше тот и победил?
Записан

while (8==8)
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines