Вычисление подобия двух наборов выпуклых многоугольников?

Question

Я сгенерировал 2 набора выпуклых многоугольников с помощью разных алгоритмов. Каждый многоугольник в каждом наборе описывается массивом координат [n_points, xy_coords], поэтому квадрат описывается массивом [4,2], но пятиугольник с закругленными углами имеет [80,2], а дополнительные 75 точек составляют используется для описания кривизны.

Моя цель - количественно определить, насколько похожи два набора геометрий.

Кто-нибудь может порекомендовать какие-либо методы для этого?

До сих пор я встречал:

• Расстояние Хэмминга
• Расстояние Хаусдорфа

Я хотел бы знать, какие другие надежные меры подобия для 2D полигонов. В идеале метод должен быть устойчивым к выпуклым многоугольникам и давать меру сходства между большими наборами (более 10 000 в каждом).

Answer 1

Предполагая, что оба многоугольника выровнены, центрированы и выпуклы, вы можете попытаться оценить сходство, вычислив отношение площади меньшего многоугольника к площади выпуклой оболочки обоих многоугольников.

Ratio = Min (Area (A) , Area (B)) / Area (ConvexHull (A, B))

Соотношение будет 1, если оба многоугольника равны, и 0, если они сильно различаются, как точка и квадрат.

Площадь многоугольника может быть вычислена за время O (N). См. Площадь многоугольника . Выпуклая оболочка может быть вычислена за O (N log N). См. Расчет выпуклой оболочки . Его можно ускорить до O (N) путем сортировки слиянием уже отсортированных вершин обоих полигонов и применения второй фазы алгоритма сканирования Грэма .