powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вопрос по поводу алгоритма
45 сообщений из 45, показаны все 2 страниц
Вопрос по поводу алгоритма
    #39848200
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте!

На холсте есть совокупность отрезков (серые линии). Нужно определить, если ли набор пересекающихся отрезков, которые образуют замкнутую фигуру (синие линии). Нужно разобраться, как написать такой алгоритм. С алгоритмом пересечения отрезков я разобрался. Дальше разобраться как искать эту фигуру из пересекающихся точек, потом замкнута ли она. Какие варианты замкнутости присутствуют на холсте. Подскажите, какой раздел из теории надо изучать, чтобы написать такой алгоритм. Реализую на C#.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848206
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Строим граф, где вершины - отрезки, а ребра - точки пересечения, и ищем в нем циклы.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848207
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из простых:
1) найти все точки пересечения
2) Просматривать "в глубину" (на деле что-то вроде комивояжера): идти от первой точки по отрезку до следующей. Дальше, перейдя с точки на отрезок, который ее породил - пройтись по всем точкам этого отрезка, и так далее до тех пор, пока не вернешься в исходную точку.

Вопрос лишь в другом.
Если пересечений будет много, то сложнее будет найти самую крупную фигуру...
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848227
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk, покажи как ты разобрался с пересечением отрезков.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848236
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Красишь все белые точки холста от любой белой точки его границы. Замкнутые области останутся белыми...
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848251
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ничего не сказано о возможном пересечении фигур из отрезков - нет такого или есть пересечения.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848265
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848278
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?
А это разве не две соседних фигуры, пусть и имеющих общую точку?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848282
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может так.

Это надо оговорить в условии.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848295
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonferzmikk, покажи как ты разобрался с пересечением отрезков.Общая логика такова:

Отрезок это часть прямой. Уравнение прямой:
A * x + b = y

C двумя прямыми получаем систему уравнений:
A1 * x + b1 = y
A2 * x + b2 = y

Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848307
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНичего не сказано о возможном пересечении фигур из отрезков - нет такого или есть пересечения.На данный момент в условии задачи пересечении фигур - нет. Но потом думаю возможно будет, когда задача будет усложняться.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848308
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?Нет перекрученных фигур.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848309
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Определение последовательности отрезков (пути по отрезкам) похоже на работу навигатора по улицам
- как лучше проехать, и где проехать.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848312
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikkmaytonferzmikk, покажи как ты разобрался с пересечением отрезков.Общая логика такова:

Отрезок это часть прямой. Уравнение прямой:
A * x + b = y

C двумя прямыми получаем систему уравнений:
A1 * x + b1 = y
A2 * x + b2 = y

Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.
А числа у тебя целые или вещественные?

Я почему это спрашиваю. Инженерная графика - хитрая наука. И было-бы неплохо
не выдавливать из тебя информацию по крошкам. А получить сразу твой сорц на сишарпе.
И вместо доделать. Это будет в духе sql.ru.

Ты согласен?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848372
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonА числа у тебя целые или вещественные?В начале задавал int, потом double.
Я почему это спрашиваю. Инженерная графика - хитрая наука.Изучаю C# и геометрическую графику. Читаю Шилдта. Экспериментирую пока. До самой инженерной графики не доходил еще. Но чую с графикой не так все просто.
И было-бы неплохоне выдавливать из тебя информацию по крошкам. А получить сразу твой сорц на сишарпе. И вместо доделать. Это будет в духе sql.ru. Ты согласен?Именно по пересечению отрезков?

Пока написал для двух отрезков. Если находил, то закрашивал эту точку. Экспериментировал пока так. Часть кода для определения точки пересечении брал отсюда . Там в основном как функция, которая определяет пересекаются ли два отрезка или нет. А также дополнил код, что определяет точки пересечения, если пересекаются. Дополнил код для разных случаев:
- Если два отрезка вертикальные, лежат на одном X, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка горизонтальные.
- Если два отрезка горизонтальные, лежат на одном Y, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка диагональные, но параллельные, пересекаются - возвращает диагональное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.

Под свои задачи добавил:
- Sctruct, где присутствует вся информация об двух отрезках: не только точки пересечения, но и характер пересечении.
- Вывод на Panel. Рисуются два отрезка и если есть точка пересечения, то закрашивает эту точку.
- Для проверки расчетных точек пересечения использовал метод panel1_MouseMove.
- Начало координат идет слева сверху, а надо с учетом слева снизу.

