Проверка на выпуклость четырехугольника

← →
Омлет © (2010-03-15 13:58) [0]

Нужно проверить четырехугольник на выпуклость. Решил через условие пересечения диагоналей: если диагонали пересекаются, значит выпуклый. Можно ли упростить или по-другому, более оптимально решить?

type TAbsPoints = array[0..3] of TPoint; TLine = record A, B: TPoint; end; function IsConvexQuadrangle(const Pts: TAbsPoints): Boolean; function PtRightLine(const L: TLine; P: TPoint): Boolean; begin Result := (L.A.X - L.B.X)*(P.Y - L.B.Y) > (L.A.Y - L.B.Y)*(P.X - L.B.X); end; var L1, L2 : TLine; begin L1.A := Pts[0]; L1.B := Pts[2]; L2.A := Pts[1]; L2.B := Pts[3]; Result := // Проверка пересечения проекций (Max(L2.A.X, L2.B.X) >= Min(L1.A.X, L1.B.X)) and (Max(L1.A.X, L1.B.X) >= Min(L2.A.X, L2.B.X)) and (Max(L2.A.Y, L2.B.Y) >= Min(L1.A.Y, L1.B.Y)) and (Max(L1.A.Y, L1.B.Y) >= Min(L2.A.Y, L2.B.Y)) and // Проверка, что точки отрезка лежат по разные стороны прямой, образуемой другим отрезком (PtRightLine(L1, L2.A) <> PtRightLine(L1, L2.B)) and (PtRightLine(L2, L1.A) <> PtRightLine(L2, L1.B)); end;

← →
oldman © (2010-03-15 14:02) [1]

Все углы >=90 градусов

Вряд ли это проще, чем [0]

← →
Putnik © (2010-03-15 14:06) [2]

2 oldman
А параллелограмм?

← →
oldman © (2010-03-15 14:08) [3]

Туплю...

Может это поможет:
http://delphid.dax.ru/www/exampl34.htm

← →
Kerk © (2010-03-15 14:11) [4]

Противолежащие углы нужно сравнивать. Должно быть соответствие
угол2 = 2*pi - угол1

← →
Kerk © (2010-03-15 14:12) [5]

А, не. Тоже туплю :-)

← →
oldman © (2010-03-15 14:15) [6]

Кажись в выпуклом нет углов >180
А если есть - то невыпуклый

← →
TUser © (2010-03-15 14:16) [7]

Имхо, берем 4 вектора, (AB, BC, CD, DA). Произведения ABxBC, BCxCD, CDxDA, DAxAB должны быть сонаправлены.

← →
Ega23 © (2010-03-15 14:18) [8]

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

← →
oldman © (2010-03-15 14:22) [9]

> Ega23 © (15.03.10 14:18) [8]

Для невыпуклого тоже сработает

← →
oldman © (2010-03-15 14:28) [10]

> Дальше показать, что любая прямая имеет не более одной точки
> пересечения с любой из оставшихся трёх.

А как могут две несовпадающие прямые иметь более одной точки пересечения?
:)))

← →
Омлет © (2010-03-15 14:30) [11]

> TUser © (15.03.10 14:16) [7]

Хм, а это вариант.. Не знаю, быстрее ли работает, но строчек кода меньше )

function IsConvexQuadrangle1(const A, B, C, D: TPoint): Boolean; begin Result := (A.X - B.X)*(C.Y - B.Y) > (A.Y - B.Y)*(C.X - B.X); Result := (Result = ((B.X - C.X)*(D.Y - C.Y) > (B.Y - C.Y)*(D.X - C.X))) and (Result = ((C.X - D.X)*(A.Y - D.Y) > (C.Y - D.Y)*(A.X - D.X))) and (Result = ((D.X - A.X)*(B.Y - A.Y) > (D.Y - A.Y)*(B.X - A.X))); end;

← →
Ega23 © (2010-03-15 15:08) [12]

