Дано:

На плоскости есть выпуклый четырехугольник ABCD и точка F внутри этого четырехугольника. Через точку F проходит прямая, которая пересекает стороны AB и CD в точках O и P соотвественно. Причем так, что AO/OB = CP/PD.


Нужно найти это соотношение (алгоритм его получения).

Ответа не знаю.

нарисуй

Нарисовал. Осталось запрограммировать. Первое что в голову приходит - описать уравнения прямых и т.д., но там с учетом неизвестных O и P просто тонны матана вываливаются на втором же шаге, а дальше вообще нереально.

В таких условиях это соотношение может оказаться любым.
Берем любое положительное k. Выбираем точки O и P так, что k = AO/OB = CP/PD
На отрезке OP берем любую точку F.

(3) Координаты точек ABCD и точки F задаются условием.

Точнее:

AO/OB = PD/CD

Тфу , вот:

AO/OB= DP/PC

(3) если я правильно понимаю, то возможно несколько вариантов решения, для одной конфигурации четырехугольника

(4) теперь понятно

(6) в некоторых частных случаях (например, для трапеции) легко доказывается, что прямые на которых лежат AD, BC и OP пересекаются одной точке или параллельны. Возможно (здесь придется помучиться с доказательством) это верно и в общем случае, тогда задача легко решается: находим точку пересечения прямых AD и BC и проводим прямую через F.

*(9) не.. в общем случае не верно

(2) правильный ход, но никакого страшного матана там нет - линейное уравнение с одним неизвестным.

+(11) для задачи не требуется писать программу, в результате решения можно получить формулу от исходных  координат

(12) Тут как раз нужна программа по входящим координатам. Послушал совета - углубился в матан. Его там действительно не так много, как в первый раз казалось.

k - искомый коэффициент. Ax, Ay - координаты точки А.

Итого на момент получил:

(Fx - Ax - k*Bx + k*Ax)*(Fy - Dy - k*Cy + k*Dy) = (Fx- Dx - k*Cx + k*Dx) * (Fy - Ay - k*By + k * Ay)

осталось перемножить и решить квадратное уравнение )

Не пойму только что будет второй корень давать.

(14) по идее там всё линейно, квадратного быть не должно. Углубляться правда лень.

https://ru.m.wikipedia.org/wiki/Проективное_преобразование


Если спроецировать четырехугольник на квадрат, то коодината Fy' и будет ответом.

что то кажется решения в общем случае нет
(16) проективное преобразование афаир задается тремя точками, так что решения может не быть

(16) квадрат не обязательно, достаточно 2х параллельных сторон
(17) решение очевидно есть и оно единственное

(4) Тогда прямая OP однозначно определяется без всякой точки F. И вопрос только в том, лежит ли F на этой прямой.

(18) решения поиск преобразования проективное в квадрат. Решение задачи да, понял что можно показать что всегда есть
кажется можно через вектора записать и решить
АБ = к*АО
ДЦ = к*ДП
и уравнение прямой через точки О и П для К

(19) таких прямых много. С учетом (6), если обозначить k=AO/AB=DP/DC, то прямая OP вращается (или движется параллельно) превращаясь в AD(k=0) и ВС (при k=1). Решение очевидно есть и на отрезке [0,1] единственное.

Если задача решить программно, можно просто делением отрезка пополам получить k с нужной точностью.

Через аффинные преобразования не взлетело (или кунг-фу не хватило). Теоретически, если разметить каждую сторону на n делений и провести линии между противоположными, то получится вполне годная координатная сетка (хоть и кривая) и у точки F будет вполне конкретная координата в этой сетке. Т.е. преобразование существует, вопрос в том как его найти...

(21) С удовольствием сделал бы дихотомией, но участок такой что каждый такт на счету.

Пока продолжу с уравнениями прямых.

(21) да вот только она не заметает полный диапазон, все думаю над контр примером)

(0) Нарисуй.

(23) от одной стороны до другой, где не заметает-то?
Ты (6) учитываешь?

https://hkar.ru/QJ3d

Наконец-то нарисовал )

Пришёл к каноническому квадратному уравнению:


k*k(Bx*Cy - Ax*Cy - Bx*Dy + Ax*Dy - Cx*By + Dx*By + Cx*Ay - Dx*Ay)
+k*(-Bx*Fy + Ax*Fy + Bx*Dy - Ax*Dy - Fx*Cy + Ax*Cy + Fx*Dy - Ax*Dy + Cx*Fy - Dx*Fy - Cx*Ay + Dx*Ay + Fx*By - Dx*By - Fx*Ay + Dx*Ay)
+(-Ax*Fy - Fx*Dy + Ax*Dy + Dx*Fy + Fx*Ay - Dx*Ay) = 0

Если взлетит, выложу вывод )

(22) так не бери пополам. Посчитал для k1=0 q<0 для k2=1 w>0 берешь k3 = -q/(w-q). Т.к. всё линейно, есть подозрение, что это возможно это будет точное решение (и то самое искомое преобразование), а нет - ну сделаешь еще десяток итераций.

Что за задача-то прикладная?

(29) Грубо говоря надо раскрасить градиентно растр в пределах четырехугольника, так, чтобы точки на границе AD имели 100% цвета, а на границе BC 0%.

С уравнением что-то не взлетело )

(26) Теперь доведи АВ и СД до точки соединения.

(4) хм...
AO/OB*CD/PD=1
видимо такая точка максимум единственная тогда, или ее нет

(33) Смотри (26).


Кстати OP теоретически в длину равна (АD + (BC - AD)*k), это наверное можно использовать.

(34) нет, только если стороны параллельны, иначе из-за поворота OP будет нелинейная зависимость от k

(35) Да, действительно... Может уменьшаться к середине и растягиваться ближе к сторонам.

С уравнением снова не взлетело, результаты те же. ~120 и ~-20 интересно знать бы что это, закладывалось вообще число 0..1.

Ладно, сегодня спать.

(30) так это задача? Бери и закрашивая, точка F то откуда?

(0) Рекомендую прислушаться к (32), только немного подправив:
у (BC) и (AD) находишь точку пересечения, и из этой точки проводишь прямую через F. Ее пересечение с (AB) и (CD) и будут твои нужные точки. Если же (BC) и (AD) параллельны, то и прямая через F будет параллельной им.

(38) в общем случае не верно

(37) F это точка растра. Для неё нужно вычислить "удаленность" от AD относительно BC.

(38) В ту сторону думал, неверно.

Копаю в эту сторону:

Допустим: x - искомое отношение, y - OF/FP.

(грубо говоря x и у это локальные координаты точки F в "пространстве ABCD" где A = (0,0) С =(1,1))

Сначала найдем F "зная" x и у:


Fx = Ox + y*Px - y*Ox

Fy = Oy + y*Py - y*Oy

где:

Ox = Ax + x*Bx - x*Ax

Oy = Ay + x*By - x*Ay

Px = Dx + x*Cx - x*Dx

Py = Dy + x*Cy - x*Dy

а дальше ща посмотрим

Напутал только с направлениями, под рисунок щас подгоню.

Пришли к системе уравнений без всяких квадратов (ошибку, которая приводила к квадратному уравнению нашёл):

Fx = x*y*Ax - x*y*Bx + x*y*Cx - x*y*Dx + y*Bx - y*Ax + x*Dx - x*Ax + Ax


Fy = x*y*Ay - x*y*By + x*y*Cy - x*y*Dy + y*By - y*Ay + x*Dy - x*Ay + Ay

имхо туда рулим

(40) Если это "удаленность", то можно ввести другие меры
-отношение расстояний от F

..(44)
-отношение расстояний от F до AD и BC
-или соотношение отрезков на которые F разобьет прямую указанную в (9) и (32)

(43) это система, всё равно квадратное получишь

(44) Отношение высот неплохо работает на большинстве четырехугольников... Но есть такие на которых сразу косяки вылезают.

(44)

https://hkar.ru/QJq0

Вот закрашивание ряда четырехугольников градиентом через отношение высот. на изгибах на границе двух фигур получается различие в оттенке. Если вычислять коэффициент по условиям задачи, этих различий на границах не будет.

x = (Fx - Ax - y*Bx + y*Ax)/(y*Ax - y*Bx + y*Cx - y*Dx + Dx - Ax)

x = (Fy - Ay - y*By + y*Ay)/(y*Ay - y*By + y*Cy - y*Dy + Dy - Ay)

Квадратное, конечно, будет, но одно. А раньше квадратная система вылезала.

(48) ты хочешь одномерный градиент, зачем вычислять для каждой точки - рисуй сразу линии. Только на границах получишь ломанные. Это именно тот результат который ты получишь решив (0). Если нужна гладкость, то нужна другая мера или вообще подход

что за первая пара уравнений в (41)? просто запиши что Ф является решением для прямой ОП
ЗЫ и зачем писать уравнения для осей х и игрек? они одинаковые, решай только для х

(52) Это и есть запись о том, что F является решением для ОП.

(48) Если задача так стоит, то вопрос - почему ты F берешь "где-то"? Намного проще же, если ты сразу F будешь брать на (AB) и тогда соответствующая точка на (CD) элементарно вычисляется.

+(54) Дополнительным плюсом будет то, что цвета на границах соседних трапеций будут 100% совпадать.

(54) На (48) видно, что изображение состоит из довольно крупных квадратов (и они могут быть больше). Т.е. я получаю квадраты, которые центрами входят в заданный четырехугольник и для каждого определяю цвет. Обычно нельзя найти даже два соседних квадрата с абсолютно одинаковым тоном. Т.е. "выбрать цвет и залить им полосу поперек градиента" не вариант.

Таки свершилось:

https://hkar.ru/QJx8

Решение:

Коэффициенты квадратного уравнения:
float a = C.x * B.y - D.x * B.y - C.x * A.y + D.x * A.y - C.y * B.x + D.y * B.x + C.y * A.x - D.y * A.x;
float b = C.x * A.y - D.x * A.y + D.x * B.y - F.x * B.y - D.x * A.y + F.x * A.y - F.y * C.x + F.y * D.x - C.y * A.x + D.y * A.x - D.y * B.x + F.y * B.x + D.y * A.x - F.y * A.x + F.x * C.y - F.x * D.y;
float c = F.y * A.x - F.x * A.y - F.y * D.x + D.x * A.y - D.y * A.x + F.x * D.y;

Дискриминант:
float d = b * b - 4 * a * c;
if (d >= 0)
{
    Result = -((-b - Mathf.Sqrt(d)) / (2 * a)); // Работает первый (отрицательный) корень со знаком "-". ХЗ почему.
}

лепота)

(56) Извини, я просто, видимо, не понимаю. На рисунке (57) у тебя квадраты не однотонные, а тоже с градиентом. Правильно?
Я к чему - что мешает тебе залить четырехугольники моим алгоритмом, а потом порезать фигуру на квадраты? А если квадрат должен быть однотонным, то рисунок в (57) будет менее красивым.

(59) движок смазывает переход между пикселями. Вообще это не пиксели, а ячейки террейна в каждой из которых две текстуры с разной степенью прозрачности.

Просто для простоты выбрана белая и черная текстуры.

Кстати в 57 поправка (существует вероятность отличная от нуля, что это кому-то понадобится) срабатывает положительный корень, а не отрицательный.