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

← →
Омлет © (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 © (16.03.10 14:10) [28]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Попробовал учесть [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;

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

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

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

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