> Для невыпуклого тоже сработает

Согласен. Не подумал.
Ega23 © (15.03.10 14:18) [8] - считать ошибкой.

← →
Anatoly Podgoretsky © (2010-03-15 15:18) [13]

> Ega23 (15.03.2010 15:08:12) [12]

Зачем Ega23 считать ошибкой.

← →
@!!ex © (2010-03-15 15:31) [14]

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

← →
Smile (2010-03-15 15:33) [15]

> Ega23 © (15.03.10 14:18) [8]
> Каждая грань - уравнение прямой.

Четырехугольник не имеет граней, его стороны участки прямой :)

Проверка на выпуклость: все внутренние углы меньше 180 градусов.
))

← →
Омлет © (2010-03-15 15:39) [16]

> @!!ex © (15.03.10 15:31) [14]

Не понял. Это то же, что и TUser © [7]?

← →
Ega23 © (2010-03-15 15:41) [17]

> Anatoly Podgoretsky © (15.03.10 15:18) [13]
>
> Зачем Ega23 считать ошибкой.

Потому что Ega23 - мутант с DataSet-ом, чихающий строго 7 раз.

← →
@!!ex © (2010-03-15 16:59) [18]

> [16] Омлет © (15.03.10 15:39)

Векторное умножение и подстановка коэфициентов в уравнение - не одно и тоже.
Суть одна и таже, а вычисления разные.

← →
Sha © (2010-03-15 17:05) [19]

Выпуклый, если вершины 2 и 4 лежат по разные стороны от диагонали, проведенной через вершины 1 и 3.

← →
Sha © (2010-03-15 17:06) [20]

И если вершины 1 и 3 лежат по разные стороны от диагонали, проведенной через вершины 2 и 4.

← →
12 © (2010-03-15 17:47) [21]

Сумма углов выпуклого n-угольника равна 180° (n – 2).

← →
Dimka Maslov © (2010-03-15 20:26) [22]

Как-то так:

1. Выбираем любую вершину в качестве полюса.
2. Для каждых двух соседних вершин вычисляем площадь треугольника, образованного этими вершинами и полюсом. (через определитель матрицы - написано у Корнов)
3. Все площади должны иметь одинаковый знак (чтобы не заморачиваться с определением направления обхода).

← →
oldman © (2010-03-16 08:54) [23]

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

Кто придумает еще более извращенный способ кроме описанного в [0]. Проверка диагоналей на пересечение, имхо, самый простой.

← →
oldman © (2010-03-16 09:16) [24]

Если емеем координаты углов (x1,y1),(x2,y2),(x3,y3),(x4,y4), то координата х точки пересечения находится (в формуле могу ошибиться, вывел за 10 минут карандашем на столе)

X=((y1-y2)/(x1-x2)-(y3-y4)/(x3-x4))/( y3-y1+x1(y1-y2)/(x1-x2)-x3(y3-y4)/(x3-x4))

если это выражение истинно, точка пересечения есть.

← →
oldman © (2010-03-16 11:47) [25]

Так, наверное, вернее

x = (y4-x4(y3-y4)/(x3-x4)-y2+x2(y1-y2)/(x1-x2)) / ((y1-y2)/(x1-x2)-(y3-y4)/(x3-x4))
y = x(y1-y2)/(x1-x2)+y2-x2(y1-y2)/(x1-x2)

← →
Sha © (2010-03-16 13:42) [26]

Омлет © (15.03.10 14:30) [11]

Жаль, что этот код работает неоднозначно, если одна из вершин лежит на диагонали.
В зависимости от направления перечисления вершин для одного и того же
четырехугольника можно получить разные ответы, например:
00, 11, 22, 20
00, 20. 22, 11

← →
oldman © (2010-03-16 13:44) [27]

> если одна из вершин лежит на диагонали.

Чего? Это треугольник получится.

