На основании документации вводится два списка координат:
contour, определяющий исходный контур (красный на изображении ниже) convexhull определяет выпуклый корпус, соответствующий этому контуру (синий на изображении ниже)
Алгоритм работает следующим образом:
Если контур или корпус содержат менее 3 точек, то контур всегда выпуклый и больше не требуется никакой обработки.Алгоритм обеспечивает доступ к контуру и корпусу в одной и той же ориентации.
Примечание: В дальнейшем объяснении я предполагаю, что они находятся в одинаковой ориентации, и игнорирую деталио представлении глубины с плавающей точкой в виде целого числа.
Затем для каждой пары соседних точек корпуса (H[i], H[i+1]), определяющих один край выпуклой оболочки, рассчитайте расстояние открай каждой точки контура C[n], который лежит между H[i] и H[i+1] (исключая C[n] == H[i+1]).Если расстояние больше нуля, значит, дефект присутствует.При наличии дефекта запишите i, i+1, максимальное расстояние и индекс (n) точки контура, в которой находится максимум.
Расстояние рассчитывается следующим образом:
dx0 = H[i+1].x - H[i].x
dy0 = H[i+1].y - H[i].y
if (dx0 is 0) and (dy0 is 0) then
scale = 0
else
scale = 1 / sqrt(dx0 * dx0 + dy0 * dy0)
dx = C[n].x - H[i].x
dy = C[n].y - H[i].y
distance = abs(-dy0 * dx + dx0 * dy) * scale
Может быть проще визуализировать с точки зрения векторов:
C: вектор дефекта от H[i] до C[n]H: вектор края корпуса от H[i] до H[i+1]H_rot: вектор края корпуса H повернуто на 90 градусов U_rot: единичный вектор в направлении H_rot
H* Компоненты 1080 * равны [dx0, dy0], поэтому при повороте на 90 градусов [-dy0, dx0].
scale используется для поиска U_rot из H_rot, но поскольку деления в вычислительном отношении дороже, чем умножения, обратное используется в качестве оптимизации.Он также предварительно рассчитывается перед циклом над C[n], чтобы избежать повторного вычисления каждой итерации.
| H |= sqrt (dx0 * dx0 + dy0 * dy0)
U_rot = H_rot / | H |= H_rot * scale
Затем точечное произведение между C и U_rot дает перпендикулярное расстояние отточка дефекта указывает на край корпуса, и abs() используется для получения положительной величины в любой ориентации.
distance = abs (U_rot. C) = abs (-dy0 * dx + dx0 * dy) * scale
В сценарии, изображенном на изображении выше, в первой итерации ребро определяется как H[0] и H[1].Точки контура, которые нужно исследовать для этого края: C[0], C[1] и C[2] (начиная с C[3] == H[1]).
Тамдефекты на C[1] и C[2].Дефект в C[1] является самым глубоким, поэтому алгоритм будет записывать (0, 1, 1, 50).
Следующее ребро определяется H[1] и H[2] и соответствующей точкой контура C[3].Дефектов нет, поэтому ничего не записывается.
Следующее ребро определяется H[2] и H[3] и соответствующей точкой контура C[4].Дефектов нет, поэтому ничего не записано.
Начиная с C[5] == H[3], последнюю точку контура можно игнорировать - там не может быть дефектов.