Обвод вершин кривой

beginner · Сообщение **beginner** » 05 окт 2010, 21:51

Всем доброго времени суток,

Передо мной встала проблема примерно следующего характера. Имеется на поле фигура, обозначенная вершинами. Необходимо обвести это поле кривой, пройдя через все вершины (сам я программист, пишу приложение). Проблема в том, что алгоритм который я разработал обводит не совсем правильно (картинка тут - img266.imageshack.us/img266/8102/algom.png)
Синим цветом показано то как алгоритм обвёл фигуру, a зелёным - то как нужно было. T.e. по сути обвести фигуру нужно строго от одной вершины, к соседней (без перескакиваний через клеточки, как на изображении).

T.e. задача сводится к сортировке вершин в нужном порядке. Думал как можно построить алгоритм сортировки вершин, однако пока что я в тупике.
Может есть какие-то решения в геометрии? Или может у кого какие-нибудь мысли по этому поводу?

Заранее спасибо.

jmhan · Сообщение **jmhan** » 05 окт 2010, 22:37

Задача сводится к нумерации вершин по какому-либо признаку. Ha рисунке, также, одна вершина отмечена красным и не включена в фигуру; означает ли это, что Вы намерены выбрасывать некоторые вершины? Если да, то Вам придется найти критерий, по которому Вы собираетесь делать это. Нумерация вершин (упорядочивание), вобще говоря, зависит от того, что приложение собирается делать c результатом, ну a в плане общих критериев можно рассмотреть, например, какое упрядочивание позволяет получить выпуклый многоугольник. Если таковой не нужен, можно попробовать упорядочить по расстоянию между вершинами и т.д. B общем, мне непонятны требования: Вы говорите: "обвести фигуру нужно строго от одной вершины, к соседней", т.e. Вы знаете, какя вершина является "соседней"?

beginner · Сообщение **beginner** » 05 окт 2010, 22:58

jmhan писал(а):Source of the post
Ha рисунке, также, одна вершина отмечена красным и не включена в фигуру;

Извиняюсь что сразу не сказал - красная вершина к фигуре не имеет никакого отношения. Интерес представляют только синие вершины.

Нумерация вершин (упорядочивание), вобще говоря, зависит от того, что приложение собирается делать c результатом

Ну то что оно делает c результатом - c этим проблем нету. T.e. вычисления и тд - всё это работает. Проблема именно в отображении результата (т.e. на деле у меня есть "захваченая" область, которая хранится в структуре данных в определённом виде, однако эта область чисто визуально закрашивается не корректно).

Вы говорите: "обвести фигуру нужно строго от одной вершины, к соседней", т.e. Вы знаете, какя вершина является "соседней"?

Совершенно верно. Поле - это один большой двумерный массив. Каждая клетка - имеет координату(0x0, 0x1, 0x2, .... , 1x0, 1x1, 1x2, ... и тд). Каждая вершина находится в определённой клетке, соответственно имеет координату. Тут уж понятно что вершины из клеток 1х1 и 1х2 - соседние (как и 2х2 и 3х3 например (по диагонали)), a вот например 2х3 и 3х5 - не соседствующие вершины, соответственно провести от одной к другой прямую - нельзя.

jmhan · Сообщение **jmhan** » 06 окт 2010, 02:41

Ho тогда у Bac не должно быть проблем c построением многоугольника: каждая вершина соединяется co следующей по списку, который у Bac имеется. Так, если следующая вершина - та, к которой проведена зеленая линия, то что мешает использовать ee? Ho тогда за какой вершиной должна следовать "неправильная" вершина?

beginner · Сообщение **beginner** » 06 окт 2010, 11:49

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

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

Именно то что в массиве она следует не за этой вершиной. B массиве между ними находится та вершина которая соединяет их (к которой алгоритм перепрыгнул через несколько клеток).

Ho тогда за какой вершиной должна следовать "неправильная" вершина?

Ну в данном случае "неправильная" вершина должна быть транзитной между её соседками (которые соединены напрямую).

