Нахождение квадрата в группе координат

Просто чтобы прояснить, фактическая длина боковых сегментов не имеет значения, верно? Все, что вас волнует, — образуют ли полубесконечные линии, образованные боковыми сегментами двух троек, квадрат? Или фактические сегменты должны пересекаться?

Предполагая первый, способ проверить, образуют ли две тройки квадрат, заключается в следующем. Давайте использовать Point3D а также Vector3D от System.Windows.Media.Media3D Пространство имен для определения некоторой терминологии, так как это достойные универсальные трехмерные точки двойной точности и векторы, которые поддерживают основные методы линейной алгебры. Это c #, поэтому вы не можете использовать их напрямую, но я бы хотел сослаться на некоторые из основных методов, упомянутых там.

Вот основной метод проверки, пересекаются ли две тройки:

1. Определите тройку следующим образом: Center, Side1 и Side2 как три структуры Point3D.

2. Для каждой тройки определите нормализованный диагональный вектор как

   NormalizedDiagonal = ((Side1 - Center) + (Side2 - Center));
NormalizedDiagonal.Normalize()

   (Вы можете кэшировать это для производительности.)

3. Проверьте, равны ли два центра в пределах определенного вами линейного допуска. Если равно, верните false — это вырожденный случай.

4. Убедитесь, что два диагональных вектора антипараллельны в пределах определенного углового допуска. (Т.е. NormalizedDiagonal1 == -NormalizedDiagonal2 с некоторым допуском.) Если нет, верните false, а не квадрат.

5. Вычислите вектор из triple2.Center в triple2.Center: delta = triple2.Center - triple1.Center,

6. Если double deltaDotDiagonal = DotProduct(delta, triple1.NormalizedDiagonal) < 0, вернуть false — две тройки указывают друг на друга.

7. Наконец, вычислите расстояние от центра triple2 до (бесконечной) диагональной линии, проходящей через центр triple1. Если ноль (в пределах вашего линейного допуска), они образуют квадрат.

   Чтобы вычислить это расстояние: distance = (delta - deltaDotDiagonal*triple1.NormalizedDiagonal).Length

   Замечания: deltaDotDiagonal*triple1.NormalizedDiagonal это проекция delta вектор на triple1.NormalizedDiagonal, и поэтому delta - deltaDotDiagonal*triple1.NormalizedDiagonal является компонентом delta это перпендикулярно этой диагонали. Его длина — это расстояние, которое мы ищем.

Наконец, если ваше определение квадрата требует пересечения фактических боковых сегментов, вы можете добавить дополнительную проверку, что длины всех боковых сегментов меньше, чем sqrt(2) * delta.Length,

Этот метод проверяет, образуют ли две тройки квадрат. Поиск всех троек, образующих квадраты, это, конечно, O (N-квадрат). Если это проблема, вы можете поместить их в массив и отсортировать angle = Atan2(NormalizedDiagonal.Y, NormalizedDiagonal.X), Сделав это, вы можете найти тройки, которые потенциально образуют квадраты с заданной тройкой, с помощью двоичного поиска в массиве тройки с углами = +/- π от угла текущей тройки в пределах вашего углового допуска. (Когда угол около π, вам нужно проверить начало и конец массива.)

Обновить

Хорошо, давайте посмотрим, смогу ли я сделать это с вашими классами. У меня нет определений для Vec2i а также Vec2f так что я могу ошибиться …

double getLength(Vec2f vector)
{
return sqrt(pow(vector[0], 2) + pow(vector[1], 2));
}

Vec2f scaleVector(Vec2f vec, float scale)
{
Vec2f scaled;
scaled[0] = vec[0] * scale;
scaled[1] = vec[1] * scale;
return scaled;
}

Vec2f subtractVectorsAsFloat(Vec2i first, Vec2i second)
{
// return first - second as float.
Vec2f diff;
diff[0] = first[0] - second[0];
diff[1] = first[1] - second[1];
return diff;
}

Vec2f subtractVectorsAsFloat(Vec2f first, Vec2f second)
{
// return first - second as float.
Vec2f diff;
diff[0] = first[0] - second[0];
diff[1] = first[1] - second[1];
return diff;
}

double dot(Vec2f first, Vec2f second)
{
return first[0] * second[0] + first[1] * second[1];
}

//for all triples
for (size_t i = 0; i < toTry.size() - 1; i++) {

Vec2i center_i = toTry[i].avg;
//NormalizedDiagonal = ((Side1 - Center) + (Side2 - Center));
Vec2i a = toTry[i].p, b = toTry[i].q;
Vec2f normalized_i = normalizedDiagonal(center_i, toTry[i].p, toTry[i].q);

for (size_t j = i + 1; j < toTry.size(); j++) {

Vec2i center_j = toTry[j].avg;
//Se os pontos sao proximos, nao importam
if (areClose(center_i, center_j, 25))
continue;

Vec2f normalized_j = normalizedDiagonal(center_j, toTry[j].p, toTry[j].q);

//test if antiparallel
if (abs(normalized_i[0] - normalized_j[0]) > 0.1 || abs(normalized_i[1] - normalized_j[1] > 0.1))
continue;

// get a vector pointing from center_i to center_j.
Vec2f delta = subtractVectorsAsFloat(center_j, center_i);

//test if do product < 0
float deltaDotDiagonal = dot(delta, normalized_i);
if (deltaDotDiagonal < 0)
continue;

Vec2f deltaProjectedOntoDiagonal = scaleVector(normalized_i, deltaDotDiagonal);

// Subtracting the dot product of delta projected onto normalized_i will leave the component
// of delta which is perpendicular to normalized_i...
Vec2f distanceVec = subtractVectorsAsFloat(deltaProjectedOntoDiagonal, center_j);

// ... the length of which is the distance from center_j
// to the diagonal through center_i.
double distance = getLength(distanceVec);

if(distance < 25) {
}
}