Может кто-нибудь, пожалуйста, покажите мне в псевдокоде C-стиля, как написать функцию (представить точки, которые вам нравятся), которая возвращает true, если 4-балльные (аргументы функции) образуют прямоугольник, а false в противном случае?
Я придумал решение, которое сначала пытается найти 2 разных пары точек с равным x-значением, а затем это для оси y. Но код довольно длинный. Просто любопытно посмотреть, что другие придумали.
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)
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);
}
это намного более сжато в коде, но: -)
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 в заголовках. Это плохая практика. Они есть не по какой-то причине. Всегда нужно работать с некоторая верхняя граница ошибки при сравнении результатов с плавающей запятой.)
Если точки A, B, C и D, и вы знаете порядок, то вы вычисляете векторы:
x = B-A, y = C-B, z = D-C и w = A-D
Затем возьмем точечные произведения (x dot y), (y dot z), (z dot w) и (w dot x). Если они все равны нулю, у вас есть прямоугольник.
Расстояние от одной точки до другой 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 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
Мы знаем, что две звездные линии перпендикулярны, если произведение их наклонов равно -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 точками точек, а затем посмотрите, соответствуют ли 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}