← →
Sha © (2010-03-16 14:10) [28]

Ну да, а че низя?

← →
Sha © (2010-03-16 14:14) [29]

> oldman ©

кстати, что делать если в [24] или [25] произойдет деление на 0?

← →
oldman © (2010-03-16 14:14) [30]

> Sha © (16.03.10 14:10) [28]

А если две вершины лежат на диагонали, то это отрезок.
А че, низя?
:)

Пардон, в отрезке все 4 вершины лежат на диагонали...

← →
oldman © (2010-03-16 14:15) [31]

> Sha © (16.03.10 14:14) [29]

Значит такой точки не существует, диагонали не пересекаются...

← →
oldman © (2010-03-16 14:17) [32]

При решении системы уравнений диагоналей может случится 0х=0.
Вроде правильное уравнение, но х=0/0, пересечения нет.

← →
Sha © (2010-03-16 14:20) [33]

> Значит такой точки не существует, диагонали не пересекаются...

Еще как пересекаются:
01 12 21 10

← →
oldman © (2010-03-16 14:24) [34]

Аааааа....
Я ошибся....

(x1,y1),(x2,y2) - одна диагональ
(x3,y3),(x4,y4) - друга диагональ

← →
oldman © (2010-03-16 14:27) [35]

Как я выводил:

Уравнение прямой по двум точкам.
Получаем два уравнения диагоналей.
Приравниваем их. Выводим х.
Может ошибся в цифрах-буквах.

← →
Alx2 © (2010-03-16 14:40) [36]

А почему через скалярное произведение сторон не нравится (как в[7])? Вроде проще некуда.

← →
Sha © (2010-03-16 14:43) [37]

> oldman © (16.03.10 14:27) [35]
> Выводим х.

Проблема в том, что формулы для получения координат точки пересечения содержат операцию деления. Поэтому потребуется ветвление для случая нулевого и ненулевого значения знаменателя. Нулевое значение, в свою очередь, требует дополнительного анализа. Все не так просто.

← →
Sha © (2010-03-16 14:45) [38]

> Alx2 © (16.03.10 14:40) [36]
> А почему через скалярное произведение сторон не нравится (как в[7])? Вроде проще некуда.

Ну так [11] и есть [7].
Все бы хорошо, если бы не [26].

← →
Sha © (2010-03-16 14:52) [39]

Попробовал учесть [26].
function ShaIsSameDirection(const t0, t1, t2: TPoint; var dir: integer): boolean; var s: integer; begin; s:=(t1.X-t0.X) * (t2.Y-t0.Y) - (t2.X-t0.X) * (t1.Y-t0.Y); if s=0 then Result:=true else begin; s:=s or MaxInt; Result:=(s xor dir)<>$80000000; dir:=s; end; end; function ShaIsConvexQuadrangle(const p0, p1, p2, p3: TPoint): boolean; var dir: integer; begin; dir:=0; Result:=ShaIsSameDirection(p0, p1, p2, dir) and ShaIsSameDirection(p1, p2, p3, dir) and ShaIsSameDirection(p2, p3, p0, dir) and ShaIsSameDirection(p3, p0, p1, dir); end;

← →
Alx2 © (2010-03-16 14:53) [40]

>Sha © (16.03.10 14:45) [38]

1. Направление обхода фиксируем.
2. Критерий невыпуклости - "смена дрейфа" (то есть смена знака произведения) при обходе.

Насчет того, что вершина может лежать на диагонали ([26]) - вроде не мешает. Честно говоря, вообще не понимаю, что мешает.

← →
Alx2 © (2010-03-16 14:57) [41]

Вдогонку к [40]:

Т.е. типа такого:
A,B,C,D - вершины

isConvex := ((B-A)*(C-B) >=0) = ((C-B)*(D-C)>=0) = ((D-C)*(A-D)>=0) = ((A-D)*(B-A) >=0)

← →
Sha © (2010-03-16 15:02) [42]

