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

Question

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

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

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

64

c algorithm geometry

Источник

user277770 20 фев '10 в 19:01

10 ответов

Другие вопросы по тегам c algorithm geometry

user136452 20 фев '10 в 22:42 2010-02-20 22:42 · Answer 1 · 2010-02-20 22:42

найти центр масс угловых точек: 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)

user276994 20 фев '10 в 19:12 2010-02-20 19:12 · Answer 2 · 2010-02-20 19:12

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);
}

user5644696 08 июл '18 в 23:22 2018-07-08 23:22 · Answer 3 · 2018-07-08 23:22

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.

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

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

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

Немного магии

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

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

user276068 28 фев '10 в 02:13 2010-02-28 02:13 · Answer 4 · 2010-02-28 02:13

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

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

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

user237761 21 фев '10 в 08:16 2010-02-21 08:16 · Answer 5 · 2010-02-21 08:16

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

user5876 20 фев '10 в 23:04 2010-02-20 23:04 · Answer 6 · 2010-02-20 23:04

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

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

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

5

Источник

user5876 20 фев '10 в 23:04

user278457 22 фев '10 в 14:23 2010-02-22 14:23 · Answer 7 · 2010-02-22 14:23

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

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

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

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

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

Я на самом деле не знаю, Си-программирование, но вот несколько "мета" программирования для вас: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}

user191799 21 фев '10 в 04:54 2010-02-21 04:54 · Answer 8 · 2010-02-21 04:54

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

user10625697 08 ноя '18 в 20:24 2018-11-08 20:24 · Answer 9 · 2018-11-08 20:24

Недавно я столкнулся с аналогичной проблемой, но в 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

user9023700 05 авг '18 в 03:48 2018-08-05 03:48 · Answer 10 · 2018-08-05 03:48

Как насчет проверки того, что эти 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.

Я не знал, существуют ли ошибки. Пожалуйста, разберись, если есть.

user1765893 28 май '19 в 21:06 2019-05-28 21:06 · Answer 11 · 2019-05-28 21:06

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

Идея состоит в том, чтобы взять первую точку в качестве точки поворота, и что все остальные точки должны соответствовать той же ширине и высоте, и проверяет, что все точки различны, через набор, чтобы учесть такие случаи, как (1, 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)))