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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.11.2008, 03:10
гость

 
Сообщений: n/a

пересечение отрезков
Код из статьи о пересечении отрезков не работает:

Код:
bool IsLinesCross(int x11, int y11, int x12, int y12, int x21, int y21, int x22, int y22)
{

int maxx1 = std::max(x11, x12), maxy1 = std::max(y11, y12);
int minx1 = std::min(x11, x12), miny1 = std::min(y11, y12);
int maxx2 = std::max(x21, x22), maxy2 = std::max(y21, y22);
int minx2 = std::min(x21, x22), miny2 = std::min(y21, y22);

if (minx1 > maxx2 || maxx1 < minx2 || miny1 > maxy2 || maxy1 < miny2)
  return false;  // Момент, када линии имеют одну общую вершину...

int dx1 = x12-x11, dy1 = y12-y11; // Длина проекций первой линии на ось x и y
int dx2 = x22-x21, dy2 = y22-y21; // Длина проекций второй линии на ось x и y
int dxx = x11-x21, dyy = y11-y21;
int div, mul;


if ((div = (int)((double)dy2*dx1-(double)dx2*dy1)) == 0)
  return false; // Линии параллельны...
if (div > 0) {
  if ((mul = (int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > div)
    return false; // Первый отрезок пересекается за своими границами...
  if ((mul = (int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > div)
     return false; // Второй отрезок пересекается за своими границами...
}

if ((mul = -(int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > -div)
  return false; // Первый отрезок пересекается за своими границами...
if ((mul = -(int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > -div)
  return false; // Второй отрезок пересекается за своими границами...

return true;
}

printf("%s\n", IsLinesCross(553,926, 557,940, 202,929, 1129,929) ? "true" : "false");
printf("%s\n", IsLinesCross(202,929, 1129,929, 553,926, 557,940) ? "true" : "false");
Выводит

true
false

Хотя я только поменял отрезки местами в аргументах функции. Получается, что P1 пересекается с P2, но P2 не пересекается с P1 ?
  #2  
Старый 15.11.2008, 15:10
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

http://kladovka.net.ru/delphibase/?a...hcalc&id=10708
  #3  
Старый 01.02.2010, 22:33
Amper

 
Сообщений: n/a

Использую такую функцию

Код:
bool IsLinesCross(Tsegment s1, Tsegment s2)
{
	float zn = (s2.B.y-s2.A.y)*(s1.B.x-s1.A.x) - (s2.B.x-s2.A.x)*(s1.B.y-s1.A.y);
	float ch1 = (s2.B.x-s2.A.x)*(s1.A.y-s2.A.y) - (s2.B.y-s2.A.y)*(s1.A.x-s2.A.x);
	float ch2 = (s1.B.x-s1.A.x)*(s1.A.y-s2.A.y) - (s1.B.y-s1.A.y)*(s1.A.x-s2.A.x);

	if (zn == 0) return false;

	if ((ch1/zn <= 1 && ch1/zn >= 0) && (ch2/zn <= 1 && ch2/zn >= 0))
		return true;
	return false;
}
Код:
struct Tpoint

{

	float x;

	float y;

};

struct Tsegment
{
	Tpoint A;
	Tpoint B;
};
  #4  
Старый 18.02.2011, 13:17
ales

 
Сообщений: n/a

Для if (div > 0) не хватает else
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Построение отрезков в большом множестве Денис Вычислительная геометрия 1 12.07.2008 22:18
Пересечение отрезков гость Реализация, исходники, языки 1 26.12.2007 00:29
дерево промежутков (отрезков) гость Графы 1 18.11.2007 13:41
Пересечение отрезков Lomir Задачи 2 22.10.2007 22:50
Пересечение двух отрезков в 3d. незарегистрированный Математические алгоритмы 1 25.01.2007 12:17