Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

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

 
Омлет ©   (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]) - вроде не мешает. Честно говоря, вообще не понимаю, что мешает.



Страницы: 1 2 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.56 MB
Время: 0.059 c
15-1272852692
Tirael
2010-05-03 06:11
2010.08.27
как скрыть лишние интерфейсы


2-1269669606
NBAH1990
2010-03-27 09:00
2010.08.27
Помогите разобраться с компонентом TsListView


15-1270124231
Славян
2010-04-01 16:17
2010.08.27
Нужна прога,которая берёт случайный набор слов и фраз(заданное на


15-1264973402
Юрий
2010-02-01 00:30
2010.08.27
С днем рождения ! 1 февраля 2010 понедельник


15-1272622758
JohnKorsh
2010-04-30 14:19
2010.08.27
Как определить, какая программа использует файл.