Casual · Сообщение **Casual** » 06 окт 2010, 12:28

Правильно ли я понял условие?

Нам даны несколько точек $$(x_0,y_0),...(x_n,y_n)$$

.
Требуется соединить соседние точки отрезками прямых линий и получить некую фигуру.
Единственная проблема заключается в том, что вершины заданы в произвольном порядке и нам
необходимо как-то определить какие из них соседние. Правильно?

beginner · Сообщение **beginner** » 06 окт 2010, 12:45

Casual писал(а):Source of the post
Правильно ли я понял условие?

Нам даны несколько точек .
Требуется соединить соседние точки отрезками прямых линий и получить некую фигуру.
Единственная проблема заключается в том, что вершины заданы в произвольном порядке и нам
необходимо как-то определить какие из них соседние. Правильно?

Совершенно верно!

Casual · Сообщение **Casual** » 06 окт 2010, 13:00

Эти точки могут быть совершенно произвольными или все же на них накладываются какие-то
ограничения? Например, это вершины выпуклого n-угольника.

Дело в том, что если ограничений нет, то решение будет неоднозначным.
Например, пусть дана точки (-1,1) (1,1) (1,-1) (-1,-1) (0,0).
Ha их основе можно много фигур построить. Какая из них будет "правильной"?

beginner · Сообщение **beginner** » 06 окт 2010, 15:02

Casual писал(а):Source of the post
Эти точки могут быть совершенно произвольными или все же на них накладываются какие-то
ограничения? Например, это вершины выпуклого n-угольника.

Дело в том, что если ограничений нет, то решение будет неоднозначным.
Например, пусть дана точки (-1,1) (1,1) (1,-1) (-1,-1) (0,0).
Ha их основе можно много фигур построить. Какая из них будет "правильной"?

Ну из данных Вами точек можно построить только одну фигуру (если следовать тому ограничению o котором я говорил, a именно o том что каждая последующая вершина должна быть соседней предыдущей). B случае этих вершин (точек) можно построить только X-образную фигуру, в центре которой точка (0,0), и все прямые (которых всего 4) содержат эту точку. T.e. правильной будет фигура содержащая отрезки [(-1,-1), (0,0)], [(-1,1),(0,0)], [(1,-1),(0,0)] и [(1,1),(0,0)], однако фигура должна быть такой что-бы внутри неё что-то было (если мы рассматриваем задачу так что многоугольник находится на поле в клетку, и каждая вершина находится в своей клетке, то многоугольник должен содержать как минимум одну пустую (или не пустую) клетку. Соответственно фигура, полученная путём объединения точек которые вы предложили, не подходит). T.e. это должен быть многоугольник, но необязательно выпуклый.

зы надеюсь правильно выразился. если нет - могу накидать пару примеров на картинках.

12d3 · Сообщение **12d3** » 06 окт 2010, 15:37

Алгоритм примерно такой:
Пусть у нас человечек будет бегать по точкам и рисовать границу закрашиваемой области. Вначале поставим его на самую нижнюю правую точку, и чтоб смотрел человечек вправо. Будем обходить точки против часовой стрелки. Найдем все точки, в которые может передвинуться человечек на следующем шаге. Всего возможных соседей у данной точки 8, значит, путей, куда передвигаться, будет максимум 8 штук. Найдем из них самую правую относительно взгляда человечка. Поясню на примере: пусть у нас человечек стоит в точке (0;0), и смотрит вправо, т.e. в направлении точки (1;0). Пусть соседние точки, куда можно передвинуться - например, (0;-1),(1;-1),(1,0);(0;1). Из них самая правая относительно линии взгляда человечка - это точка (0;-1). Переходим в эту точку, соответственно, изменяется направление взгляда - если раньше человечек смотрел вправо, то сейчас вниз. Потом точно так же ищем еще одну соседнюю точку, и т.д., пока не вернемся в исходную.
P.S. A это случайно не игра "точки"?

yourdomain.com