> Alx2 © (16.03.10 14:53) [40]
> Честно говоря, вообще не понимаю, что мешает.

В [26] пример четырехугольника приведен.
Который в соответствии с алгоритмом [11] одновременно и выпуклый и невыпуклый.

> Alx2 © (16.03.10 14:57) [41]

Та же самая неоднозначность.

← →
Alx2 © (2010-03-16 15:23) [43]

>Sha © (16.03.10 15:02) [42]

Сорри, я ошибся. Подразумевал векторное произведение, а не скалярное.

Пусть (в 3D) точка A = [ax,ay,0] B = [bx,by,0]

Векторное будет: AxB = [0,0,ax*by-ay*bx]

Используем только третью координату: ax*by-ay*bx

Тогда справедливо:
isConvex := ((B-A)*(C-B) >=0) = ((C-B)*(D-C)>=0) = ((D-C)*(A-D)>=0) = ((A-D)*(B-A) >=0)

где операция произведения определена как [ax,ay] x [bx,by] = ax*by-ay*bx

← →
Sha © (2010-03-16 15:30) [44]

> Alx2 © (16.03.10 15:23) [43]
>Подразумевал векторное произведение, а не скалярное.

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

← →
Alx2 © (2010-03-16 15:43) [45]

>Sha © (16.03.10 15:30) [44]

А. Все. Дошло. Спасибо :)

Я неверно записал условие, которое должно выполняться:
"все произведения >=0 " or "все произведения <= 0".

← →
Sha © (2010-03-16 15:48) [46]

> Alx2 © (16.03.10 15:43) [45]
> "все произведения >=0 " or "все произведения <= 0".

а это и есть [39]

← →
Alx2 © (2010-03-16 15:51) [47]

> Sha © (16.03.10 14:43) [37]

Всегда думал, что математика наука точная.
То есть, если система уравнений имеет решение, оно выводится подстановкой.
Блин!!!

> Всегда думал, что математика наука точная.

После появления на "сцене" в 1921 г. Лютфи Алескерзаде ( более известного, как Lotfi Asker Zadeh ) и его основополагающей работы в 1965 г. по созданию теории нечетких множеств - математика "перестала" быть точной наукой :)

← →
ald (2010-03-16 20:31) [51]

> oldman © (16.03.10 18:19) [49]
> > Sha © (16.03.10 14:43) [37]
> Всегда думал, что математика наука точная.
> То есть, если система уравнений имеет решение, оно выводится
> подстановкой.
> Блин!!!
дифференциальность конечно путает много чего в плане точности..)

← →
ald (2010-03-16 20:32) [52]

> Омлет © (16.03.10 18:07) [48]
> Объясни, плз. Не очень понимаю этот магический код..

Обходим четырехугольник по периметру.

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

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

В начале алгоритма устанавливаем dir=0, т.е. знак площадей (т.е. направление векторного произведения) неопределен.

Далее:
если встретим треугольник с нулевой площадью, не меняем значение dir,
если встретим треугольник с положительной площадью, установим dir=MaxInt,
если встретим треугольник с положительной площадью, установим dir=-1.

Если окажется, что очередной треугольник
имеет положительную площадь, а запомнено значение dir=-1,
или имеет отрицательную площадь, а запомнено значение dir=MaxInt,
то возвращаем false, т.к. обнаружено изменение знака поворота.
Иначе возвращаем true.

В этом виде алгоритм не годится для 5ти- и более -угольников, т.к. можно запросто перекрутить в одну стророну. Пример: звезда.

Стенка - это мой ник с другого компьютера.

Copy/Paste Error:
если встретим треугольник с отрицательной площадью, установим dir=-1.

> Германн © (17.03.10 01:48) [55]
> И зачем он тебе нужен?

Так сложилось исторически,
сообщения с этого компа отправляю не только я,
ник запомнен в куках.

