Какова формула пересечения отрезков на шахматной доске? Привет,
на тему пересечений отрезков и проекции точки на линию - все готовое уже есть, много примеров и формул. Как можно упростить формулы, если геометрическое пространство - это шахматная доска? Т.е.
1. Координаты точки, или начала и конца отрезка - целочисленные.
2. Отрезки могут располагаться в трех направлениях: вертикально, горизонтально, по диагонали.
Т.е. в этом "мире" нет иных углов, кроме 0, 45 и 90.
Задача:
1. Найти точку пересечения двух отрезков.
2. Найти точку пересечения отрезка и линии, проведенной (до первого пересечения) из некой точки в одном из 8 возможных направлений.
Готового кода, конечно, не прошу, просто куда копнуть, чтобы посчитать это быстро (нужна высокая скорость вычислений).
UPD1: еще проще, есть точка с двумя координатами, и из нее направление (одно из 8 возможных, по сторонам света). Где-то на этой же плоскости есть отрезок, заданный координатами начала и конца. Если двигаясь из точки мы в итоге пересечем отрезок, то только под углом 90 или 45 градусов. Нужно найти точку пересечения, имяя координаты точки, направление движения, и координаты отрезка.
Какова формула пересечения отрезков на шахматной доске? Привет,
на тему пересечений отрезков и проекции точки на линию - все готовое уже есть, много примеров и формул. Как можно упростить формулы, если геометрическое пространство - это шахматная доска? Т.е.
1. Координаты точки, или начала и конца отрезка - целочисленные.
2. Отрезки могут располагаться в трех направлениях: вертикально, горизонтально, по диагонали.
Т.е. в этом "мире" нет иных углов, кроме 0, 45 и 90.
Задача:
1. Найти точку пересечения двух отрезков.
2. Найти точку пересечения отрезка и линии, проведенной (до первого пересечения) из некой точки в одном из 8 возможных направлений.
Готового кода, конечно, не прошу, просто куда копнуть, чтобы посчитать это быстро (нужна высокая скорость вычислений).
UPD1: еще проще, есть точка с двумя координатами, и из нее направление (одно из 8 возможных, по сторонам света). Где-то на этой же плоскости есть отрезок, заданный координатами начала и конца. Если двигаясь из точки мы в итоге пересечем отрезок, то только под углом 90 или 45 градусов. Нужно найти точку пересечения, имяя координаты точки, направление движения, и координаты отрезка.
на тему пересечений отрезков и проекции точки на линию - все готовое уже есть, много примеров и формул. Как можно упростить формулы, если геометрическое пространство - это шахматная доска? Т.е.
1. Координаты точки, или начала и конца отрезка - целочисленные.
2. Отрезки могут располагаться в трех направлениях: вертикально, горизонтально, по диагонали.
Т.е. в этом "мире" нет иных углов, кроме 0, 45 и 90.
Задача:
1. Найти точку пересечения двух отрезков.
2. Найти точку пересечения отрезка и линии, проведенной (до первого пересечения) из некой точки в одном из 8 возможных направлений.
Готового кода, конечно, не прошу, просто куда копнуть, чтобы посчитать это быстро (нужна высокая скорость вычислений).
UPD1: еще проще, есть точка с двумя координатами, и из нее направление (одно из 8 возможных, по сторонам света). Где-то на этой же плоскости есть отрезок, заданный координатами начала и конца. Если двигаясь из точки мы в итоге пересечем отрезок, то только под углом 90 или 45 градусов. Нужно найти точку пересечения, имяя координаты точки, направление движения, и координаты отрезка.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
В данном случае, когда все координаты целочисленные и отрезки могут располагаться только вертикально, горизонтально или по диагонали под углом 45 или 90 градусов, можно использовать следующий алгоритм:
Для начала определите направление, по которому движется ваша точка (север, юг, восток, запад, северо-восток, северо-запад, юго-восток, юго-запад).Далее определите, пересекает ли линия (проведенная из точки) отрезок. Это можно сделать, сравнив координаты точки и координаты начала и конца отрезка.Если линия пересекает отрезок, найдите точку пересечения. Для этого вам нужно будет рассмотреть два случая: когда отрезок вертикален и когда горизонтален.В общем случае формула пересечения отрезков под углом 90 или 45 градусов сложнее и состоит из системы уравнений. Однако с учетом ограничений, которые вы предоставили, можно значительно упростить и ускорить процесс вычислений. Не забудьте также проверить случаи, когда точка находится на концах отрезка или отрезок вырожден (длина равна 0).