найти, если 4 точки на плоскости образуют прямоугольник?

Может кто-нибудь, пожалуйста, покажите мне в псевдокоде C-стиля, как написать функцию (представить точки, которые вам нравятся), который возвращает true, если 4-балльные (аргументы функции) образуют прямоугольник, а false в противном случае?

Я придумал решение, которое сначала пытается найти 2 разных пары точек с равным x-значением, а затем это для оси y. Но код довольно длинный. Просто любопытно посмотреть, что другие придумали.

  • найти центр масс угловых точек: cx = (x1 + x2 + x3 + x4) / 4, cy = (y1 + y2 + y3 + y4) / 4
  • если квадрат расстояний от центра масс до всех 4 углов равен
bool isRectangle(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { double cx,cy; double dd1,dd2,dd3,dd4; cx=(x1+x2+x3+x4)/4; cy=(y1+y2+y3+y4)/4; dd1=sqr(cx-x1)+sqr(cy-y1); dd2=sqr(cx-x2)+sqr(cy-y2); dd3=sqr(cx-x3)+sqr(cy-y3); dd4=sqr(cx-x4)+sqr(cy-y4); return dd1==dd2 && dd1==dd3 && dd1==dd4; } 

(Конечно, на практике тестирование для равенства двух чисел с плавающей запятой a и b должно выполняться с конечной точностью: например, abs (ab) <1E-6)

 struct point { int x, y; } // tests if angle abc is a right angle int IsOrthogonal(point a, point b, point c) { return (bx - ax) * (bx - cx) + (by - ay) * (by - cy) == 0; } int IsRectangle(point a, point b, point c, point d) { return IsOrthogonal(a, b, c) && IsOrthogonal(b, c, d) && IsOrthogonal(c, d, a); } 

Если заказ неизвестен заранее, нам нужно немного более сложная проверка:

 int IsRectangleAnyOrder(point a, point b, point c, point d) { return IsRectangle(a, b, c, d) || IsRectangle(b, c, a, d) || IsRectangle(c, a, b, d); } 
  • перевести четырехугольник так, чтобы одна из его вершин теперь лежала в начале координат
  • три оставшиеся точки образуют три вектора из начала координат
  • один из них должен представлять диагональ
  • два других должны представлять стороны
  • по правилу параллелограмма, если стороны образуют диагональ, мы имеем параллелограмм
  • если стороны образуют прямой угол, это параллелограмм с прямым углом
  • противоположные углы параллелограмма равны
  • последовательные углы параллелограмма являются дополнительными
  • поэтому все углы являются прямыми углами
  • это прямоугольник
  • это намного более сжато в коде, хотя 🙂

     static bool IsRectangle( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1; return (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) || (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) || (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4); } 
  • (Если вы хотите, чтобы он работал с значениями с плавающей запятой, пожалуйста, не просто слепо заменяйте объявления int в заголовках. Это плохая практика. Они есть по какой-то причине. Всегда нужно работать с некоторой верхней границей ошибки при сравнении результатов с плавающей запятой).

Расстояние от одной точки до другой 3 должно составлять правый треугольник:

 |  / / |
 |  / / |
 |  / / |
 | / ___ / ___ |
 d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) if d1^2 == d2^2 + d3^2 then it's a rectangle 

Упрощая:

 d1 = (x2-x1)^2 + (y2-y1)^2 d2 = (x3-x1)^2 + (y3-y1)^2 d3 = (x4-x1)^2 + (y4-y1)^2 if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true 

Если точки A, B, C & D и вы знаете порядок, то вы вычисляете векторы:

x = BA, y = CB, z = DC и w = AD

Затем возьмем точечные произведения (x dot y), (y dot z), (z dot w) и (w dot x). Если они все равны нулю, у вас есть прямоугольник.

Мы знаем, что две звездные линии перпендикулярны, если произведение их наклонов равно -1, поскольку дана плоскость, мы можем найти наклоны трех последовательных линий, а затем умножить их, чтобы проверить, действительно ли они перпендикулярны или нет. Предположим, что у нас есть прямые L1, L2, L3. Теперь, если L1 перпендикулярно L2 и L2 перпендикулярно L3, то это прямоугольник и наклон m (L1) * m (L2) = – 1 и m (L2) * m (L3) = -1, то это подразумевает, что это прямоугольник. Код выглядит следующим образом

 bool isRectangle(double x1,double y1, double x2,double y2, double x3,double y3, double x4,double y4){ double m1,m2,m3; m1 = (y2-y1)/(x2-x1); m2 = (y2-y3)/(x2-x3); m3 = (y4-y3)/(x4-x3); if((m1*m2)==-1 && (m2*m3)==-1) return true; else return false; } 

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

