как определить форму креста с заданными вершинами

Question

У меня возникают проблемы при формировании алгоритма, чтобы определить, будут ли 12 вершин, которые были введены пользователем в любом порядке, сформировать крестообразную форму в 2D-плоскости.Судя по тому, как я на это смотрю, это могут быть два пересекающихся прямоугольника.

Если я выберу грубую силу, сравнивая расстояния, я получу 67 расстояний от 12 вершин, что было бы невозможно сравнить все из них.Есть ли какая-нибудь характеристика креста или формы, которую я мог бы использовать?

Answer 1

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

1. Убедитесь, что ни один из 12 пунктов не является идентичным.

2. Должно быть только4 различных значения Х среди 12 баллов.Поместите их в порядке возрастания в массив, который мы назовем вашим X-вектором.

3. Сделайте то же самое со значениями Y, создав Y-вектор с 4 различными значениями.

4. Создайте массив 4x4, инициализируя все ячейки нулями.

5. Просмотрите каждое из 12 значений, используя их значения X и Y вместе с X-вектором.и Y-вектор, чтобы выбрать ячейку в массиве 4x4 для увеличения.Таким образом, если бы у вас была точка (12,9) и 12 было в записи [0] X-вектора, а 9 было в [2] записи Y-вектора, вы бы увеличили ячейку [0,2]массива 4x4.

6. Теперь ваш массив 4x4 должен выглядеть точно так:

0, 1, 1, 0
1, 1, 1, 1
1, 1, 1, 1
0, 1, 1, 0

Если тактогда это крест, как вы его определили.И если нет, или если это не удается на любом предыдущем этапе, то это не крест.

Answer 2

Должно работать что-то вроде следующего:

• собирать точки в наборе или списке
• повторять точки и находить различные координаты X и Y;должно быть ровно четыре разных значения для X и Y соответственно;если их больше или меньше, это не крестообразная форма
• сортирует различные координаты X и Y и называет их от x1 до x4 и y1 до y4
• проверьте, содержит ли исходный список точек именно такие точки (x1, y2), (x1, y3), (x2, y1), (x2, y2), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y3), (x3, y4), (x4, y2) и (x4, y3), в любом порядке
• , если есть другие свойства, которые должны быть выполнены, например, четыре плеча, имеющие одинаковую длину, также проверьте их, используя идентифицированные различные значения X и Y