> Sha © (17.03.10 01:56) [57]
>
> > Германн © (17.03.10 01:48) [55]
> > И зачем он тебе нужен?
>
> Так сложилось исторически,
> сообщения с этого компа отправляю не только я,
> ник запомнен в куках.
>

Тем более.
Накой нам "стенка", когда мы не знаем кто это?
А куки с чужого компа нужно удалять после использования.

> Германн © (17.03.10 02:02) [58]

Правила форума запрещают преднамеренное использование разных ников в одной ветке.
Поэтому своим постом [54] я снял возможное недоразумение.

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

Однако, мы немного отвлеклись от темы.

> Стенка © (17.03.10 01:35) [53]

Спасибо!

А то сначала не понял, в чём хитрость
s:=s or MaxInt;
Result:=(s xor dir)<>$80000000;

Похоже, пока что это самый оптимальный и правильный вариант..

> Sha © (16.03.10 14:52) [39]

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

function IsConvexQuadrangle1(const p0, p1, p2, p3: TPoint): boolean; function ShaIsSameDirection(const A,B,C: TPoint; var Dir: integer; var LastZero: Boolean): boolean; var S : Integer; begin; S := (A.X - B.X)*(C.Y - B.Y) - (A.Y - B.Y)*(C.X - B.X); if S <> 0 then begin Result := ((S > 0) and (Dir > 0)) or ((S < 0) and (Dir < 0)) or (Dir = 0); Dir := S; LastZero := False; end else begin Result := (not LastZero); LastZero := True; end; end; var Dir : Integer; LastZero : Boolean; begin; Dir := 0; LastZero := False; Result := ShaIsSameDirection(p0, p2, p1, Dir, LastZero) and ShaIsSameDirection(p1, p3, p2, Dir, LastZero) and ShaIsSameDirection(p2, p0, p3, Dir, LastZero) and ShaIsSameDirection(p3, p1, p0, Dir, LastZero); end;

> Омлет © (19.03.10 07:53) [61]
> Сегодня проверил - код не работает.

Было бы интересно узнать, как это проявляется и на каких исходных данных.

> Sha ©

Всегда возвращает true.

var A,B,C,D: TPoint; procedure TForm1.FormCreate(Sender: TObject); begin A := Point(10, 10); B := Point(90, 90); C := Point(90, 10); D := Point(10, 90); if ShaIsConvexQuadrangle(A,B,C,D) then Caption := "Convex." else Caption := "Not convex."; end; procedure TForm1.FormPaint(Sender: TObject); begin Canvas.Polygon([A,B,C,D]); end;

И варнинг Comparison always evaluates to True на строке
Result:=(s xor dir)<>$80000000;

Понятно.

Это исправляется так
Result:=(s xor dir)<>integer($80000000);

Или лучше так:
function ShaIsSameDirection(const t0, t1, t2: TPoint; var dir: integer): boolean; const MinInt=-1 xor MaxInt; var s: integer; begin; s:=(t1.X-t0.X) * (t2.Y-t0.Y) - (t2.X-t0.X) * (t1.Y-t0.Y); if s=0 then Result:=true else begin; s:=s or MaxInt; Result:=(s xor dir)<>MinInt; dir:=s; end; end;

А.. точно ))
Но я [61] оставлю, так более читабельно и проверка на случай всех точек на одной прямой.

> LastZero - для отбраковки варианта, где все четыре точки на одной прямой.

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

function ShaIsConvexQuadrangle(const p0, p1, p2, p3: TPoint): boolean; var dir: integer; begin; dir:=0; Result:=ShaIsSameDirection(p0, p1, p2, dir) and ShaIsSameDirection(p1, p2, p3, dir) and ShaIsSameDirection(p2, p3, p0, dir) and ShaIsSameDirection(p3, p0, p1, dir) and (dir<>0); end;

Проверка на выпуклость четырехугольника Найти похожие ветки