Геометрия (задачки)

[Igors]

Добрый день

Задачки простые, но встречаются в 2/3D графике часто. Тема по образцу "задачки" - пополняйте. Для начала

1) Есть 4-угольник на плоскости (напр QPointF[4]). Определить является ли он выпуклым

2) Есть 4-угольник на плоскости. Как лучше разбить его на 2 треугольника?

[panAlexey]

2) Есть 4-угольник на плоскости. Как лучше разбить его на 2 треугольника?

А что значит "лучше"?

[m_ax]

1) Задать произвольное направление обхода контура (1->2->3->4).
2) В каждой точке посчитать знак векторного произведения "смыкающихся векторов".
3) Если в какой либо точке знак будет отличен от других - то треугольник вогнутый.

По второй задаче:
1) Определить вогнутый ли треугольник. Если нет, то не понятен критерий "лучшести"..
2) Если вогнутый, найти ту точку (где знак другой, см. задачу 1) и резать от этой точки до противоположной (т.е. той, где смыкаются другие два вектора)..


 

[Igors]

1) Задать произвольное направление обхода контура (1->2->3->4).
2) В каждой точке посчитать знак векторного произведения "смыкающихся векторов".
3) Если в какой либо точке знак будет отличен от других - то треугольник вогнутый.

По существу - правильно, формально нет. Возможны 2 знака плюс и 2 минус

А что значит "лучше"?

1)Если нет, то не понятен критерий "лучшести"..

Вот этот критерий и надо сформулировать, т.е. в этом и вопрос

[Igors]

Вот еще - совсем простенько, но в "художественном" изложении (m_ax, здесь просьба воздержаться)

3) "Ехала машина темным лесом". Путь задан в виде последовательности точек, напр QVector <QPointF>. Для любой точки  (но не первой и не последней) определить

- машина едет вперед или дает задний ход
- положение руля: (влево, вправо, по центру)

[Torvald]

Сначала нужно условиться, каким образом машина меняет ход вперед/назад. Пусть это будет участок ломаной, который образует острый угол
Для определения направления в точке p (из n точек):
1. Запоминаем текущее направление (машина стартует передним или заднем ходом)
2. проходимся по точкам от 1 до p
2.2 если угол между векторами (i-1), i, и i, (i+1) острый - значит инвертируем текущее направление
3. когда доходим до точки p - имеем текущее направление в данной точке

Сложность такого алгоритма O(p), где p находится в диапазоне [1, n)
По моему уменьшить сложность нельзя, так как текущее состояние машины зависит от предыдущего. Однако можно узнать за время O(1) сменила ли машина направление в данной точки

Для определения положения руля:
1. Вычисляем синус угла между векторами (i-1), i и (i-1), (i+1)
1.1 если синус равен нулю - положение руля прямое
1.2 если синус меньше нуля - руль повернут вправо, если едем вперед и влево, если едем назад
1.3 если синус больше нуля - влево, если вперед и вправо, если назад
2. но если это переломный момент, то есть в данной точке машина меняет направление (назад/вперед), то пункты 1.2 и 1.3 "инвертируются"

Вроде так  

[Igors]

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

Да, или др словами - шаг достаточно мал, иначе смена направления неотличима от (резкого) поворота

2.2 если угол между векторами (i-1), i, и i, (i+1) острый -

1. Вычисляем синус угла между векторами (i-1), i и (i-1), (i+1)

А как эти углы посчитать? И нужны ли сами углы (можно ли обойтись знаком) ?

[Torvald]

А как эти углы посчитать? И нужны ли сами углы (можно ли обойтись знаком) ?

Ну да, как и во втором случае, достаточно обойтись косинусом. Если знак положительный - сменили направление.

a = p[j]-p[j-1]
b = p[j+1]-p[j-1]
cos(a, b) = (a.x*b.x+a.y*b.y) / (sqrt(a.x*a.x+a.y*a.y)+sqrt(b.x*b.x+b.y*b.y))

если знаменатель равен нулю, значит точки совпадают

--------------------------------
Кстати положение третьей точки можно узнать через уравнение прямой по двум точкам:
(p.x-p1.x)/(p2.x-p1.x) = (p.y-p1.y)/(p2.y-p1.y)

Для определения направления движения машины (назад/вперед) можно составить уравнение прямой перпендикулярной к отрезку (p[j], p[j-1]) и проходящую через точку p[j] и узнать положение точки p[j+1] относительно этой прямой.

Для определения положения руля можно узнать положение точки p[j+1] относительно прямой построенной по точкам p[j], p[j-1]

Вроде как в этом случае вычислений меньше

PS не знаю как экранировать тэгирование

Код:

[i]

поэтому вместо i использую j  

[Igors]

Ну да, как и во втором случае, достаточно обойтись косинусом. Если знак положительный - сменили направление.

a = p[j]-p[j-1]
b = p[j+1]-p[j-1]
cos(a, b) = (a.x*b.x+a.y*b.y) / (sqrt(a.x*a.x+a.y*a.y)+sqrt(b.x*b.x+b.y*b.y))

если знаменатель равен нулю, значит точки совпадают

Так зачем же Вы делите на длины если они положительны и знака не меняют? Просто

Код

C++ (Qt)
qreal dot = a.x*b.x+a.y*b.y; 
 

Это скалярное произведение 2 векторов, равно косинусу угла между векторами умноженному на их длины.

Кстати положение третьей точки можно узнать через уравнение прямой по двум точкам:
(p.x-p1.x)/(p2.x-p1.x) = (p.y-p1.y)/(p2.y-p1.y)
...
Для определения положения руля можно узнать положение точки p[j+1] относительно прямой построенной по точкам p[j], p[j-1]

Вроде как в этом случае вычислений меньше

Ну найти точку из этого уравнения не удастся, т.к неизвестных 2 (x и у), а ур-е одно. Можно рассуждать так: пусть есть прямая заданная точками p1 и p2. Она разбивает плоскость на 2 полу-плоскости. Подставив тестируемую точку p в ур-е прямой получаем число (знаковое расстояние). Если оно > 0, точка p "слева", если < 0 то справа. Расписав ур-е "крестиком"

Код

C++ (Qt)
qreal cross = (p.x-p1.x) * (p2.y-p1.y) - (p2.x-p1.x) * (p.y-p1.y);
 

Получаем формулу векторного произведения

[Torvald]

Так зачем же Вы делите на длины если они положительны и знака не меняют?

Действительно. Не догадался.

Ну найти точку из этого уравнения не удастся, т.к неизвестных 2 (x и у), а ур-е одно. Можно рассуждать так: пусть есть прямая заданная точками p1 и p2. Она разбивает плоскость на 2 полу-плоскости. Подставив тестируемую точку p в ур-е прямой получаем число (знаковое расстояние). Если оно > 0, точка p "слева", если < 0 то справа. Расписав ур-е "крестиком"

Код

C++ (Qt)
qreal cross = (p.x-p1.x) * (p2.y-p1.y) - (p2.x-p1.x) * (p.y-p1.y);
 

Получаем формулу векторного произведения

Как это два неизвестных? И не нужно искать точку, подставив в него данные (а они все известны) - получаем число, по знаку которого можно судить в какую сторону повернут руль.
Вот же:
(p.x-p1.x)/(p2.x-p1.x) = (p.y-p1.y)/(p2.y-p1.y)
где p - точка p[j+1]
p1 и p2 - прямая образованная двумя точками p[j-1] и p[j]

подставляем, решаем:
value = (p.x-p1.x)/(p2.x-p1.x) - (p.y-p1.y)/(p2.y-p1.y)

Деление в самом деле можно заменить умножением, опять же не догадался:
value = (p.x-p1.x)*(p2.y-p1.y) - (p2.x-p1.x)*(p.y-p1.y)

получилась ваша формула. Хотя согласен, можно было сразу ее использовать  

----------------------------------------
Над следующей задачкой обещаю подумать получше 

[Igors]

#4  Дана картинка (слева). Получить популярный эффект выдавливания (справа), который называется всяко (emboss, bump и.т.п. - не суть). Придумывать опции эффекта разрешается

[Torvald]

#4  Дана картинка (слева). Получить популярный эффект выдавливания (справа), который называется всяко (emboss, bump и.т.п. - не суть). Придумывать опции эффекта разрешается