Пока еще все сыро, экспериментирую. Возможно что то лишнее есть, а что то надо добавить.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848374
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovОпределение последовательности отрезков (пути по отрезкам) похоже на работу навигатора по улицам
- как лучше проехать, и где проехать.Теория графов?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848387
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ferzmikk Дополнил код для разных случаев:
Какие случаи?ferzmikkC двумя прямыми получаем систему уравнений:
A1 * x + b1 = y
A2 * x + b2 = y
Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.Имея решение пересечения,
необходимо сравнить это решение на попадание координат решения в диапазон по Х и в диапазон по Y обоих отрезков.
И всё...
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848539
vas0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk,

Для проверки на пересечение двух отрезков: A1 - A2, B1 - B2, достаточно чтобы точки A1 и A2 лежали по разную от отрезка b, а точки B1 и B2 по разную сторону отрезка a. По разную сторону, это значит определитель соотвествующий матрицы дает разные знаки.

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

ЗЫ Это все что вспомнил из университетского курса 15 летней давности.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848552
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шилдта не читай. Он не в теме.

Читай Шикин и Боресков - Комьютерная графика.
Читай Computer Graphics - Donald Hearn

автор
Код: sql
1.
A * x + b = y 


Это школьное уравнение прямой описывает зависимости y=f(x)
но не может описать прямую параллельную оси OY. Для этого нужно оперировать
бесконечностями или переворачивать формулу. Когда будешь писать код - переворачивать
формулу - означает реализовывать 2 разных алгоритма.

Для геометрии на плоскости используются следующие формы задания прямой.

1. В векторном виде.
(x-x1) / (x2 -x1) = (y-y1) / (y2-y1)

2. Каноническое
Ax + By + C = 0

3. Полярные координаты.
xcos(fi) + ysin(fi) - p = 0

(в полярных греческое "ро" есть расстояние от перпендикуляра прямой к центру координат и угол фи - соотв. угол
вращения прямой вокруг системы).

И есть способы перехода от одной формы к другой. Все три формы используются в зависимости от удобства
или ситуации.

В твоей задаче надо проверить на параллельность прямых. Это равенство угловых коэффициентов.
И решить что делать с наложением двух отрезков. Или принять решение о том что пересечения нет.
+Задача упрощается построением выпуклого boundinx box вокруг четырех точек. Это упрощает
поиск и не надо искать его на бесконечно больших числах.

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

Вообще. Для всех серъезных приложений инженерной графики проверка на совпадение вещественных
координат - это почти всегда попадение в выпуклую облочку размера эпсилон по отношению с другому
объекту. Например - точка попадает в окружность (другую точку). Или точка попадает в овал (окрестность
вокруг отрезка). Игры с погрешностями и окрестности - это основная сложность подобных алгоритмов
если решать их в вещественных числах.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848596
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovferzmikk Дополнил код для разных случаев:
Какие случаи?ferzmikkДополнил код для разных случаев:
- Если два отрезка вертикальные, лежат на одном X, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка горизонтальные.
- Если два отрезка горизонтальные, лежат на одном Y, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка диагональные, но параллельные, пересекаются - возвращает диагональное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848597
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonШилдта не читай. Он не в теме.Шилдта читаю не для графики, а для изучения C#.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848883
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vas0ferzmikk,

Для проверки на пересечение двух отрезков: A1 - A2, B1 - B2, достаточно чтобы точки A1 и A2 лежали по разную от отрезка b, а точки B1 и B2 по разную сторону отрезка a. По разную сторону, это значит определитель соотвествующий матрицы дает разные знаки.Не проще ли проверить так: найденные параметры А1 и B1, а также А2 и В2 подставить рассчитанный х и сравнить полученный Y для обоих уравнений?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848902
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЧитай Шикин и Боресков - Комьютерная графика.Это же для 3D Studio Max.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39848911
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikkmaytonЧитай Шикин и Боресков - Комьютерная графика.Это же для 3D Studio Max.
Зачем выдумки выдумывать? Почитай сначала.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850038
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Берешь любую линию (которые у тебя в массиве), ищешь, что с ней пересеклось. Так же делаешь для второй (т.е. ищешь какую то третью, которая пересеклась со второй).
Запоминаешь эти линии, которые в твоей цепочке.
Для каждой последующей , исключая предыдущую (не ПЕРВУЮ а предыдущую) смотришь не пересеклась ли она с чем-то уже пройденным начиная от первой. Раз пересеклась - имеешь замкнутую фигуру.

