Как найти клетки с которыми пересекается отрезок заданный двумя точками(на плоскости)

Здравствуйте, я хочу спросить совета какими максимально простыми способами можно найти с какими клетками на сетке пересекается отрезок, заданный двумя точками. Точки случайны, находятся на плоскости с осями X и Z. Точка P1(x1,z1) и P2(x2,z2). Для задач такого рода уже должны существовать простые не ресурсоёмкие решения, у меня у самого есть идея как это можно реализовать, однако я не уверен что это самый простой вариант. Свой вариант с иллюстрацией я приложу чуть позже(постараюсь в течении дня). Буду благодарен любой помощи и поддержке.

Миниатюры

 

0

Даниил2021, https://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма

2

Здравствуйте, большое спасибо за помощь, однако ознакомившись с указанной вами статьёй, я заметил что в алгоритме Брезенхэма координаты точек(начало и конец) прямой являются целыми числами и привязаны к сетке(выровнены по центру). В моём же случае координаты являются значениями с плавающей точкой(не целые числа) и никак не привязаны к сетке. Также в моём случае требуется чтобы любая клетка которая пересекается с прямой была подсвечена, даже если точка пересечения является углом клетки. Алгоритм Брезенхэма оставляет клетку не закрашенной если от точки на прямой до центра клетки(по вертикали) дистанция больше 0.5 что и вызывает то что не каждая пересечённая клетка подсвечивается. Данное недопонимание возникло скорее всего из-за моего не точного изложения вопроса. Но даже так благодарю вас за помощь, данный алгоритм натолкнул меня на новые мысли и пути решения, пока что я ещё думаю как реализовать это. Приложил примеры того что нужно мне и что выдаёт алгоритм Брезенхэма.

Миниатюры

 

0

Даниил2021, ты же не школьник, как я понимаю. по ссылке, что я привел, есть раздел "литература", в каждой специальной литературе есть свои термины, которые гуглшь и получаешь тысячи статей на все случаи.

1

Придумал метод основанный на уравнении прямой. Метод довольно таки прост, сначала округляем в меньшую сторону координаты точек до целых чисел, и записываем это как координаты пикселей начала и конца(Зелёный цвет). Дальше по уравнению прямой сначала подставляем все значения Х(Красный) что больше первой пиксельной координаты Х и до последней пиксельной координаты Х.
Считаем по уравнению координаты Z(Синий) и округляя их(в меньшую сторону) получаем список координат пикселей. Это набор пикселей получившийся при движении по оси Х. Теперь тоже самое делаем двигаясь по оси Z. А дальше убираем дубликаты координат из двух наборов. На рисунке по порядку 1 этап, 2 этап, 3 этап. Также чтобы использовать этот метод нужно чтобы вектор отрезка был направлен в положительную четверть, иначе метод не будет работать корректно. Но это сделать не сложно, поэтому это даже не проблема. Проблема с которой я столкнулся теперь, это то что даже так если прямая пересекает точку между 4 квадратами то подкрасится лишь 2 из них. А мне требуется чтобы подкрасились все 4. Так как логически пересекая эту точку прямая пересекает все 4 квадрата. Буду думать как это исправить. Если есть идеи пишите, буду благодарен любым мыслям и помощи.

На нижнем отрезке видно что будет если вектор отрезка направлен не в положительную четверть. Начальные точки с лева, конечные справа.

Миниатюры

 

0

Сообщение от Даниил2021 Придумал метод основанный на уравнении прямой.

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

Сообщение от Даниил2021 Алгоритм Брезенхэма оставляет клетку не закрашенной если

Алгоритм Брезенхэма - это алгоритм не определяющий пересечение клеток. Это алгоритм строящий аппроксимацию прямой и всегда выбирает только одну наиболее подходящую клетку.

0

Кажется я доделал метод, и теперь он должен будет работать прекрасно.
Суть метода не поменялась. Сначала зная координаты точек по уравнению прямой я составляю 2 набора координат. Сначала подставляя целые Х-сы и получая Z. Потом подставляя целые Z я получаю X-сы.

Не обязательно каждый раз считать коэффициент, его можно посчитать 1 раз и просто прибавлять при каждом новом цикле, а поскольку это 2 разных уравнения то 2 коэффициента. В конце концов всё сводится к простой арифметике, никакого деления и умножения. Теперь нужно полученные значения координат(не целые числа) округлить в меньшую сторону в java Math.floor(). И у нас получится набор координат клеток(или пикселей).


Однако теперь нужно выполнить операцию которая поможет исправить проблему с 4 квадратами. Моя тактика такова что двигаясь по значениям Х(1,2,3) подставляя их, если полученная координата Z после округления не изменится(было допустим 5, и после округления осталось 5) значит я сейчас на точке между 4 блоками, и нужно полученную координату пикселя сместить в -1 по оси Z. То есть на рисунке сдвинуть вверх. Это что нужно делать при движении по целым значениями на оси X. (Красные)

С осью Z очень похожая тактика, только если мы опять оказались на угле нужно не смещать пиксель в - по Z, а добавить новый пиксель(дополнительный) координаты которого будут такие же только -1 по оси X. То есть на рисунке сделать дубликат пикселя и сдвинуть его на клетку влево. (Синие)

Теперь всегда все пиксели будут закрашены правильно, и не нужно делать проверку на совпадения координат пикселей(нужно но только для первого и последнего пикселя-клетки).

Данное решение мне требуется для 3-х мерного пространства, но добавление ещё одной оси не меняет сути принципа. Просто нужно будет посчитать 6 коэффициентов и составить 3 списка с координатами клеток которые надо будет объединить. + нужно не забывать что если начальная Х координата и конечная находятся на одной высоте(после округления) то значит выполнять расчётов по этой оси не надо(горизонтальная линия или вертикальная). И много таких подробностей которые и не упомнить. Как напишу сам код приложу его сюда. Вот иллюстрация работы данной логики.

Миниатюры

 

0

Также заметил что можно не делать проверку на совпадения совсем если просто изначально не добавлять конечную позицию в список клеток изначально, когда мы посчитали её в самом начале.

0

Теперь попробую понять как лучше работать с отрезком если его вектор не направлен в положительную четверть. Вот нашёл зависимости от того куда направлен вектор отрезка, надо теперь вывести простую формулу для подсчёта смещения по Х и по Z в каждый цикл(движение по Х и движение по Z). Чтобы в любом направлении метод работал корректно. Так по идее меньше придётся переводить данных после вычисления позиций клеток(Так пришлось бы сначала повернуть вектор в положительную четверть, потом посчитать точки, потом повернуть обратно), а так я меняю вычисление 1 переменной 1 раз которая будет влиять на то как выбирается клетка.

Миниатюры

 

0