Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
Здравствуйте!

На холсте есть совокупность отрезков (серые линии). Нужно определить, если ли набор пересекающихся отрезков, которые образуют замкнутую фигуру (синие линии). Нужно разобраться, как написать такой алгоритм. С алгоритмом пересечения отрезков я разобрался. Дальше разобраться как искать эту фигуру из пересекающихся точек, потом замкнута ли она. Какие варианты замкнутости присутствуют на холсте. Подскажите, какой раздел из теории надо изучать, чтобы написать такой алгоритм. Реализую на C#.

К сообщению приложен файл. Размер - 7Kb
12 авг 19, 11:46    [21946970]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
wst
Member

Откуда:
Сообщений: 206
Строим граф, где вершины - отрезки, а ребра - точки пересечения, и ищем в нем циклы.
12 авг 19, 11:52    [21946980]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59112
Из простых:
1) найти все точки пересечения
2) Просматривать "в глубину" (на деле что-то вроде комивояжера): идти от первой точки по отрезку до следующей. Дальше, перейдя с точки на отрезок, который ее породил - пройтись по всем точкам этого отрезка, и так далее до тех пор, пока не вернешься в исходную точку.

Вопрос лишь в другом.
Если пересечений будет много, то сложнее будет найти самую крупную фигуру...
12 авг 19, 11:52    [21946981]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
ferzmikk, покажи как ты разобрался с пересечением отрезков.
12 авг 19, 12:15    [21947011]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 19590
Красишь все белые точки холста от любой белой точки его границы. Замкнутые области останутся белыми...
12 авг 19, 12:29    [21947027]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Ничего не сказано о возможном пересечении фигур из отрезков - нет такого или есть пересечения.
12 авг 19, 12:44    [21947048]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
В задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?
12 авг 19, 13:01    [21947073]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59112
mayton
В задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?

А это разве не две соседних фигуры, пусть и имеющих общую точку?
12 авг 19, 13:21    [21947102]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Может так.

Это надо оговорить в условии.
12 авг 19, 13:28    [21947108]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
mayton
ferzmikk, покажи как ты разобрался с пересечением отрезков.
Общая логика такова:

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

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

Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.
12 авг 19, 13:45    [21947129]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
Gennadiy Usov
Ничего не сказано о возможном пересечении фигур из отрезков - нет такого или есть пересечения.
На данный момент в условии задачи пересечении фигур - нет. Но потом думаю возможно будет, когда задача будет усложняться.
12 авг 19, 13:55    [21947149]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
mayton
В задаче еще не сказано о перекручненных фигурах (образуют восьмёрку).

Как с ними быть? Считать из замкнутыми?
Нет перекрученных фигур.
12 авг 19, 13:56    [21947150]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Определение последовательности отрезков (пути по отрезкам) похоже на работу навигатора по улицам
- как лучше проехать, и где проехать.
12 авг 19, 14:00    [21947155]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
ferzmikk
mayton
ferzmikk, покажи как ты разобрался с пересечением отрезков.
Общая логика такова:

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

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

Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.

А числа у тебя целые или вещественные?

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

Ты согласен?
12 авг 19, 14:06    [21947162]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

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

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

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

Пока еще все сыро, экспериментирую. Возможно что то лишнее есть, а что то надо добавить.
12 авг 19, 15:42    [21947277]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
Gennadiy Usov
Определение последовательности отрезков (пути по отрезкам) похоже на работу навигатора по улицам
- как лучше проехать, и где проехать.
Теория графов?
12 авг 19, 15:44    [21947281]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
ferzmikk
Дополнил код для разных случаев:
Какие случаи?
ferzmikk
C двумя прямыми получаем систему уравнений:
A1 * x + b1 = y
A2 * x + b2 = y
Находим A1, A2, b1 и b2. Потом получаем точки пересечения x и y.
Имея решение пересечения,
необходимо сравнить это решение на попадание координат решения в диапазон по Х и в диапазон по Y обоих отрезков.
И всё...
12 авг 19, 15:57    [21947303]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
vas0
Member

Откуда: Таможенный союз (Россия, Казахстан)
Сообщений: 1288
ferzmikk,

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

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

ЗЫ Это все что вспомнил из университетского курса 15 летней давности.
12 авг 19, 22:18    [21947568]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Шилдта не читай. Он не в теме.

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

автор
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 вокруг четырех точек. Это упрощает
поиск и не надо искать его на бесконечно больших числах.

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

Вообще. Для всех серъезных приложений инженерной графики проверка на совпадение вещественных
координат - это почти всегда попадение в выпуклую облочку размера эпсилон по отношению с другому
объекту. Например - точка попадает в окружность (другую точку). Или точка попадает в овал (окрестность
вокруг отрезка). Игры с погрешностями и окрестности - это основная сложность подобных алгоритмов
если решать их в вещественных числах.
12 авг 19, 23:08    [21947586]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
Gennadiy Usov
ferzmikk
Дополнил код для разных случаев:
Какие случаи?
ferzmikk
Дополнил код для разных случаев:
- Если два отрезка вертикальные, лежат на одном X, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка горизонтальные.
- Если два отрезка горизонтальные, лежат на одном Y, пересекаются - возвращает вертикальное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
- Если оба отрезка диагональные, но параллельные, пересекаются - возвращает диагональное пересечение. Нужно еще добавить, чтобы возвращал начала и конец пересечения.
13 авг 19, 08:17    [21947656]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
mayton
Шилдта не читай. Он не в теме.
Шилдта читаю не для графики, а для изучения C#.
13 авг 19, 08:20    [21947658]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
vas0
ferzmikk,

Для проверки на пересечение двух отрезков: A1 - A2, B1 - B2, достаточно чтобы точки A1 и A2 лежали по разную от отрезка b, а точки B1 и B2 по разную сторону отрезка a. По разную сторону, это значит определитель соотвествующий матрицы дает разные знаки.
Не проще ли проверить так: найденные параметры А1 и B1, а также А2 и В2 подставить рассчитанный х и сравнить полученный Y для обоих уравнений?
13 авг 19, 16:25    [21948310]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
mayton
Читай Шикин и Боресков - Комьютерная графика.
Это же для 3D Studio Max.
13 авг 19, 16:42    [21948341]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
ferzmikk
mayton
Читай Шикин и Боресков - Комьютерная графика.
Это же для 3D Studio Max.

Зачем выдумки выдумывать? Почитай сначала.
13 авг 19, 16:54    [21948361]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос по поводу алгоритма  [new]
АСУ ТПшник
Member

Откуда:
Сообщений: 805
Берешь любую линию (которые у тебя в массиве), ищешь, что с ней пересеклось. Так же делаешь для второй (т.е. ищешь какую то третью, которая пересеклась со второй).
Запоминаешь эти линии, которые в твоей цепочке.
Для каждой последующей , исключая предыдущую (не ПЕРВУЮ а предыдущую) смотришь не пересеклась ли она с чем-то уже пройденным начиная от первой. Раз пересеклась - имеешь замкнутую фигуру.

Алгоритм гоняешь с самого начала для уже next from list = дабы найти все замкнутые фигуры.
Там еще граничные всякие случаи погонять надо (как тут остроумно заметили - перекрученную а так же варианты пересечения двух "многоугольников"), но тупой перебор спасет отца российской алгоритмистики.
15 авг 19, 20:50    [21950498]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить