2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение03.01.2016, 04:45 


20/03/14
12041
Обязательно.

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

 Профиль  
                  
 
 Posted automatically
Сообщение03.01.2016, 11:14 


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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение04.01.2016, 22:53 


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

Тут побывала модератор 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, выбираем (из каких-то соображений) размер окна и масштаб (ну, поскольку пикселы упоминаются, такая инфа может быть полезной).

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

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение05.01.2016, 01:47 


20/03/14
12041
Алексей К. в сообщении #1088124 писал(а):
Тут побывала модератор Lia, и меня подмывает спросить её: поняла ли она постановку задачи (знаю, что такой обязанности нет)? Если да --- может ли она, в порядке любезности, парой слов пояснить мне, о чём речь?
Нет, не могу пояснить. Слова порознь понимаю, а вот вместе - никак.
Пусть уж автор пояснит.

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение05.01.2016, 06:59 


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

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

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

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

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

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

Изображение

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

Изображение

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

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

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

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение05.01.2016, 17:30 


29/09/06
4552
Lia в сообщении #1088141 писал(а):
Нет, не могу пояснить.

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

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

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

И, повторяю, --- с этого следовало начать. Вы же, Kshvorowiszm, и во второй раз начали не с этого. Вот покажу Вам, как читателю читается Ваш текст.
Kshvorowiszm в сообщении #1088151 писал(а):
Если откинуть нужность или нет алгоритмов, суть вопроса, чтобы найти расстояние от каждой из двух точек...
Каких двух точек? откуда они взялись? почему от двух сразу, а не от каждой по отдельности?
Понимаете --- Вы использовали слово "каждой". Это безусловно требует предварительного знакомства читателя с точками.

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

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

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

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

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение06.01.2016, 00:33 


29/09/06
4552
Алексей К. в сообщении #1088240 писал(а):
$Ax+By=C$ или $Ax+By-C=0$?
Ну, я имел в виду в качестве второго варианта нечто, реально отличное от первого: $Ax+By{\color{magenta}{}+{}}C=0$. Очередной объект угадывания.

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение06.01.2016, 10:05 


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

(Оффтоп)

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


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

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение06.01.2016, 23:36 


29/09/06
4552
Пивняк был просто совковой метафорой (не знаю, как это явление выглядит сейчас, если вообще существует). Замену искать не стал, хотя слово "семинар", наверное, подошло бы.
Kshvorowiszm в сообщении #1088421 писал(а):
Казалось, уж по тем советам, что мне дали, люди должны были въехать больше, чем сейчас вы говорите, что никак. (И iifat и sender кажется поняли >.) Уж с этой белой схемой которую я привёл, мне казалось всё стало до крайности ясно. Может я ошибался.
Ошибались, и мне даже удалось привлечь доказательство (спасибо Вам, отзывчивая Lia). Люди все сильно разные. Возможно, упомянутые Вами iifat и Sender просто знали про Брезенхэма (теперь и я знаю) и потому поняли, что было у Вас в голове на самом деле. А то, что Вы не умеете излагать свои мысли --- как бы очевидно, независимо от того, что кто-то сумел Вас понять.

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

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение08.01.2016, 13:00 


14/12/14
17
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 --

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

 Профиль  
                  
 
 Re: Условие близости точки к конкретной половине эллипса
Сообщение08.01.2016, 15:27 


14/12/14
17
И опять я ошибся не дописал. $$C = ....-a^2b^2\qquad\qquad\qquad C = ....-a^2b^2$$ в обоих. Конечно, из нижних преобразований это видно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group