Найти количество точек в трапеции

Question

Суть задачи - нахождение количества точек в области видимости некоего объекта. Область видимости представляет из себя трапецию.

Дано:

Массив объектов(на рисунке объект один), каждый из которых содержит следующие данные: координаты юнита, на рисунке взял за (0, 0). Радиус-вектор r. Угол зрения между боковыми сторонами(угол АОВ). Расстояние от объекта до ближней границы отсечения(отрезок AB) и до дальней границы отсечения(отрезок CD). Массив с координатами точек.

Сами данные представляют следующие два класса:

struct Point
{
    float x;
    float y;
};

struct Unit
{
    Point position;    // позиция игрока
    Point direction;   // радиус-вектор направления взгляда
    float fov_deg;         // угол зрения в градусах (между боковыми сторонами)
    float z_near, z_far; // ближняя и дальняя границы отсечения
};

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

int Task::calc_visible_points(const std::vector<Unit> &input_units, const std::vector<Point>& &points)
{
    
}

Мой способ решения

Подумал сначала найти координаты вершин получившейся трапеции и найти точки, которые находятся внутри этих вершин. Но мои скромные знания математики помогли только посчитать угол вектора r между Ox и Oy, координаты середины отрезка AB и CD они же точки M и N. Далее рассуждаю: Зная вектор r я могу сдвинуть его на угол, равный углу MOB, получится какой-то вектор, на котором будет лежать отрезок BD, точки которого мне нужно найти. Также я могу сдвинуть вектор на угол AOM, на котором будет лежать отрезок AC. Далее находить вершины трапеции как точки пересечения сдвинутого вектора с отрезками AB и CD ну или AC и BD. Возможно мой способ у кого получится дополнить или подтолкнет на другой вариант.

Answer 1

Вам требуется:

Опустить перпендикулярную проекцию точки или на отрезок MN, и проверить, что она находится в пределах отрезка (коэффициент t (здесь) находится в пределах 0..1), или на центральный луч

Если вы рассчитываете вектора OA, OB, то достаточно проверить, что векторные произведения OA x OP и OP x OB имеют один знак - в этом случае точка внутри сектора.

Если эти вектора у вас умозрительные, а в работе применяются только углы, то можно посчитать, что cos(OP,OM)>cos(половинного угла(например,AOM))

Answer 2

Дополню ответ выше реализацией на плюсах

int calc_visible_points(const std::vector<Unit>& input_units, const std::vector<Point>& points)
{
    int res = 0; 

    for (const auto& unit : input_units) {

        const float rLen = sqrt(unit.direction.x * unit.direction.x + unit.direction.y * unit.direction.y);

        const float halfTCos = cos(unit.fov_deg * M_PI / 360); // Половина угла видимости в cos

        const Point zn{ unit.z_near * unit.direction.x / rLen,
                        unit.z_near * unit.direction.y / rLen }; // координаты середины ближней границы

        const Point zf{ unit.z_far * unit.direction.x / rLen,
                        unit.z_far * unit.direction.y / rLen }; // координаты середины дальней границы

        const float tZnam = (zf.x - zn.x) * (zf.x - zn.x) + (zf.y - zn.y) * (zf.y - zn.y);

        for (auto point : points) {

            point.x -= unit.position.x;
            point.y -= unit.position.y;

            // Проверка нахождения точки в пределах ближней и дальней границ
            const float t = ((point.x - zn.x) * (zf.x - zn.x) + (point.y - zn.y) * (zf.y - zn.y)) / tZnam;

            if (t >= 0 && t <= 1) {
                const float rpTCos = (unit.direction.x * point.x + unit.direction.y * point.y) /
                    (rLen * sqrt(point.x * point.x + point.y * point.y)); // Угол между радиус-вектором и точкой

                // Проверка нахождения точки в пределах угла видимости
                if (rpTCos > halfTCos) res++;
            }
        }
    }

    return res;
}

БЛОГ НА HUSL

Найти количество точек в трапеции

Дано:

Мой способ решения

Ответы (2 шт):