?

Log in

No account? Create an account
 
 
23 Ноябрь 2012 @ 01:59
Хочется  
Определить вложенность/невложенность двух замкнутых контуров на плоскости, заданных аналитически или кусочно.
Ясен пень, что пересечение это просто корни найти. А вот внутри или снаружи.. как это?
Надо оценить возможные методы и потребные вычислительные ресурсы.
 
 
 
zewgmazewgma on Ноябрь, 24, 2012 05:33 (UTC)
Если корней нет, то это не обязательно один внутри, а может быть и что они рядом!
zewgmazewgma on Ноябрь, 24, 2012 06:07 (UTC)
Еле натянувшие тройку по матану предлагают поступить так (картинка)





Объяснения:
1) Красная стрелочка. Вот ты нашел, что корней нет - два контура не пересекаются. Надо узнать, расположен ли один внутри другого, или они как-нибудь рядом. По-моему, удобно сделать систему уравнений, добавив некое линейное, чтоб значит эта линия пересекала, и посмотреть, лежат ли точки пересечения с одним из контуров между точками пересечения с другим из контуров, или нет.
Правда, сейчас сообразила, что может быть еще более хитрая загогулина. Тогда, пожалуй, надо было красную стрелочку пересекать с синим и зеленым контурами на рисунке.
Синий и зеленый - это фигуры, образованные касательными к внешним экстремумам. В смысле к выпуклым. Чтобы получился выпуклый многоугольник. Тогда внутренний выпуклый многоугльник (зеленый) будет точно иметь меньший периметр и меньшую площадь, чем внешний (синий).
Хотя, строго говоря, площадь внутреннего будет при любой форме меньше, чем площадь внешнего. А периметр - нет. Но зато для решения вопроса, который внутри и внутри ли, мне этот образованный касательными (= первыми производными!) многоугольник кажется очень удобным. Тогда пересечений красной стрелочки с синим и зеленым контурами будет только 4, а не как с черным контуром - неопределенно много.

zewgmazewgma on Ноябрь, 24, 2012 06:35 (UTC)
Вот вариант с хитрыми загогулинами

Чего нарисовала, сама не пойму.
Первые производные дают пересекающиеся многоугольники, а про красные линии можно ли сказать, что нет такой ситуации, чтоб все пересечения с зеленым были внутри пересечений с синим, поэтому контуры не вложены? ХЗ. Может, в таком случае вторые производные брать?
Мне перестает нравиться ход моей мысли, хотя желтая и оранжевая загогулины вышли очень красивые, как один древний морской червячок...
zewgmazewgma on Ноябрь, 24, 2012 06:37 (UTC)
Ладно, я сдаюсь, спроси профессионалов
matabubamatabuba on Ноябрь, 24, 2012 07:17 (UTC)
Ну, я для начала копнул несколько глубже - теорию множеств. И так постепенно дошел до контуров,в которых меня конечно же немедленно послали куда?.. да - в теорию множеств)))

В общем, я выяснил вопрос. Корни искать все равно придется. Причем, существует случай с корнями, но без пересечения - касание (в аналитическом случае выявляется совпадением касательных, в кусочном - стрёмной эвристикой - извращением с площадями фигур и нормалями))))
Далее, выбираются максимумы по осям (условным, допустим, посередине) фигур и сравниваются со сначением второй кривой по абсциссе и по ординате.

Вместе получается вполне годный критерий, исключая случаи кусочно-линейного (составного) контура.

Edited at 2012-11-24 07:18 (UTC)
zewgmazewgma on Ноябрь, 24, 2012 07:39 (UTC)
ну а топологию ты читал? Ее же достаточно!
matabubamatabuba on Ноябрь, 24, 2012 07:42 (UTC)
да, почитал, раньше ещё
zewgmazewgma on Ноябрь, 24, 2012 08:09 (UTC)
В топологии эти самые контуры называют циклами! http://www.itlab.unn.ru/uploads/top/topBook.pdf и считают методами линейной алгебры
matabubamatabuba on Ноябрь, 24, 2012 08:13 (UTC)
Ага, но чот без картинок))) Почитаю, спасибо.
zewgmazewgma on Ноябрь, 24, 2012 08:14 (UTC)
Я ее быстро пролистала, нашла картинку похожую и прочла к ней подпись :)
matabubamatabuba on Ноябрь, 24, 2012 08:36 (UTC)
Точно, дальше картинки есть)) Посмотрим, насколько это полезно в смысле конкретного метода вычисления.
zewgmazewgma on Ноябрь, 24, 2012 08:56 (UTC)
книжка из той же самой Википедии! ты ее (википедию) невнимательно листал.
zewgmazewgma on Ноябрь, 24, 2012 08:17 (UTC)
вот еще в тему http://habrahabr.ru/qa/19831/
matabubamatabuba on Ноябрь, 24, 2012 08:32 (UTC)
Да, та же задача.
zewgmazewgma on Ноябрь, 24, 2012 08:55 (UTC)
Ну там и название алгоритма есть.
zewgmazewgma on Ноябрь, 24, 2012 07:42 (UTC)
Если находятся точки пересечения/касания, если их, к примеру, две или больше, то через них можно провести линию и посмотреть, попадают ли туда точки, принадлежащие множеству внутри первого контура? внутри второго контура?
Корни да, по любому искать, я же и не спорю.
matabubamatabuba on Ноябрь, 24, 2012 07:44 (UTC)
Мне хотелось какой-нибудь специализированный "волшебный"))) критерий. Типа, делаешь что-нибудь с уравнениями кривых и по результату операций можно судить о вложенности.
zewgmazewgma on Ноябрь, 24, 2012 07:56 (UTC)
первые производные возьми :)


Мне казалось, что он должен быть, и как раз в топологии...
matabubamatabuba on Ноябрь, 24, 2012 08:01 (UTC)
с касательными именно производные надо брать))
мне казалось, что-нибудь эдакое, типа преобразования Лапласа или Фурье, или, там, Найквиста из ТАУ, чтобы на том конце критерий был совсем простой и очевидный.
zewgmazewgma on Ноябрь, 24, 2012 08:03 (UTC)
я знаю, для чего берут производные :)
т.е. хочешь непременно чужое преобразование, не свое?
matabubamatabuba on Ноябрь, 24, 2012 08:09 (UTC)
Вряд ли мне под силу придумать какую-то новую метафору, настолько же изящную как то же преобразование Лапласа. Занырнуть в параллельный мир, где можно пройти миллион километров одним шагом или, вот - квантовые вычисления - 100500 вычислений в одной операции одновременно?!
zewgmazewgma on Ноябрь, 24, 2012 08:15 (UTC)
не, ну - скомпилировать из существующих, ведь понятно же, что отдельные части проблемы исследованы, просто стояла ли другая задача?
zewgmazewgma on Ноябрь, 24, 2012 07:54 (UTC)
а как ты узнаешь, где середина фигуры? если ты даже не знаешь, где она находится?
matabubamatabuba on Ноябрь, 24, 2012 07:58 (UTC)
Почему же не знаю?! Знаю, у меня даже и уравнение в общем случае есть. А можно и тупо поделить координаты габаритов пополам.
Также фигуры в одной системе координат.
zewgmazewgma on Ноябрь, 24, 2012 08:00 (UTC)
ну если ты знаешь, где она сама, то почему не можешь судить о вложенности/невложенности простым, тксзть, глазом?
matabubamatabuba on Ноябрь, 24, 2012 08:01 (UTC)
Не я же буду следить)) А мозг принтера это должен делать 1000000 раз в секунду))
zewgmazewgma on Ноябрь, 24, 2012 08:04 (UTC)
он должен следить за касаниями/пересечениями, да? пока они не наступили, топология вложенности не поменялась.
matabubamatabuba on Ноябрь, 24, 2012 08:30 (UTC)
В общем сейчас состояние разработки такое: измерительный сектор передаёт в процессор массив точек(текущую поверхность). С некоторым отступом от самых нижних впадин делается "сечение", в которое попадают области разного материала, пустоты. Из точек восстанавливаются несколько контуров и она как бы является "картой", на которой можно планировать заполнение этих контуров.
Текущая метафора такова: над этой картой летит строй бомбардировщиков!
Сперва волна бомбардировщиков с большими бомбами, которые оставляют большое пятно (оно вычитается из контура для следующих бомбардировщиков) - в этот момент запоминается координата, которая посылается в реальное сопло, которое эту операцию должно исполнить.
Затем проходит вторая волна - с меньшим диаметром следа - и т.д. пока все не пройдут и поверхность окажется в обсновном "забомблена".

Затем цикл повторяется. Измерение-моделирование момбление- реальное бомбление.

При этом продвижение "строя бомбардировщиков" строго соответствует динамике и геометрии "строя" сопел в разных секторах нанесения.

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

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

Таков в моём текущем понимании процесс проектирования массированного параллельного печатания разными размерами частиц на переменном рельефе с оптимальной по производительности и, одновременно, по точности адаптивной программой.
zewgmazewgma on Ноябрь, 24, 2012 08:54 (UTC)
А летчики знают не только куда бомбить, но и куда попали. Не иначе как у них лазерное наведение, и бомба упавшая в ответ тоже испускает лазерный луч - или закрывает шедший из поверхности враждебной планеты...
matabubamatabuba on Ноябрь, 24, 2012 09:06 (UTC)
Летчики не знают куда попали! Модель строя самолётов прошлась над моделью поверхности и передала координаты реальному строю. Всё. А что получится можно узнать лишь после нового промера поверхности. Ведь поверхность ещё и трёхмерная! Так что представление плоскими фигурами - упрощение. Адекватное, надеюсь)))
zewgmazewgma on Ноябрь, 24, 2012 09:57 (UTC)
В учебнике топологии в основном трехмерные рассматриваются вообще
matabubamatabuba on Ноябрь, 24, 2012 10:03 (UTC)
Даже если частица представляет собой правильный шар, то невозможно сказать, как его размажет при ударе о поверхность, поэтому важно, во первых, прекратить моделировать и предсказывать всё равно непредсказуемое на возможно менее затратном этапе, а во-вторых - одним ударом разделяться с проблемой, введя обратную связь - измерение!
zewgmazewgma on Ноябрь, 24, 2012 13:59 (UTC)
а я не про частицы говорю что они трехмерные,а про создающуюся на принтере модель
matabubamatabuba on Ноябрь, 24, 2012 14:05 (UTC)
Тогда совсем не могу понять комментария.
zewgmazewgma on Ноябрь, 24, 2012 14:43 (UTC)
где гарантия, что будет ровно слой за слоем? когда будут оставаться ямы и колдобины, которые потом заполнятся следующими бомбами?
matabubamatabuba on Ноябрь, 24, 2012 23:56 (UTC)
Когда есть возможность померить нет нужды делать ровные слои, каковая необходимость и ограничивает современные системы печати. Измеряя же результат мы можем если в прошлом цикле не получилось, забросать ямы в следующем цикле, причем в приоритетном порядке.
Такая адаптивная система система допускает неточности и условность представления (двухмерный контур вместо трехмерной поверхности при проектировании прохода в цикле), ошибки, поломки.
matabubamatabuba on Ноябрь, 25, 2012 01:47 (UTC)
повторения
ГГГГ)))
zewgmazewgma on Ноябрь, 24, 2012 07:58 (UTC)
я думаю, не максимум от оси, а ось от максимума :) где вторая производная равна нулю, там точка перегиба, так? Через нее локальную ось, а вернее, нормаль.
zewgmazewgma on Ноябрь, 24, 2012 08:01 (UTC)
ну или заранее согласиться на попеременное проведение оси абсцисс в нескольких направлениях по очереди. Компьютеру-то что, он их хоть сотню проведет и посчитает.