Как я могу вычислить координаты вершин зоны пересечения зебры из координат вершин полосы зебры?

Question

Я занимаюсь проблемой обнаружения пересечения зебры, и теперь я уже знаю вершины каждой полоски зебры в виде списка точек.Как я могу эффективно рассчитать координаты вершин прямоугольника контура, содержащего эти полосы зебры?

Я делаю это в 3D

Я думал над этим вопросом несколько дней, и не могу понять,решение, а не грубая сила ...

Это другая проблема, чем нахождение ограничивающего прямоугольника данного списка точек.Для этой задачи возвращением было бы четыре вершины этих полосок зебры.Мне просто нужно их выяснить.Любая помощь или указатели были бы полезны!

ОБНОВЛЕНИЕ: Я, наконец, отсортировал эти зебра-скрещивания по ориентации и легко нашел концевые полоски зебры.Остальная часть работы тривиальна

Answer 1

Из того, что вы говорите, кажется, что у вас есть трехмерные координаты контура прямоугольника. Я приму декартовы координаты и неискаженную геометрию.

Точки принадлежат плоскости, которую можно определить с помощью 3D-подгонки плоскости. Затем путем ортогональной замены переменных вы можете спроецировать точки на эту плоскость.

Для достаточно хорошей точности вы можете

• найти центр тяжести точек;

• найти точку, наиболее удаленную от центроида;

• разделить точку, установленную линией от центроида к этой точке;

• на обеих половинах, найдите самые отдаленные точки от центроида;

• соединяющая их линия позволяет вам разделить ее на четыре квадранта;

• в каждом квадранте, примените подгонку, чтобы найти края.

---

Если то, что вам нужно, это ограничивающий прямоугольник из нескольких полос, вы можете продолжить, как указано выше, чтобы найти направления сторон. Затем примените изменение координат, чтобы выровнять эти стороны по оси. Найти ограничивающий прямоугольник теперь просто.

Отмените преобразования, чтобы получить трехмерные координаты прямоугольника в 3D.

Answer 2

Как вы сказали, вы знаете координаты каждой отдельной полосы пересечения зебры.Итак, теперь вы можете определить первую и последнюю полосы, посмотрев максимальные и минимальные координаты всех вершин (рассматривая ось отсчета, от которой вы можете измерить расстояние).затем вы знаете координаты клеммных полос и, следовательно, вы можете сделать контур, учитывая координаты и, следовательно, делая больший прямоугольник из этих четырех координат, определяющих все пересечение зебры.