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

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

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

Такую задачу можно решить следующим кодом:

			public class Line {
	// Сверхмалая единица, которую мы используем для сравнения чисел с плавающей точкой:
	static double epsilon = 0.000001;
	// Наклон прямой:
	public double slope;
	// Сдвиг прямой по OY:
	public double yintercept;

	public Line(double s, double y) {
		slope = s;
		yintercept = y;
	}

	public boolean intersect(Line line2) {
		return Math.abs(slope - line2.slope) > epsilon || Math.abs(yintercept - line2.yintercept) < epsilon;
	}
}
		

В этом решении линия будет задаваться двумя параметрами — сдвигом по оси X и наклоном по оси Y. Далее мы в два этапа проверяем, считаются ли линии параллельными.

Ранее мы условились, что совпадающие линии мы будем считать пересекающимися. Соответственно, если выяснится, что две линии имеют одинаковый сдвиг (то есть разница между сдвигами окажется меньше нашей сверхмалой единицы) — это автоматически означает, что они пересеклись.

Далее, если окажется, что у одной линии наклон по Y не такой, как у другой — это также будет означать, что линии рано или поздно пересекутся.

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

Поэтому мы будем использовать для сравнения отдельную малую единицу (в математике малые единицы часто обозначаются греческой буквой “эпсилон”): при оперировании с таким числом еще будет сохраняться достаточная точность, поэтому мы сможем более точно определять, являются ли равными числа. В нашем случае получается: если разница двух чисел окажется больше достаточно малой величины, это будет означать, что они различаются, а значит, не равны друг другу.