kray_zemli (kray_zemli) wrote,
kray_zemli
kray_zemli

Category:

Ещё одно тестовое задание

Неужели я так плохо делаю тестовые задания? Лаборатория Касперского пропала без вести. ДубльГис пропал без вести. Сейчас вот отправил в Бриксис Текнолоджис. Первое впечатление -- контора лишь чуть-чуть получше той, где я считаю реакторы, но как первый этап знакомства с индустрией сойдёт. Пишут что-то типа Автокада.

Тестовое задание дали такое: написать функцию, проверяющую пересечение двух треугольников. Задание вроде простое, а геморрою с ним порядочно. Зато теперь я понял, отчего в игрушках приходится постоянно застревать в текстурах.

Решение я выбрал следующее (за быстродействием особо не гнался).

1. Сравниваем описывающие параллелепипеды, если не пересекаются -- возвращаем false. Шаг лишний, на самом деле, при отладке и тестировании я это выключал, но в финальной версии оставил на случай.

2. Тупым сравнением координат ищем общие вершины треугольников. Если все вершины совпали -- возвращаем true, если совпали две -- возвращаем false (копланарность треугольников всё равно нормально не проверить). Вообще-то это ещё более лишний шаг, исключительно на случай смежных треугольников, но в условии не было обговорено, стоит ли обрабатывать такой случай.

3. Выбираем за A треугольник площадью побольше, ищем его нормаль при помощи векторного произведения (его модуль и есть площадь). Если квадрат нормали A меньше Эпсилон (наименьшего положительного неденормализованного double), то считаем, что не пересекаются.

4. Проецируем второй треугольник B в плоскость A, заодно определяя расстояние от его вершин до плоскости.

5. Ищем точки пересечения рёбер B с плоскостью A. Если расстояния обеих вершин одного знака, то пересечения нет, если разного -- то есть. Точку пересечения можно найти линейной интерполяцией проекций вершин с учётом расстояний до плоскости. В результате должно получиться либо 0 (не пересекаются), либо 2 пересечения, дающие отрезок X, являющийся пересечением B с плоскостью A. Если 0 -- понятное дело, треугольники не пересекаются, а если 2 -- надо смотреть дальше. И вот тут первая засада -- если одна или тем более две вершины B лежат в плоскости A. В первом случае проблема в том, что такая вершина является точкой пересечения двойной кратности. Треугольники не пересекаютя, но как будто бы всё нормально -- есть два пересечения. Если A и B имеют одну общую вершину -- то можно заранее позаботиться о кратности такой точки. Но в общем случае я поступаю так: если точек пересесения две, но квадрат расстояния между ними меньше Эпсилон, то возвращаю false. А если треугольники пересекаются -- то вообще будет 3 точки пересечения, и из них ещё надо выбрать правильные. Я сделал тупо -- из 3 возможных отрезков выбираю длиннейший. Если же две вершины B лежат в плоскости A, то возникнет ещё и проблема с линейной интерполяцией, так как разница расстояний, что стоит в знаменателе, равна нулю. Я в этом случае разницу тупо проверяю на плюс-минус Эпсилон и вместо интерполяции беру среднее. Хотя можно было бы просто вернуть false.

6. Ну а теперь надо проверить пересечение A с отрезком X. Здесь всё то же самое: определяются расстояния от вершин A до X, а также расстояния от проекций этих точек до одного из концов X. Для этого вектор X нормируется, а также вычисляется перпендикуляр через векторное произведение нормали A и вектора X. Собственно, все проблемы здесь точно такие же, как в предыдущем пункте. Разве что в случае 3-х пересечений проще -- просто выбираем наименьшую и наибольшую координаты.

7. Итак, если минимальная координата пересечения больше длины отрезка, либо максимальная меньше нуля, то false, иначе true.

Вот так вот. Задача вроде простая, а сколько, оказывается, вычислений требуется, и сколько особых случаев!
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments