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

Хорошо, у меня возникли проблемы с поиском решения, которое кажется простой проблемой геометрии.

У меня есть список тройных координат, которые образуют квадратный угол.

Между всеми этими тройными координатами я хочу найти пару, которая образует квадрат.

Я считаю, что лучшее, что я могу сделать, чтобы показать это, это показать изображение:

Некоторые тройные координаты в пространстве

  1. и 2. не имеют значения. 3. и 4. это то, что я ищу.

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

Подводя итог, учитывая шесть точек, 2 для диагонали + 4 других точки, как я могу найти, если они образуют квадрат?

obs: две линии, составляющие угол, согласованы, но имеют разный размер.

obs2: линии из разных троек могут не пересекаться

Спасибо за потраченное время, любую помощь и понимание.

Если какой-либо термин, который я использовал, является неправильным или просто трудным для понимания, дайте мне знать, я не являюсь носителем английского языка.

Изменить: код, как он есть.

//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);
line(src, Point(center_i[0], center_i[1]), Point(center_i[0] + 1 * normalized_i[0], center_i[1] + 1 * normalized_i[1]), Scalar(255, 255, 255), 1);

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

Vec2f delta;
delta[0] = center_j[0] - center_i[0]; delta[1] = center_j[1] - center_i[1];
double dd = sqrt(pow((center_i[0] - center_j[0]), 2) + pow((center_i[1] - center_j[1]), 2));
//delta[0] = delta[0] / dd;
//delta[1] = delta[1] / dd;

float dotProduct = normalized_i[0] * delta[0] + normalized_i[1] * delta[1];

//test if do product < 0
if (dotProduct < 0)
continue;

float deltaDotDiagonal = delta[0] * normalized_i[0] + delta[1] * normalized_i[1];
menor_d[0] = delta[0] - deltaDotDiagonal * normalized_i[0];
menor_d[1] = delta[1] - deltaDotDiagonal * normalized_i[1];
dd = sqrt(pow((center_j[0] - menor_d[0]), 2) + pow((center_j[1] - menor_d[1]), 2));

if(dd < 25)
[...]

1

Решение

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

Предполагая первый, способ проверить, образуют ли две тройки квадрат, заключается в следующем. Давайте использовать 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) {
}
}
1

Другие решения

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

Вы просто используете тройные координаты, чтобы определить среднюю точку, и два отрезка, которые выступают из нее (тривиально). Сделайте это для обоих тройных наборов.

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

Вы можете посмотреть код, который я написал для Вычислительная геометрия в C,
в котором подробно обсуждается этот вопрос (глава 1, раздел 5).
код доступен как SegSegInt по ссылкам на этом веб-сайте.

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

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

Удачи!

Рекомендации


  1. нахождение пересечения двух отрезков в 2d (с потенциальными вырождениями), По состоянию на 2014-08-18, <https://math.stackexchange.com/questions/276735/finding-the-intersection-of-two-line-segments-in-2d-with-potential-degeneracies>
1

  1. В паре сегментов назовите один «базовый сегмент», а тот, который получается путем поворота базового сегмента на π / 2 против часовой стрелки, называется «другим сегментом».
  2. Для каждой тройки вычислите угол между базовым сегментом и осью X. Назовите это своим основным углом.
  3. Сортировать тройки по главному углу.
  4. Теперь для каждой тройки с главным углом α любой потенциальный образующий квадрат квадрат имеет главный угол α + π (mod 2π). Это легко найти с помощью бинарного поиска.
  5. Кроме того, для двух кандидатских троек с вершинами а также а» и главные углы α и α + π, угол вектора аа» должно быть α + π / 4.
  6. Наконец, если каждый из четырех сегментов хотя бы |аа ‘|/ √2 долго, у нас есть квадрат.
1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector