?

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 и считают методами линейной алгебры
(no subject) - matabuba on Ноябрь, 24, 2012 08:13 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:14 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 08:36 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:56 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:17 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 08:32 (UTC) (Развернуть)
(no subject) - zewgma 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)
первые производные возьми :)


Мне казалось, что он должен быть, и как раз в топологии...
(no subject) - matabuba on Ноябрь, 24, 2012 08:01 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:03 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 08:09 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:15 (UTC) (Развернуть)
zewgmazewgma on Ноябрь, 24, 2012 07:54 (UTC)
а как ты узнаешь, где середина фигуры? если ты даже не знаешь, где она находится?
matabubamatabuba on Ноябрь, 24, 2012 07:58 (UTC)
Почему же не знаю?! Знаю, у меня даже и уравнение в общем случае есть. А можно и тупо поделить координаты габаритов пополам.
Также фигуры в одной системе координат.
(no subject) - zewgma on Ноябрь, 24, 2012 08:00 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 08:01 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:04 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 08:30 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 08:54 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 09:06 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 09:57 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 10:03 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 13:59 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 14:05 (UTC) (Развернуть)
(no subject) - zewgma on Ноябрь, 24, 2012 14:43 (UTC) (Развернуть)
(no subject) - matabuba on Ноябрь, 24, 2012 23:56 (UTC) (Развернуть)
повторения - matabuba on Ноябрь, 25, 2012 01:47 (UTC) (Развернуть)
zewgmazewgma on Ноябрь, 24, 2012 07:58 (UTC)
я думаю, не максимум от оси, а ось от максимума :) где вторая производная равна нулю, там точка перегиба, так? Через нее локальную ось, а вернее, нормаль.
zewgmazewgma on Ноябрь, 24, 2012 08:01 (UTC)
ну или заранее согласиться на попеременное проведение оси абсцисс в нескольких направлениях по очереди. Компьютеру-то что, он их хоть сотню проведет и посчитает.