Алгоритм гоняешь с самого начала для уже next from list = дабы найти все замкнутые фигуры.
Там еще граничные всякие случаи погонять надо (как тут остроумно заметили - перекрученную а так же варианты пересечения двух "многоугольников"), но тупой перебор спасет отца российской алгоритмистики.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850410
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока алгоритм вижу из следующих шагов:
1. Получаем заданный набор из n отрезков. Каждый отрезок имеет координаты начала и конца P1(x1,y1) b P2(x2,y2).
2. Из набора отрезков перебираем пересечения с другим отрезками. Находим точки пересечения. Необходимо построить матрицу n*n. В элементе матрицы свойства: ЕстьПересечение , ТочкаПересечение (х,y) .
3. Из матрицы формируем набор (варианты) пересекающихся линией.
4. Определить замкнутость и характер фигуры для каждого варианта.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850411
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шаг 1
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850412
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шаг 2
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850414
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шаг 3
Вариант 1: L1(P1) - L2(P2) - L3(P3) - L4(P4)
Вариант 2: L1(P1) - L2(P2) - L3(P3) - P3(P5) - L6(P5) - L6(P6) - L7 (P7)

1. Правильно ли я начал строить алгоритм? Если где то ошибаюсь или что то не учел, то, пожалуйста, поправьте.
2. На шаге 3 вариант 2 нужно ли придавать значениям к точкам, которые выделены серым цветом?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850415
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Что за галиматься? Зачем тебе нужна матрица? Что она дает по отношению к решаемой задаче?

Промежуточный итог? Самоконтроль?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850513
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Матрицу использую не для того, чтобы потом складывать или умножать на другие матрицы, а для хранения упорядоченного набора пересеченных отрезков, чтобы потом удобнее было искать фигуру.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850538
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk, для поиска пересечений фигур в пространстве обычно делают следующее.
1) Каждую фигуру окружают прямоугольником (BoundingBox).
2) Для всех боксов строят индекс класса QuadTree или R-Tree.

Данный способ используется в картографии и ГИС и позволяет очень быстро искать пересечения тысячей миллионов
и миллиардов геометрических объектов. Но в твоём случае сойдет и полный перебор. Или простая прямоугольная сетка
если надо чуть-чуть ускориться.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850573
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
авторДля всех боксов строят индекс класса QuadTree или R-Tree.
что-что? Индекс класса? Такого даже гугл не знает, я сначала на свою неосведомленность подумал.

Зачем баунды для отрезков? Если проще через арифметику?

Ничего не понял вобщем.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850584
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А забей. Если не слыхал то и не надо.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850596
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задумался я свой вариант на псевдо яве написать.
И.... засел на два часа в онлайн редакторе каком то.
Сильно не пинайте, но вот если кто подскажет как все эти моментики проще делать - буду рад. Пока в голове все сумбурно и спать охота.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
/*Код без проверки, просто заинтересовался как описать свою идею попроще.
Не вышло. Зато я понял что циклы с минимум 3 условиями одновременно - это очень замороченно. 
По идее должен быть более структуированный способ*/

public static void Main (Line [] arrayOfLines)
{
    Line [] linesWithClosing, linesWothoutClosing, currentLinesSet;
    Line line, a,next, previousLine, firstLine;
    
    foreeach line in arrayOfLines{
        currentLinesSet = null;
        previousLine = null;
        firstLine = null;
        
        /*------------------------------------------------
        This block fill only first element in our array
        -------------------------------------------------*/
        a = hasCross (line, null, null, arrayOfLines);
        if (a !=null) 
            {
            currentLinesSet.add (a);
            firstLine=line;
            previousLine = line;    
            }
        else
        {
            arrayOfLines.remove (line)
            //******* EXIT FROM CURRENT ITERATION*****
            continue;
        }
        /*------------------------------------------------
        Now we have frist element in array inititalized variables
        If somebody knows how to refactor this piece of shit
        please help (I mean to many If and Other Cycles) 
        And I have spent 3 bloody hours to organaize this shit in my head
        -------------------------------------------------*/
        next = a; //using "a" from initial check to start CYCLE
        until (next != null)
        {
            next = hasCross (next, previosLine, firstLine, arrayOfLines);
            if (next != null)
            {
                if (next != firstLine)
                {
                    /*ok go with this loop*/
                    currentLinesSet.add (a);
                    previousLine = next;
                    hasCross (next, previosLine, firstLine, arrayOfLines); //Just to find Next Next
                }
                else
                {
                    /*We have found closed lines loop*/
                    next = 0;
                    linesWithClosing.add (currrentSet);
                    break;
                    
                }
            }
        }
    }
    
    Line hasCross{line, firstLineInSet, previousLineInSet, arrayOfLines}
    {
        /* return next Line. NotPrevious! Return Null if no next lines*/
    }
}


...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Какие "моментики" ?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39850634
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В двух словах - цикл на цикле , и куча сквозных переменных в моем решении, которые то меняются в цикле то нет.
Читать мой код даже мне трудно.

То есть вопрос был про стиль описания, а не про алгоритм как таковой, что наверное оффтопик в этой теме.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39852816
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk,
может поздно уже с поучениями)), мои советы дидактические, надеюсь, что не ущемил ни чьи авторские права.

1) В начале топика был дан самый ИМХО полезный совет: построить граф, а на нём искать циклы. Зачем, правда, нужно вместо геометрически очевидного представления строить двойственное?

2) Услышав слово граф, не надо бросаться придумывать всё своё, начиная с представления. Помимо прочей инфы есть в инете актуальная по сю пору книга Липского, Москва, Мир, 1988.
Весь раздел 2, особенно 2.4 и 2.5.,теорема 2.8. В 2.4. есть алгоритм нахождения в связном графе, в 2.5 - для фундаментальных циклов. Надо только быть внимательным (а всё равно ведь отлаживаться), поскольку издание не свободно от опечаток.
Вот тогда уже, после изучения основ, можно пытыться для тренировки их все реализовать без подсказок.

3) Задача распадается на независимые составляющие, имхо очевидные и рутинные, если не учитывать оптимизации:
а) найти все геометрические тт пересечения;
пересечения (и тождественность) определять с точностью до эпсилон, как следствие некоторые участки отрезков могут "совпасть";

б) сформировать граф, он м.б. несвязным, нахождение компонент сязности в Липском не представлено. Каой груф? Нуууу, наверное неориентированный;

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

г) "Вторичные" циклы, если нужны, формируются комбинациями фундаментальных, раздел 2.5.

4) После этого можно оптимизировать.

Ну то есть я вообще не вижу проблем кроме как в оптимизациях.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855709
Serge_987654321
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
1) Найти точки пересечения и в этих точках разбить исходные отрезки на более мелкие
2) Из полученного множества отрезков, которые уже ни с чем не пересекаются, а могут только иметь обшие граничные точки,
удалить отрезки, у которых граничная точка принадлежит только одному отрезку.
3) Повторять пока есть такие отрезки
То что осталось - образует замкнутые кривые
В них можно элементарно найти "минимальные" замкнутые области проходом по отрезкам в одном направлении с поворотом направо,
т.к у каждого оставшегося отрезка не более двух таких областей - срава и слева.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855865
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я знаю секрет этого форума.
Пока никто не запостит прототип кода - ничего не будет.
Теоретики будут выдвигать самые смелые теории.
А автор и ныне топчется не старте.

Ну. У кого есть прототип на C#?
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855882
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
у меня есть прототип на VBA (я бы сказал на барсике). Да он у всех есть, в разделе МС-офис декабрь 2014 - январь 2015
тама конечно же не один в один, но пересечения отрезков и поиск пути между вершинами есть. Тема была в названии расширение автокад-файлов, что-то типа DVG, а в тексте про разветвлённую сеть коридоров.
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855883
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А выше мой совет по данному топику самый полный и самый научный - фактически уже готовое ТЗ, не надо никаких велосипедов, даже готовых библиотек не требуется.
(без оптимизаций, разумеется)
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855915
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для "замкнутости", нужны отрезки имеющий минимум два пересечения.
Осталось найти среди них "повторы"
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855916
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Или рекурсией убрать из пересечений отрезки, не имеющий двух пересечений (концы)
Если что останется - то и есть замкнутая кривая
...
Рейтинг: 0 / 0
Вопрос по поводу алгоритма
    #39855917
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ знаю секрет этого форума.
Пока никто не запостит прототип кода - ничего не будет.
Теоретики будут выдвигать самые смелые теории.

Совершенно верное замечание.
И единственно правильная методика поведения.
...
Рейтинг: 0 / 0
45 сообщений из 45, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вопрос по поводу алгоритма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]