Добрый день.
Вопрос глупейший, подозреваю сказывается отсутствие ВО в области (менеджер самого среднего звена по образованию)
Есть сетка N x M, есть точка S(x,y) из которой проведена прямая в F(x,y).
Задача определить ячейки которые пересекаются прямой с некой толерантностью (если прямая идёт очень близко к некой ячейке но не пересекает её, мы всё равно засчитаем по причине попадания в зону толерантности).
Вот недокартинка иллюстрирующая что мне нужно. https://www.dropbox.com/s/gjxdwqapyafdh69/Clipboard01.png
На картинке розовая — прямая, зеленое — зона толерантности, и алгоритм должен обозначить левую нижнюю ячейку как попадающую под прямую.
Сейчас алгоритм написан крайне неэффективно. Я прохожу по каждой точке прямой с константным небольшим шагом (около 1/100) размера ячейки и проверяю принадлежность точки на этом шаге какой либо ячейке. После этого проверяется зона вокруг точки (проверяю псевдоокружность с константным радиусом с шагом 45 градусов, и проверяю ячейки по этой окружности).
Оно примерно даёт то что нужно, но работает с совершенно неприемлемой скоростью да и точность далека от идеала (а для алгоритма крайне нежелательны false-negative результаты, уж лучше false-positive).
Вернее конечно же алгоритм должен вернуть все 4 ячейки в результате. Имеется в виду что левая нижняя тоже должна быть в результате (хоть и не под прямой непосредственно)
Здравствуйте, BYBelorus, Вы писали:
BYB>Есть сетка N x M, есть точка S(x,y) из которой проведена прямая в F(x,y). BYB>Задача определить ячейки которые пересекаются прямой с некой толерантностью (если прямая идёт очень близко к некой ячейке но не пересекает её, мы всё равно засчитаем по причине попадания в зону толерантности).
Вначале посчитай координаты точек S', F', S'' и F'' — концов отрезков, представляющих собой границы полосы толерантности. Вместо решения задачи для «толстого» отрезка реши два экземпляра задачи для «тонких» отрезков.
BYB>Подскажите пожалуйста в какую сторону покопать.
Тебе нужно найти пересечение твоего отрезка с несколькими вертикальными линиями сетки, проходящими через AABB твоего отрезка. Две ячейки, прилегающие к каждой точке пересечения пометь. Аналогично для нескольких горизонтальных линий сетки.
Здравствуйте, BYBelorus, Вы писали:
BYB>Подскажите пожалуйста в какую сторону покопать.
Стоит посмотреть на алгоритм Ву. Он как раз находит ячейки, и долю пересечения их с толстой прямой. Вот из этой доли уже можно вычислять свой уровень толерантности.
Либо можешь начать даже с алгоритма Брезенхема — он проще, так как считает лишь точное пересечение, то есть с ним всё равно придётся проверять пару соседей ячейки. Но по крайней мере этот алгоритм ускорит продвижение вдоль прямой в сотню раз.
Q>Вначале посчитай координаты точек S', F', S'' и F'' — концов отрезков, представляющих собой границы полосы толерантности. Вместо решения задачи для «толстого» отрезка реши два экземпляра задачи для «тонких» отрезков.
Q>Тебе нужно найти пересечение твоего отрезка с несколькими вертикальными линиями сетки, проходящими через AABB твоего отрезка. Две ячейки, прилегающие к каждой точке пересечения пометь. Аналогично для нескольких горизонтальных линий сетки.