Воспользоваться оператором Собеля и нормализировать полученные значения.

Для этого сперва нужно привести картинку к черно-белому виду. Это можно сделать чисто математически - найти среднее арифметическое по всем каналам для каждого пикселя:
result[j] = (r[j]+g[j]+b[j]) / 3
а можно с учетом человеческого зрения, когда каждый канал воспринимается глазом по разному, например:
result[j] = r[j]*0.2126 + g[j]*0.7152 + b[j]*0.0722

После этого можно применять оператор Собеля. Судя по правой картинке из вашего примера, градиент был применен по горизонтали:
-1 0 1
-2 0 2
-1 0 1
После применения оператора Собеля имеем изображение в более широком диапазоне, чем исходное изображение, в том числе и отрицательную яркость пикселей.
На этом этапе можно изменить силу эффекта или контрастность:
v *= contrast, где v - пиксель после применения оператора Собеля, contrast - значение от 0 до 1
Яркость:
v += bright, где bright в диапазоне от -127 до 127
И собственно нормализация, приведение к диапазону от 0 до 255:
v += 127
v = clamp(v, 0, 255);

Можно попробовать модернизировать оператор - добавить возможность задания вектора градиента.
Вот набросал небольшую демку:

Хотя все равно больше похоже на фотошопное "теснение", чам на картинку вправа у вас

[Igors]

Воспользоваться оператором Собеля и нормализировать полученные значения.

Хммм... часто после того как человек нашел решение в инете (или изучил в школе?) с ним становится трудно что-то обсуждать Ведь он уже "знает правильный ответ".  В действительности найденное - далеко не всегда лучшее. Да, Собель возможен, но он довольно хлопотлив в реализации и возможности ограничены. Есть др решение, которое гораздо проще и богаче.

Закройте исходную левую картинку (чтобы не сбивала с толку) и смотрите только на правую. Не кажется ли Вам что это рельеф/ландшафт местности? Не надо пугаться что горы - это уже 3D, наоборот, здесь решение в 3D гораздо проще чем в 2D. Ну это если хотите подумать, а нет - я расскажу т.к. Вы рабочее решение привели.

а можно с учетом человеческого зрения, когда каждый канал воспринимается глазом по разному, например:
result[j] = r[j]*0.2126 + g[j]*0.7152 + b[j]*0.0722

Укажите первоисточник откуда взяты коэффициенты. Насколько я помню blue ~ 0.11 green ~ 0.59

[Old]

Хммм... часто после того как человек нашел решение в инете (или изучил в школе?) с ним становится трудно что-то обсуждать Ведь он уже "знает правильный ответ".

Судя по тому, как вы сейчас общаетесь, вы нашли в интернете другой "правильный ответ". Умничка.

[Torvald]

Укажите первоисточник откуда взяты коэффициенты. Насколько я помню blue ~ 0.11 green ~ 0.59

Это зависит от цветовой модели. Вот источник

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

Ну, не хотите готовыми операторами, можно воспользоваться нечто подобным, что я описал в этой статье.
В данном случае взять черно-белую картинку и представить что она - это карта высот. Далее можно взять источник света, находящийся, например слева в бесконечности (вектор) и "осветить" эту "местность" используя карту высот.
То есть для каждого пикселя смотрим на разность высот/интенсивностей в двух соседних точках лежащих на одинаковом расстоянии на луче света, проходящим через рассматриваемый пиксель. На основе этой разности можно вычислять интенсивность пикселя в результирующей картинке. Расстояние между этими точками влияет на силу эффекта. Сами точки не обязательно будут совпадать с пикселями, для них можно интерполировать значения, особенно это будет проявляться на векторах не кратных 90°
К сожалению сейчас на работе нет времени подробнее описать или набросать демку, но если хотите вечером распишу подробнее.

Или если уж совсем просто: разность между левым и правым пикселем от текущего - и есть результирующий bump. Правда в данном случае будут отрицательные и малые значения, поэтому нормализация все же необходима. Но это решение хоть и быстрое, но не универсально) Зато очень хорошо распараллеливается и переносится на SIMD архитектуру.