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

Question

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

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

Answer 1

• найти центр масс угловых точек: 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 (a-b) <1E-6) </p>

Answer 2

struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 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);
}

Answer 3

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

• это намного более кратко в коде, хотя: -)

  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 в заголовках. Это плохая практика. При сравнении результатов с плавающей запятой всегда следует работать с некоторой верхней границей ошибки.

Answer 4

Расстояние от одной точки до другой 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

Answer 5

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.

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

Свойства прямоугольника в игре

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

Бит Магия

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

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

Answer 6

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

x = B-A, y = C-B, z = D-C и w = A-D

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

Answer 7

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

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

вектор v = B-A вектор u = C-A

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

так что если (v.u == 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 (v.u/|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}

Answer 8

Мы знаем, что две звездные линии перпендикулярны, если произведение их уклонов равно -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;
}

Answer 9

Вот мое предложение по алгоритму для теста с прямоугольником, ориентированным по оси, но в Python.

Идея состоит в том, чтобы захватить первую точку как точку поворота, и чтобы все остальные точки должны были соответствовать одной и той же ширине и высоте, и проверять, чтобы все точки были различны через набор для учета таких случаев, как , 2), (1, 2), (10, 30), (10, 30).

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def is_rectangle(p1, p2, p3, p4) -> bool:
    width = None
    height = None

    # All must be distinct
    if (len(set((p1, p2, p3, p4))) < 4):
        return False

    pivot = p1

    for point in (p2, p3, p4):
        candidate_width = point.x - pivot.x
        candidate_height = point.y - pivot.y

        if (candidate_width != 0):
            if (width is None):
                width = candidate_width
            elif (width != candidate_width):
                return False

        if (candidate_height != 0):
            if (height is None):
                height = candidate_height
            elif (height != candidate_height):
                return False

    return width is not None and height is not None

# Some Examples
print(is_rectangle(Point(10, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(100, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 10), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 30), Point(20, 30), Point(10, 30), Point(20, 30)))
print(is_rectangle(Point(10, 30), Point(10, 30), Point(10, 30), Point(10, 30)))
print(is_rectangle(Point(1, 2), Point(10, 30), Point(1, 2), Point(10, 30)))
print(is_rectangle(Point(10, 50), Point(80, 50), Point(10, 40), Point(80, 40)))

Answer 10

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

def con_rec(a,b,c,d): 
        d1 = a.distanceFromPoint(b)
        d2 = b.distanceFromPoint(c)
        d3 = c.distanceFromPoint(d)
        d4 = d.distanceFromPoint(a)
        d5 = d.distanceFromPoint(b)
        d6 = a.distanceFromPoint(c)
        lst = [d1,d2,d3,d4,d5,d6] # list of all combinations 
        of point to point distances
        if min(lst) * math.sqrt(2) == max(lst): # this confirms a square, not a rectangle
            return False
        z = set(lst) # set of unique values in ck
        if len(lst) == 3: # there should be three values, length, width, diagonal, if a 
        4th, it's not a rectangle
            return True
        else: # not a rectangle
            return False