Если у вас есть точки [Ax, Ay] [Bx, By] [Cx, Cy] [Dx, Dy]

вектор v = вектор BA u = CA

v (точка) U / | v || ц | == cos (тета)

поэтому, если (vu == 0), там есть пара перпендикулярных линий.

На самом деле я не знаю программирования на C, но для вас есть «мета-программирование»: P

 if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral} var dot = (v1*u1 + v2*u2); //computes the "top half" of (vu/|v||u|) if (dot == 0) { //potentially a rectangle if true if (Dy==By && Dx==Cx){ is a rectangle } else if (Dx==Bx && Dy==Cy){ is a rectangle } } else {not a rectangle} 

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

Итак, вычислительно, вам нужно четыре вычитания, чтобы получить v и u, два умножения, одно дополнение, и вы должны проверить где-то между 1 и 7 равенствами.

возможно, я это делаю, но я смутно помню, как читал где-то, что вычитания и умножения являются «более быстрыми» вычислениями. Я предполагаю, что объявление переменных / массивов и установка их значений также довольно быстро?

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

Изменить: попробуйте это на основе моего комментария ниже:

 A = [a1,a2]; B = [b1,b2]; C = [c1,c2]; D = [d1,d2]; u = (b1-a1,b2-a2); v = (c1-a1,c2-a2); if ( u==0 || v==0 || A==D || u==v) {!rectangle} // get the obvious out of the way var dot = u1*v1 + u2*v2; var pgram = [a1+u1+v1,a2+u2+v2] if (dot == 0 && pgram == D) {rectangle} // will be true 50% of the time if rectangle else if (pgram == D) { w = [d1-a1,d2-a2]; if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance else {!rectangle} } else {!rectangle} 
 1. Find all possible distances between given 4 points. (we will have 6 distances) 2. XOR all distances found in step #1 3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle). 4. Now, to differentiate between square and rectangle a. Find the largest distance out of 4 distances found in step #1. b. Check if the largest distance / Math.sqrt (2) is equal to any other distance. c. If answer is No, then given four points form a rectangle otherwise they form a square. 

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

Прямоугольные свойства в игре

  1. Противоположные стороны и диагонали прямоугольника имеют одинаковую длину.
  2. Если диагональная длина прямоугольника равна sqrt (2) раз любой длины, то прямоугольник является квадратом.

Бит Магия

  1. XORing равные значения возвращают 0.

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

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

input 4 points A, B, C, D;

if(A, B, C, D are the same points), exit;// not a rectangle;

else form 3 vectors, AB, AC, AD, verify(AB=AC+AD || AC=AB+AD || AD=AB+AC), \\if one of them satisfied, this is a parallelogram;

2. проверить правильный угол

through the last step, we could find which two points are the adjacent points of A;

We need to find out if angle A is a right angle, if it is, then rectangle.

Я не знал, есть ли ошибки. Пожалуйста, выясните это, если есть.

  • Как сделать насыщающее дополнение в C?
  • Как закодировать URL-сокращение?
  • Загорается игровой алгоритм
  • Генерация сетки из точек с координатами x, y и z
  • Сортировка четырех точек по часовой стрелке
  • Эффективный алгоритм сжатия коротких текстовых строк
  • Быстрый алгоритм быстрого поиска диапазона, в котором содержится номер в наборе диапазонов?
  • Обнаружение, если два изображения визуально идентичны
  • математика / алгоритм Fit изображение на экран сохранить соотношение сторон
  • Алгоритм анаграммы в java
  • Найдите пути между двумя заданными узлами?
  • Interesting Posts

    mysql «Где не в», используя два столбца

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

    Как исправить «для начального объявления цикла, используемого вне режима C99» Ошибка GCC?

    Как выборочно загружать изображения в Chromium?

    Geo Fencing – точка внутри / снаружи многоугольника

    Почему Java не поддерживает unsigned ints?

    AppCompatActivity.onCreate можно вызывать только из одной и той же группы библиотек

    XP CD не предлагает вариант ремонта

    Передача имени переменной в функцию из R

    Box Shadow в строке таблицы, не отображающейся в некоторых браузерах

    Как автоматически удалить приложение Android с устройства перед установкой новой версии

    Как я могу указать явный заказ ScriptBundle?

    Копирование файлов в папку приложения во время компиляции

    WiFi-карта не была обнаружена Windows впервые после перезапуска с Ubuntu в режиме двойной загрузки

    Как инициализировать массив до 0 в C?

    Давайте будем гением компьютера.