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

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 [Все]   Вниз
  Печать  
Автор Тема: Направление ввода полигона  (Прочитано 58845 раз)
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 Кб - загружено 2785 раз.)
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - 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 Кб - загружено 2738 раз.)
Записан
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
Команда клуба

ca
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)
Dale
Блюзмен
Команда клуба

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

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

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

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

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

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

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

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

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

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

ru
Offline Offline

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

Записан

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

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

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

При обходе вдоль всего контура внутренняя область полигона остается слева. Вывод: обход против часовой стрелки, несмотря на то, что в точках 2 и 5 углы внутренние.
Записан

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

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

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

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

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

Для всего полигона обход против часововой, т.к. вся площадь полигона всегда находится слева от контура. А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.
Записан
Dale
Блюзмен
Команда клуба

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

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

А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.

Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет.
Записан

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

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

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

ru
Offline Offline

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

А если точка 2 окажется левее точки 5?
Записан

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

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

WWW
« Ответ #37 : 27-12-2010 10:01 » 

Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
Записан

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

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

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

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

WWW
« Ответ #38 : 27-12-2010 10:04 » 

А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.

Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет.

Вот попытался проиллюстрировать эту мысль наглядно:



Единственная точка N полностью определяет направление контура в целом.

* Poly.png (3.55 Кб - загружено 1867 раз.)
Записан

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

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

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

ru
Offline Offline

« Ответ #39 : 27-12-2010 10:11 » 

Я сдаюсь.. Если выбор будет сделан на основе отнимем площадь треугольников по часовой и против - у кого больше тот и победил... Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится..
Записан

while (8==8)
Dimka
Деятель
Команда клуба

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

« Ответ #40 : 27-12-2010 10:16 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

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

WWW
« Ответ #41 : 27-12-2010 10:18 » 

Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится..

Например, я когда-то решал задачу заливки внутренней области полигона прямоугольниками. Это нужно для проектирования фотошаблонов при производстве микросхем. Важно знать, слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода.

Добавлено через 34 секунды:
Dale, если я правильно понял, то только для выпуклых многоугольников.

Что именно? Приведенная формула?
« Последнее редактирование: 27-12-2010 10:19 от Dale » Записан

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

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

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

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

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

Цитата: Dale
Что именно? Приведенная формула?
Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
sss
Специалист

ru
Offline Offline

« Ответ #43 : 27-12-2010 13:02 » 

...слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода.

Так вот, тогда, в месте локального треугольника, имеющего направление отличное от вычисленного общего, вы получите ошибку в определении направления.
« Последнее редактирование: 27-12-2010 13:29 от sss » Записан

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

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

WWW
« Ответ #44 : 27-12-2010 13:35 » 

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

Можно иллюстрацию?

Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным.

Да, в таком случае можно и по трем, если мы точно знаем, что в каждой точке поворот производится в одном направлении. Тогда остальные точки не дадут нам никакой новой информации. Но это слишком частный случай.
Записан

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

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

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

ru
Offline Offline

« Ответ #45 : 28-12-2010 02:24 » 

Посидел, посчитал площадь так и сяк. Признаю, для невыпуклых полигонов, был не прав . Пошел переделывать (добавлять) код..
Записан

while (8==8)
Алексей++
глобальный и пушистый
Глобальный модератор

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


« Ответ #46 : 28-12-2010 04:44 » 

sss, полигон у меня может быть не то чтобы даже выпуклым, а совсем впуклым )) Собственно, вот для чего делалось - в аттаче экзешник. В меню кнопка "отсечение линии". Отрезок разбивается полигоном на кусочки, и какие отрезки будут лежать внутри полигона - зависит от направления обхода (красным окрасятся, когда полигон ЧС, синим - ~ЧС)

Не работает только когда конец линии находится внутри полигона - не стал пока разбираться.



Добавлено через 2 минуты:
Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
при самопересечениях придётся разбивать полигон на несколько и считать их разными, соответственно

* GrafEdit_0012.rar (702.2 Кб - загружено 1069 раз.)
« Последнее редактирование: 28-12-2010 04:46 от Алексей1153 » Записан

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines