Условие близости точки к конкретной половине эллипса

[Lia]

Обязательно.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Алексей К.]

Получимши уведомления о новых акциях в теме, внимательно её перечитал. И не понял, почему год назад встрял в неё --- я ведь ничего не понял, ни тогда, ни сейчас. Скорее всего, было скучно, и сработал синдром ВЖНД. Тем не менее автор пару раз отметил мои слепые советы; возможно, отметил не просто из вежливости, а что-то в них в натуре угадалось.

Тут побывала модератор Lia, и меня подмывает спросить её: поняла ли она постановку задачи (знаю, что такой обязанности нет)? Если да --- может ли она, в порядке любезности, парой слов пояснить мне, о чём речь?

Ну и сам автор темы --- может, он сумеет изложить задачу для человека как бы постороннего, в математике не совсем профана, но не способного к телепатии, к угадыванию --- чем занимается и о чём думает автор? В пивняке это было бы легко, но не через интернеты.

Kshvorowiszm в сообщении #946300 писал(а):

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

Соседние в каком смысле: один или оба номера пикселов отличаются ровно на единицу?

Что первично --- точки или эллипс?

Изначально задан эллипс, на нём как-то вырисовались две точки? И почему тогда не сразу задан искомый полуэллипс?

Изначально появились две точки, и к ним приваривается какой-то эллипс? Ну, нет, совсем ерунда, импоссибль...

Пример, когда автор явно рассчитывает на телепатию:

Kshvorowiszm в сообщении #1087690 писал(а):

Формулы являются

$A=b^2\cos^2\beta+a^2\sin^2\beta$
$B=y\cdot2\cos\beta\sin\beta\cdot(b^2-a^2)$
$C=y^2\cdot(b^2\sin^2\beta+a^2\cos^2\beta)$
$D=B^2-4AC$
$K=\dfrac{-B\pm\sqrt{D}}{2A}$.

Без напряжения угадывается лишь какое-то квадратное уравнение. Какое? Кто такие A, B, C? Коэффициенты уравнения коники? Что-то из личного черновичка автора? Autre chose? /В пивняке бы разобрались за 3 минуты./

Вариант (стиля):

Kshvorowiszm этого пока не писал(а):

Имеется уравнение кривой второго порядка, о которой заранее известно, что это эллипс (т.е. кривая ограничена и её можно целиком нарисовать). Требуется ? нарисовать ? кривую. Определяем её BoundingBox, выбираем (из каких-то соображений) размер окна и масштаб (ну, поскольку пикселы упоминаются, такая инфа может быть полезной).

Рассмотрим две соседние точки, образовавшиеся (таким-то путём)... Проблема в том, что... итд.

/Ни на чём, ясен пень, не настаиваю./

[Lia]

Алексей К. в сообщении #1088124 писал(а):

Тут побывала модератор Lia, и меня подмывает спросить её: поняла ли она постановку задачи (знаю, что такой обязанности нет)? Если да --- может ли она, в порядке любезности, парой слов пояснить мне, о чём речь?

Нет, не могу пояснить. Слова порознь понимаю, а вот вместе - никак.
Пусть уж автор пояснит.

[Kshvorowiszm]

Если откинуть нужность или нет алгоритмов, суть вопроса, чтобы найти расстояние от каждой из двух точек (находящихся где-то на небольшом отдалении друг от друга и эллипса) до одной из дуг эллипса, выбросив из внимания другую дугу. И я нашёл как это сделать, введя прямую, проходящую через эти точки. Не через боковые вершины, как предложили, а именно через них. И это квадратное уравнение – это и есть решение системы, пересечения прямой и наклонного эллипса (уравнение которого я написал как раз над этими формулами). Его коэффициенты, это что лучнýлось из этого. Буквы такие я сделал для удобства, потому что так действительно решаются квадратные уравнения.
Это не на телепатию, а я думал что если кто-то будет решать такое, он придёт к этому же, и уже будет знать что это. Там ведь сказано, что это $K$ это мы ищем их пересечение, одна координата.


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

Цитата:

Соседние в каком смысле

При пиксельно-пространственном алгоритме выбираются соседние на экране точки, потому что так проще описать. Нам ведь надо рисовать одну их них. На самом деле можно проверить (тогда я ещё это не знал) одну точку между ними, и по её погрешности сделать вывод, склоняться на следующем ходу рисования в эту точку, или другую.

Я знаю, что можно нарисовать эллипс параметрически, как вы писали. И таких алгоритмов уже несколько находил. Но это алгоритмы – исходят из углового пространства, и мало того что требуют тригонометрию в процессоре, так и потом грубо находят точки, отражающие эллипс. А надо-то нарисовать – точки. Поэтому хорошим (“настоящим”) механизмом рисования фигуры является алгоритм, исходящий из пиксельного же пространства. То есть берущий за исходную точку какую-то точку, идущий по точкам, подставляющий их в модель, и проверяющий какая точка лучше подходит. К тому же это быстрее. Я думаю это не естественно – считать косинусы при нарисовке окружности. Человек собственно и нашёл значение синусов и косинусов проходя окружность по шагам. (наверно.)
Эти алгоритмы (парам.) тоже можно уоптимизировать (Допустим недавно нашёл алгоритм Минского – там первая точка считается синусами, а следующие – поворотом относительно её по формуле поворота.), но всё равно, дельта-алгоритм “типа Брезэнхэма” может спуститься чуть ли не до $5$'и тактов на точку для наклонных, это быстрее, и вообще не зависит от $3$гонометрических функций.

Главное (если строить эллипсы и окружности для художественности, пиксел-арта, а не только математических иллюстраций), что они правда грязные – или их нужно ещё нетривильно оптимизовывать. Вот сравните результирующий растр у нарисованного из пикселного пространства:



и как вы говорили достаточным, уже способом, $\Delta\angle\to tochka$:



Второй не гарантирует какие будут затронуты точки – все которые покрывает кривая, или минимально нужные соседи. А в первом это точно ясно, и можно даже выбирать ($8$'иходовой или $4$'ёхходовой).

Поэтому я и начал вопрос с пикселов. Может мне правильнее было спросить в ычислительном подфоруме, но я не полностью догадался.

И в пивную я не хожу. Там бы я не смог быть.

Ваш совет действительно тоже меня продвинул. Сначала я не представлял, что надо ПРЯМО в уравнение подставлять – пытался через закономерность фокусов.

[Алексей К.]

Lia в сообщении #1088141 писал(а):

Нет, не могу пояснить.

А я что-то понял. В середине текста нашёл то, с чего автору следовало начинать:

Kshvorowiszm в сообщении #1088151 писал(а):

Я знаю, что можно нарисовать эллипс параметрически, как вы писали. И таких алгоритмов уже несколько находил. Но это алгоритмы – исходят из углового пространства, и мало того что требуют тригонометрию в процессоре, так и потом грубо находят точки, отражающие эллипс. А надо-то нарисовать – точки.

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

Ну и вижу, что предложенный мной тест на близость (к эллипсу, а не к какой-то там половинке) вполне уместен.
И алгоритм видится простым. Как бы берём начальную точку и направление, три пиксела-кандидата (в данном направлении) проверяем на близость, корректируем направление для следующего шага. Хочется даже взять в руки PostScript и наколотить программку, но пока возьму себя в руки --- уже наделал фарша, теста, и баня ждёт; не до программирования.

И, повторяю, --- с этого следовало начать. Вы же, Kshvorowiszm, и во второй раз начали не с этого. Вот покажу Вам, как читателю читается Ваш текст.

Kshvorowiszm в сообщении #1088151 писал(а):

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

Каких двух точек? откуда они взялись? почему от двух сразу, а не от каждой по отдельности?
Понимаете --- Вы использовали слово "каждой". Это безусловно требует предварительного знакомства читателя с точками.

Цитата:

...(находящихся где-то на небольшом отдалении друг от друга и эллипса) до одной из дуг эллипса, выбросив из внимания другую дугу.

Эллипс --- известен? (теперь знаю, что да, известен, но как трудно было получить это знание, не владея телепатией!) Известно, о какой половинке идёт речь? И что понимается под половинкой? Дуга между двумя противоположными вершинами? Наибольшая из двух таких дуг? (Есть и другие варианты).

Цитата:

И я нашёл как это сделать, введя прямую, проходящую через эти точки.

Чтобы найти расстояние от точки до эллипса нужна какая-то другая точка??? И прямая, проходящая через них??? Звучит, извините, ... ну, странно.

Ну и ещё про телепатию:

Цитата:

И это квадратное уравнение – это и есть решение системы, пересечения прямой и наклонного эллипса.

Но там нет квадратного уравнения, его следы только угадываются. А про $A,B,C$ следовало ясно написать, что это (если я правильно угадал) коэффициенты уравнения прямой, и само уравнение выписать: $Ax+By=C$ или $Ax+By-C=0$?

Ну как бы на сегодня всё, нет временных ресурсов (хотя хочется ещё два раза столько написать... картинки последние раскритиковать... ещё чо-то, про русский язык... глагол "лучнýлось" оставлю в покое).

А когда в пытался нагуглить "алгоритм Минского", мне среди прочих ненужностей выложили:

Цитата:

Лауреатом стала группа "Алгоритм" Минского радиотехнического института.

[Алексей К.]

Алексей К. в сообщении #1088240 писал(а):

$Ax+By=C$ или $Ax+By-C=0$?

Ну, я имел в виду в качестве второго варианта нечто, реально отличное от первого: $Ax+By{\color{magenta}{}+{}}C=0$. Очередной объект угадывания.

[Kshvorowiszm]

Казалось, уж по тем советам, что мне дали, люди должны были въехать больше, чем сейчас вы говорите, что никак. (И iifat и sender кажется поняли >.) Уж с этой белой схемой которую я привёл, мне казалось всё стало до крайности ясно. Может я ошибался.

(Оффтоп)

(Лучнулось - это получилось в совершенном виде. То есть получилось это много раз лучилось. Если мне на это указывают, я могу печатать пообщепринятее, но сам скашиваюсь на такое.)

Эллипс строится по жёстко взятому направлению. Сначала берётся одна дуга и её надо нарисовать. Точнее он рисуется проходя 8 октантов, но дуги я упоминаю потому что именно дуга (противоположная к рисуемой) становится проблемной. Ведь при сужении одного радиуса эллипс как бы схлопывается двумя половинами. А тонкие тоже надо смочь нарисовать.
Найти расстояние от одной точки до эллипса, прямая не нужна. Но полноценно это расстояние ищется слишком сложно, и для моего понимания, и процессорно, и приходится использовать какой-то упрощённый метод. Такой как “подставить в уравнение и найти погрешность”. Но такая подстановка не срабатывает (для рисования одного зафиксированного отрезка), когда эллипс тоньше чем шаг рисования. На белой схеме – зелёная точка внизу: это которую нарисовали допустим во предыдущем шаге, а верхняя зелёная, это которую по идее надо нарисовать дальше. Но при подстановке в уравнение меньшую погрешность даёт левая, зачёркнутая красным точка. И дальше всё разъезжалось, потому что следующая точка часто была ещё дальше от истинной.
А прямая эта – дала какую-то размерность, по которой можно численно точно узнать до какой стороны точка ближе. Любая гипотетическая точка.

$A$, $B$ и $C$ это просто мои переменные – при решении квадратного уравнения, получающегося из системы “прямая и эллипс”. Прямая задаётся просто одним игреком, это не её коэффициенты. Она горизонтальная, в этом примере, который на схеме. Может ещё быть вертикальная. Тогда будет $x$.
Я не хотел приводить все переобразования, как я лучнул квадр. ур. из ур. эллипса, подставив туда $y$, потому что это уже ответ, который просто может кому-то пригодиться. Он проверен, находить там что-то ещё пока никому нужно.

[Алексей К.]

Пивняк был просто совковой метафорой (не знаю, как это явление выглядит сейчас, если вообще существует). Замену искать не стал, хотя слово "семинар", наверное, подошло бы.

Kshvorowiszm в сообщении #1088421 писал(а):

Казалось, уж по тем советам, что мне дали, люди должны были въехать больше, чем сейчас вы говорите, что никак. (И iifat и sender кажется поняли >.) Уж с этой белой схемой которую я привёл, мне казалось всё стало до крайности ясно. Может я ошибался.

Ошибались, и мне даже удалось привлечь доказательство (спасибо Вам, отзывчивая Lia). Люди все сильно разные. Возможно, упомянутые Вами iifat и Sender просто знали про Брезенхэма (теперь и я знаю) и потому поняли, что было у Вас в голове на самом деле. А то, что Вы не умеете излагать свои мысли --- как бы очевидно, независимо от того, что кто-то сумел Вас понять.

Мне просто хотелось Вам показать, что так разговаривать нельзя. Но убедительно я это сделать (без пивняка ) не смогу, так что всё оставляю за Вами: либо Вы поверите мне и что-то предпримете для себя (маловероятный исход), либо останетесь в уверенности, что ... (обычно бывает именно так). Педалировать эту подтему не хочу --- она очень многобуковная, если спорить и развивать. Отмечу лишь, что Ваша необидчивость порадовала (другой бы давно залез в бутылку, а то и наговорил бы гадостей).

По делу:
проблемы какие-то с алгоритмом остались?

[Kshvorowiszm]

11 сообщений назад у меня там ошибка.
Во-первых-и-вторых в уравнении сомножители $a^2$ и $b^2$ перепутаны, и квадратов нет. Должно быть:

$b^2(x\cos\beta+y\sin\beta)^2+a^2(y\cos\beta-x\sin\beta)^2=a^2b^2$

В-третьих ответ. Для горизонтальных прямых – да, а вертикальных, конечно надо не только заменить $y$ на $x$, но и формула другая:

$$ \begin{align} &A=b^2\cos^2\beta+a^2\sin^2\beta &&A=b^2\boldsymbol{\sin}^2\beta+a^2\boldsymbol{\cos}^2\beta\\ &B=y\cdot2\cos\beta\sin\beta\cdot(b^2-a^2) &&B=x\cdot2\cos\beta\sin\beta\cdot(b^2-a^2)\\ &C=y^2\cdot(b^2\sin^2\beta+a^2\cos^2\beta) &&C=x^2\cdot(b^2\boldsymbol{\cos}^2\beta+a^2\boldsymbol{\sin}^2\beta)\\ &D=B^2-4AC\\ &K=\dfrac{-B\pm\sqrt{D}}{2A} \end{align} $$

Плохо что не могу редактировать то сообщение, там бы исправил.

Лучше выложу промежуточные действия:

уравнение $b^2(x\cos\beta+y\sin\beta)^2+a^2(y\cos\beta-x\sin\beta)^2=a^2b^2$.
Открыть скобы с целью выделить всё при $x$, $y$.

$$ \begin{align} &b^2(\cos^2\beta x^2 + \sin^2\beta y^2 + 2\cos\beta\sin\beta xy) + a^2(\sin^2\beta x^2+ \cos^2\beta y^2 - 2\sin\beta\cos\beta xy) - a^2b^2 =\\ =\;&b^2\cos^2\beta x^2 + b^2\sin^2\beta y^2 + b^2 2\cos\beta\sin\beta xy + a^2\sin^2\beta x^2 + a^2\cos^2\beta y^2 - a^22\sin\beta\cos\beta xy - a^2b^2 =\\ =\;&(b^2\cos^2\beta+a^2\sin^2\beta) x^2 + (b^2\sin^2\beta+a^2\cos^2\beta) y^2 + 2\sin\beta\cos\beta(b^2-a^2) xy - a^2b^2 = \end{align} =\left\biggl[ \begin{array}( (b^2\cos^2\beta+a^2\sin^2\beta) \boldsymbol{x^2} + 2\sin\beta\cos\beta(b^2-a^2)y \boldsymbol{x} + (b^2\sin^2\beta+a^2\cos^2\beta)y^2 - a^2b^2 \\ (b^2\sin^2\beta+a^2\cos^2\beta) \boldsymbol{y^2} + 2\sin\beta\cos\beta(b^2-a^2)x \boldsymbol{y} + (b^2\cos^2\beta+a^2\sin^2\beta)x^2 - a^2b^2 \\ \end{array} \right. $$

Так образуется то квадратное уравнение.

В алгоритме я ещё буду додумывать, там не всё сделано, но именно то что хотел спросить вроде ясно.
Механизм Минского кстати это вот: blog.mattgauger.com.

-- 08.01.2016, 13:16 --

А вообще эта задача должна где-то быть уже написана в полной форме – наклонного эллипса с наклонной прямой. И с этим частным случаем. Мне тут надо было просто сказать, что для алгоритма надо применить это пересечение.

[Kshvorowiszm]

И опять я ошибся не дописал.

$$C = ....-a^2b^2\qquad\qquad\qquad C = ....-a^2b^2$$

в обоих. Конечно, из нижних преобразований это видно.