Алгоритм определения наложения отрезков - C/C++

Добрый день.

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

Вообщем, ситуация такая:
есть несколько видов отрезков

        -----------------         ------------------                 ---------------
================           =====                      =====================

       |       |                                                     |    |

символами "|" я показал, что в этих местах они пересекаются. Как определить, что один отрезок пересекает другой для отсечения пересечения из одного из видов отрезков?

Здравствуйте, Logot, Вы писали:

L>Вот мучаюсь с алгоритмом, который должен определять, что отрезки пересекаются в одной плоскости, не поможете?

L>Как определить, что один отрезок пересекает другой для отсечения пересечения из одного из видов отрезков?

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

Здравствуйте, Logot, Вы писали:

L>

L>        -----------------         ------------------                 ---------------
L>================           =====                      =====================

L>       |       |                                                     |    |

L>

 bool  empty() const                      { return (l > h); }
 inline _range_t& operator&=(_range_t<C> a)    { l = max(l,a.l); h = min(h,a.h); return *this; }

 template <typename C> inline bool operator&&(_range_t<C> a,_range_t<C> b)            
 { 
  return 
    (max(a.l,b.l)) <= 
    (min(a.h,b.h));
 }

Здравствуйте, Logot, Вы писали:

L>Добрый день.

L>Вот мучаюсь с алгоритмом, который должен определять, что отрезки пересекаются в одной плоскости, не поможете?

L>Вообщем, ситуация такая:
L>есть несколько видов отрезков

L>

L>        -----------------         ------------------                 ---------------
L>================           =====                      =====================

L>       |       |                                                     |    |

L>

L>символами "|" я показал, что в этих местах они пересекаются. Как определить, что один отрезок пересекает другой для отсечения пересечения из одного из видов отрезков?

Отсортировать концы отрезков по координате Х, причем в итоговом массиве хранить признак конец/начало и ссылку на отрезок. И 1 раз пройтись по массиву считая пересечение следующей точки со всеми уже начатыми отрезками.

Здравствуйте, AK85, Вы писали:

AK>Отсортировать концы отрезков по координате Х, причем в итоговом массиве хранить признак конец/начало и ссылку на отрезок. И 1 раз пройтись по массиву считая пересечение следующей точки со всеми уже начатыми отрезками.
А зачем двупроходный алгоритм писать когда можно однопроходный написать?

struct LINE1D {
  float fBegin,fLength;
};
bool IntersectLine2D(const LINE1D& Line1,const LINE1D& Line2,LINE1D& LineIntersect) {
  const float fDelta = Line2.fBegin-Line1.fBegin;
  if(fDelta1 < 0) {
    const float fNewLength = Line2.fLength+fDelta1;
    if(fNewLength > 0) {
      LineIntersect.fBegin = Line1.fBegin;
      LineIntersect.fLength = fNewLength;
      return true;
    }
  } else {
    const float fNewLength = Line1.fLength-fDelta;
    if(fNewLength > 0) {
      LineIntersect.fBegin = Line2.fBegin;
      LineIntersect.fLength = fNewLength;
      return true;
    }
  }
  return false;
}

Здравствуйте, Vain, Вы писали:

V>

V>struct LINE1D {
V>  float fBegin,fLength;
V>};
V>bool IntersectLine2D(const LINE1D& Line1,const LINE1D& Line2,LINE1D& LineIntersect) {
V>  const float fDelta = Line2.fBegin-Line1.fBegin;
V>  if(fDelta1 < 0) {
V>    const float fNewLength = Line2.fLength+fDelta1;
V>    if(fNewLength > 0) {
V>      LineIntersect.fBegin = Line1.fBegin;
V>      LineIntersect.fLength = fNewLength;
V>      return true;
V>    }
V>  } else {
V>    const float fNewLength = Line1.fLength-fDelta;
V>    if(fNewLength > 0) {
V>      LineIntersect.fBegin = Line2.fBegin;
V>      LineIntersect.fLength = fNewLength;
V>      return true;
V>    }
V>  }
V>  return false;
V>}
V>

Не работает в таком случае:

-------------------------------------------------------------------------------------
           =============          =====       ===========           ================

Здравствуйте, c-smile, Вы писали:

L>>

L>>        -----------------         ------------------                 ---------------
L>>================           =====                      =====================

L>>       |       |                                                     |    |

L>>

CS>

CS> bool  empty() const                      { return (l > h); }
CS> inline _range_t& operator&=(_range_t<C> a)    { l = max(l,a.l); h = min(h,a.h); return *this; }

CS> template <typename C> inline bool operator&&(_range_t<C> a,_range_t<C> b)            
CS> { 
CS>  return 
CS>    (max(a.l,b.l)) <= 
CS>    (min(a.h,b.h));
CS> }
CS>

Чё-то я не понял сути. Что такое l, h, тип <C>? Можно немного разжевать?

Здравствуйте, Logot, Вы писали:

L>Не работает в таком случае:
L>

L>-------------------------------------------------------------------------------------
L>           =============          =====       ===========           ================
L>

Если линии не разделены на группы, то да.
А если разделены, то на вход Line1 надо подовать одну группу, на вход Line2 — другую, по очереди. Вообще для начала, надо подготовить структуры данных, наиболее подходящие для хранения и разделения линий. И уже писать алгоритм на основе этих структур.

	От:	Logot
	Дата:	06.09.06 17:24
	Оценка:

	От:	commando
	Дата:	06.09.06 20:41
	Оценка:

От:	c-smile	http://terrainformatica.com
Дата:	06.09.06 21:20
Оценка:

	От:	AK85
	Дата:	07.09.06 06:21
	Оценка:

От:	Vain	google.ru
Дата:	07.09.06 13:20
Оценка: