Богдан

[задачи] [курсы] [олимпиады] [регистрация]

		ИНФОРМАЦИЯ
	О школе Правила Олимпиады Фотоальбом Гостевая Форум Архив олимпиад

		ЗАДАЧНИК
	Архив задач Состояние системы Рейтинг Курсы

		МЕТОДИЧКА
	Новичкам Работа в системе Курсы ККДП Дистрибутивы Статьи Ссылки

СТАТИСТИКА

ФОРУМ

Вернуться
Тема: Помогите, пожалуйста, разобраться в авторском алгоритме пересечения отрезков (из раздела "Алгоритмы"): function Intersection (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 : real) : boolean; var v1, v2, v3, v4 : real; begin v1: = (bx2-bx1) * (ay1-by1) - (by2-by1) * (ax1-bx1); v2: = (bx2-bx1) * (ay2-by1) - (by2-by1) * (ax2-bx1); v3: =(ax2-ax1) * (by1-ay1) - (ay2-ay1) * (bx1-ax1); v4: =(ax2-ax1) * (by2-ay1) - (ay2-ay1) * (bx2-ax1); Intersection := (v1*v2<0) and (v3*v4<0); end; Хотел бы узнать, как называется метод, в чём суть, как и почему он работает. Заранее, спасибо.

1 Богдан, 19 июня 2018 г. 21:24:07
Большое спасибо.

2 Тер-Саркисов Богдан Олегович, 19 июня 2018 г. 12:10:50

Есть отрезок с концами (ax1, ay1), (ax2, ay2). Для него можно составить каноническое уравнение прямой, на которой он находится: (x - ax1) / (ax2 - ax1) = (y - ay1) / (ay2 - ay1). Затем приводим его к другому виду, перемножив крест-накрест и перенеся все в одну сторону: (ax2 - ax1)*(y - ay1) - (ay2 - ay1)*(x - ax1) = 0. Концы второго отрезка должны быть по разные стороны от прямой, на которой лежит первый отрезок. Чтобы это проверить, подставляют в выражение (ax2 - ax1)*(y - ay1) - (ay2 - ay1)*(x - ax1) сначала один конец второго отрезка, затем второй конец второго отрезка. Если два полученных числа (в коде это v3 и v4) имеют разные знаки, то они находятся по разные стороны от этой прямой.
Аналогичное делается для второго отрезка. Составляется его уравнение прямой, подставляются туда концы первого отрезка, получаются числа v1 и v2. Если произведение чисел отрицательное, то они имеют разные знаки.

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!