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

← →
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 15:48) [46]

Ага, вижу. Спасибо.

← →
Омлет © (2010-03-16 18:07) [48]

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

Объясни, плз. Не очень понимаю этот магический код..

← →
oldman © (2010-03-16 18:19) [49]

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

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

← →
Jeer © (2010-03-16 20:14) [50]

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

После появления на "сцене" в 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]

← →
Стенка © (2010-03-17 01:35) [53]

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

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

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

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

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

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

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

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

← →
Sha © (2010-03-17 01:44) [54]

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

← →
Германн © (2010-03-17 01:48) [55]

> Sha © (17.03.10 01:44) [54]
>
> Стенка - это мой ник с другого компьютера.
>

И зачем он тебе нужен?

← →
Sha © (2010-03-17 01:51) [56]

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

← →
Sha © (2010-03-17 01:56) [57]

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

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

← →
Германн © (2010-03-17 02:02) [58]

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

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

← →
Sha © (2010-03-17 02:26) [59]

> Германн © (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;

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