Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2010.08.27;
Скачать: [xml.tar.bz2];

Вниз

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

 
Омлет ©   (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;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.54 MB
Время: 0.06 c
4-1237964752
Alex1234
2009-03-25 10:05
2010.08.27
Выполнить настройку COM-порта


9-1180439487
gray_falcon
2007-05-29 15:51
2010.08.27
Как реализовать графику на 2D движке


15-1266186779
OneYoungMan
2010-02-15 01:32
2010.08.27
Очистка cd и dvd дисков...


2-1269519135
Влад
2010-03-25 15:12
2010.08.27
ActiveX


15-1268329391
Ega23
2010-03-11 20:43
2010.08.27
Ололо предлагают послать на Евровидение





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский