LINUX.ORG.RU

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


0

0

Даны координаты узлов полигона (черная фигура на рис.)

http://199.203.242.209/~stas-user/lor/origin/picture.png

Надо найти координаты узлов увеличенного на "дельту" полигона (синяя фигура на рис.).

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

Наверное можно проще?

★★★★★

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

RCV ★★★★
()

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

e
()

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

grob ★★★★★
()
Ответ на: комментарий от e

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

grob ★★★★★
()

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

типа:

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

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

новое ребро

P = a * t + (b + c)

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

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

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

k_andy ★★★
()

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

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

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

Teak ★★★★★
()
Ответ на: комментарий от Teak

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

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

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

k_andy ★★★
()
Ответ на: комментарий от k_andy

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

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

Teak ★★★★★
()
Ответ на: комментарий от Teak

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

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

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

угадал?

k_andy ★★★
()
Ответ на: комментарий от k_andy

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

Teak ★★★★★
()
Ответ на: комментарий от Teak

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

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

k_andy ★★★
()

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

saper ★★★★★
()

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

saper ★★★★★
()

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

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

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

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

anonymous
()

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

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

anonymous
()
Ответ на: комментарий от grob

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

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

anonymous
()
Ответ на: комментарий от grob

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

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

anonymous
()
Ответ на: комментарий от grob

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

Teak ★★★★★
()
Ответ на: комментарий от grob

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

anonymous
()
Ответ на: комментарий от anonymous

$ляяаааааа

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

grob ★★★★★
()

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

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

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

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

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

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

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

bugmaker ★★★★☆
()
Ответ на: комментарий от obormot

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

grob ★★★★★
()
Ответ на: комментарий от bugmaker

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

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

grob ★★★★★
()

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
()
Ответ на: комментарий от anonymous

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

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

grob ★★★★★
()

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

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

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

CMEPTb_C_KOCOiiii
()
Ответ на: комментарий от CMEPTb_C_KOCOiiii

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

grob ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.