Re: Алгоритм, геометрия.

Помойму разумно.

Re: Алгоритм, геометрия.

Рисуем описанную окружность по 3 точкам, масштабируем и получаем новые координаты через соотношение радиусов. С т.з. матана - давно это было, нужно подумать =)

Re: Алгоритм, геометрия.

Берем три последовательные вершины (против часовой стрелки) A,B,C. Нам нужно найти B'. Берем векторы u=BA, v=BC, w=BB'. Мы знаем, что |w|sin<(u,w) = |w|sin<(v,w) = d. С другой стороны u x w = |u||w|sin<(u,w), то есть имеем u x w = d|u| и v x w = d|v|, что просто 2 линейных уравнения для координат w.

Re: Алгоритм, геометрия.

ты о чем, куда мы ее масштабировать будем?

Re: Алгоритм, геометрия.

рёбра сдвигать, и находить их пересечения. Есть, правда, проблема с определением направления.

типа:

ребро: P = a * t + b (a, b -- векторы)

c -- вектор перпендикулярный a, |c| == delta

новое ребро

P = a * t + (b + c)

c можно найти из системы

(a , c) == 0 (перпендикулярны) |c| == delta

у нее, правда, два решения, но тут без дополнительных условий ИМХО никак.

Re: Алгоритм, геометрия.

Уравнение прямой, к которой принадлежит любая из сторон, можно однозначно задать в виде (a, r) = C, где r - радиус-вектор, a - вектор единичной длины, направленный наружу перпендикулярно отрезку, а C - некая константа, определаемая из предыдущего (находится подстановкой в уравнения любой точки прямой). Уравнение прямой, сдвинутой на дельту наружу, есть (a, r) = C + дельта. Таким образом находим уравнения всех новых сторон и координаты точек их пересечения.

Минус - придётся считать квадратные корни. Но насколько я понимаю, это лучше, чем тригонометрия.

(a, b) - скалярное произведение векторов a и b, если кто не понял.

Re: Алгоритм, геометрия.

> ... a - вектор единичной длины, направленный _наружу_ перпендикулярно отрезку ...

вот с этим _наружу_ и проблемка...

Вот если бы многоугольник был выпуклый... но даже на приведённой иллюстрации он не такой...

Re: Алгоритм, геометрия.

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

Рассказать что ли, как автоматически определить направление наружу для многоугольника, если мы точно знаем, что стороны не пересекаются? Или как проверить, что они не пересекаются? :)

Re: Алгоритм, геометрия.

> Рассказать что ли...

из того, что пришло в голову:

найти такое ребро, для которого все вершины находятся по одну сторону...

угадал?

Re: Алгоритм, геометрия.

Зачем такие сложности, найти вершину с максимальной координатой x или y, а дальше разберёмся, учитывая этот факт...

Re: Алгоритм, геометрия.

> ... вершину с максимальной координатой...

... при условии, что известно направление обхода. ;)

Re: Алгоритм, геометрия.

Чего? Тебе готовую программу что ли написать? :)

Re: Алгоритм, геометрия.

> Тебе готовую программу что ли написать? :)

Не стоит... Мне оно не надо. ;)

Re: Алгоритм, геометрия.

Первое, что пришло в голову - это построить 2 окружности с центрами в точках многоугольника и найти к ним касательную, но проблем на этом пути много...

Re: Алгоритм, геометрия.

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

Re: Алгоритм, геометрия.

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

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

Думаю, он же будет единственным верным.

Вот только с направлениями "наружу-внутрь" не все понятно. Может все-таки объясните в общих чертах, как это можно сделать?

Re: Алгоритм, геометрия.

Кстати, совсем не обязательно, что в результате такого преобразования получится полигон. Можно получить, например, "бублик" - фигуру, ограниченную внешним и внутренним контурами. Думаю, это слегка усложнит построение (заранее неизвестно даже количество вершин у новой фигуры).

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

Re: Алгоритм, геометрия.

Да - см. мой пост

Re: Алгоритм, геометрия.

>Да - см. мой пост

Это все никак не учитывает формы многоугольника. Если построить B'' по другую сторону ABC, то все эти соотношения точно так же будут выполняться.

Re: Алгоритм, геометрия.

>Да - см. мой пост

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

Re: Алгоритм, геометрия.

учимся читать: "Берем три последовательные вершины (против часовой стрелки) A,B,C"

Re: Алгоритм, геометрия.

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

Re: Алгоритм, геометрия.

Ну да, действительно непонятно, что же означает направление "против часовой стрелки". Что мы вращаем и вокруг чего?

Re: Алгоритм, геометрия.

$ляяаааааа

на рисунке вершины 1,2,3 идут по часовой стрелке, а 3,2,1 - против.

Re: Алгоритм, геометрия.

>учимся читать: "Берем три последовательные вершины (против часовой стрелки) A,B,C"

И что?

http://www.webfile.ru/1116690

Имхо ананимус прав.

Re: Алгоритм, геометрия.

Для каждой стороны находим:

- вектор смещения Vi длиной дельта и направлением, перпендикулярным стороне, в направлении "наружу".

- уравнение прямой, на которой сторона

- из предыдущих получаем уравнение прямой, на которой будет "смещённоя" сторона

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

Направление "наружу" можно натти из факта, чё любая полупрямая, начало которой есть на вершине, в направлении "наружу" пересечёт стороны 0 или чётное число раз, а "внутрь" - 1 или нечётное.

Сплошная линейная алгебра и никаких синусы/косинусы/корешки.

Re: Алгоритм, геометрия.

еще один в школе не учился
подсказка1: прочитай, что такое векторное произведение на плоскости.
подсказка2: у тебя на картинке <(u,w) не равно альфа.

Re: Алгоритм, геометрия.

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

"корешки" в конечном ответе будут (вылезут они на твоем первом шаге)

Re: Алгоритм, геометрия.

вобщем, да, согласен со всеми поправками.

Re: Алгоритм, геометрия.

grob, это еще вопрос, кто тут школу прогуливал.

Во-первых, замечание насчет <(u,w) и альфа. Глупость какая-то.

Во-вторых, само решение:

>... С другой стороны u x w = |u||w|sin<(u,w)

Очевидно, что u x w != |u||w|sin<(u,w) тк это вектор. |u||w|sin<(u,w) = |u x w|. А теперь сюрприз: |u x w| = |u x (-w)|, о чем тут уже не раз говорили.

В общем, либо вы неправильно описали решение, либо не обращаете внимания на очевидные вещи.

Определив направление обхода, действительно можно выбрать правильное направление BB', но у вас это замалчивается.

Мой вариант:

Для трех последовательных вершин A, B, C определяем направление обхода в образованном ими треугольнике. Если оно совпадает с направлением обхода контура полигона, то B' выбирается таким, чтобы луч BB' не пересекал AC, и наоборот.

Re: Алгоритм, геометрия.

специально для anonymous экскурс в школьную программу

в 3d u x w - это конечно вектор, он перпендикулярен плоскости u и w, но так как плоскость у нас одна, то направление u x w задается знаком. Поэтому на плоскости как правило определяют (a,b) x (c,d) = ad - bc, так оно впервые преподносится в школе. Кроме того u x w = |u||w|sin<(u,w). Также в школе рассказывают, что <(u,w) - направленный угол.

кто следующий мне будет заливать, что я - верблюд?

Re: Алгоритм, геометрия.

Да вы что ребята, на Линейную Алгебру в универе не ходили? ;)

Элементарная задача. Находишь уравнения прямых, сдвинутых на $\delta$, потом находишь точки пересечения этихпрямых это и будет ответом.

Уравнения прямых находятся сразу же, т.к. нам дан направляющий вектор, а дополнительную точку получим прибавляя к вершине, данной в исходном нормальный вектор, длиной $\delta$

Re: Алгоритм, геометрия.

какая линейная алгебра, тут у людей проблемы с "против часовой стрелки"