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

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

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

Берем три последовательные вершины (против часовой стрелки) 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.

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

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

типа:

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

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

новое ребро

P = a * t + (b + c)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

угадал?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$ляяаааааа

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

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

И что?

http://www.webfile.ru/1116690

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

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

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

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

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

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

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

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

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

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

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

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

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, и наоборот.

специально для 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) - направленный угол.

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

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

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

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

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