|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Пока алгоритм вижу из следующих шагов: 1. Получаем заданный набор из n отрезков. Каждый отрезок имеет координаты начала и конца P1(x1,y1) b P2(x2,y2). 2. Из набора отрезков перебираем пересечения с другим отрезками. Находим точки пересечения. Необходимо построить матрицу n*n. В элементе матрицы свойства: ЕстьПересечение , ТочкаПересечение (х,y) . 3. Из матрицы формируем набор (варианты) пересекающихся линией. 4. Определить замкнутость и характер фигуры для каждого варианта. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 15:08 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Шаг 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 нужно ли придавать значениям к точкам, которые выделены серым цветом? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 15:12 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Что за галиматься? Зачем тебе нужна матрица? Что она дает по отношению к решаемой задаче? Промежуточный итог? Самоконтроль? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 15:13 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Матрицу использую не для того, чтобы потом складывать или умножать на другие матрицы, а для хранения упорядоченного набора пересеченных отрезков, чтобы потом удобнее было искать фигуру. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 18:03 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
ferzmikk, для поиска пересечений фигур в пространстве обычно делают следующее. 1) Каждую фигуру окружают прямоугольником (BoundingBox). 2) Для всех боксов строят индекс класса QuadTree или R-Tree. Данный способ используется в картографии и ГИС и позволяет очень быстро искать пересечения тысячей миллионов и миллиардов геометрических объектов. Но в твоём случае сойдет и полный перебор. Или простая прямоугольная сетка если надо чуть-чуть ускориться. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 19:08 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
авторДля всех боксов строят индекс класса QuadTree или R-Tree. что-что? Индекс класса? Такого даже гугл не знает, я сначала на свою неосведомленность подумал. Зачем баунды для отрезков? Если проще через арифметику? Ничего не понял вобщем. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 21:24 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
А забей. Если не слыхал то и не надо. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 22:48 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Задумался я свой вариант на псевдо яве написать. И.... засел на два часа в онлайн редакторе каком то. Сильно не пинайте, но вот если кто подскажет как все эти моментики проще делать - буду рад. Пока в голове все сумбурно и спать охота. Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 23:39 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Какие "моментики" ? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.08.2019, 23:44 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
В двух словах - цикл на цикле , и куча сквозных переменных в моем решении, которые то меняются в цикле то нет. Читать мой код даже мне трудно. То есть вопрос был про стиль описания, а не про алгоритм как таковой, что наверное оффтопик в этой теме. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.08.2019, 09:34 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
ferzmikk, может поздно уже с поучениями)), мои советы дидактические, надеюсь, что не ущемил ни чьи авторские права. 1) В начале топика был дан самый ИМХО полезный совет: построить граф, а на нём искать циклы. Зачем, правда, нужно вместо геометрически очевидного представления строить двойственное? 2) Услышав слово граф, не надо бросаться придумывать всё своё, начиная с представления. Помимо прочей инфы есть в инете актуальная по сю пору книга Липского, Москва, Мир, 1988. Весь раздел 2, особенно 2.4 и 2.5.,теорема 2.8. В 2.4. есть алгоритм нахождения в связном графе, в 2.5 - для фундаментальных циклов. Надо только быть внимательным (а всё равно ведь отлаживаться), поскольку издание не свободно от опечаток. Вот тогда уже, после изучения основ, можно пытыться для тренировки их все реализовать без подсказок. 3) Задача распадается на независимые составляющие, имхо очевидные и рутинные, если не учитывать оптимизации: а) найти все геометрические тт пересечения; пересечения (и тождественность) определять с точностью до эпсилон, как следствие некоторые участки отрезков могут "совпасть"; б) сформировать граф, он м.б. несвязным, нахождение компонент сязности в Липском не представлено. Каой груф? Нуууу, наверное неориентированный; в) для каждой компоненты связности построиьт стягивающее дерево (остов), после чего добавление к нему любого ребра даёт т.н. фундаментальный цикл и (вроде) только один. Очевидно, что после каждого остова, остаются вершины из других компонент связности. Это простейший способ найти их все. г) "Вторичные" циклы, если нужны, формируются комбинациями фундаментальных, раздел 2.5. 4) После этого можно оптимизировать. Ну то есть я вообще не вижу проблем кроме как в оптимизациях. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 15:26 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
1) Найти точки пересечения и в этих точках разбить исходные отрезки на более мелкие 2) Из полученного множества отрезков, которые уже ни с чем не пересекаются, а могут только иметь обшие граничные точки, удалить отрезки, у которых граничная точка принадлежит только одному отрезку. 3) Повторять пока есть такие отрезки То что осталось - образует замкнутые кривые В них можно элементарно найти "минимальные" замкнутые области проходом по отрезкам в одном направлении с поворотом направо, т.к у каждого оставшегося отрезка не более двух таких областей - срава и слева. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.08.2019, 15:18 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Я знаю секрет этого форума. Пока никто не запостит прототип кода - ничего не будет. Теоретики будут выдвигать самые смелые теории. А автор и ныне топчется не старте. Ну. У кого есть прототип на C#? ... |
|||
:
Нравится:
Не нравится:
|
|||
30.08.2019, 20:33 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
у меня есть прототип на VBA (я бы сказал на барсике). Да он у всех есть, в разделе МС-офис декабрь 2014 - январь 2015 тама конечно же не один в один, но пересечения отрезков и поиск пути между вершинами есть. Тема была в названии расширение автокад-файлов, что-то типа DVG, а в тексте про разветвлённую сеть коридоров. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.08.2019, 21:41 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
А выше мой совет по данному топику самый полный и самый научный - фактически уже готовое ТЗ, не надо никаких велосипедов, даже готовых библиотек не требуется. (без оптимизаций, разумеется) ... |
|||
:
Нравится:
Не нравится:
|
|||
30.08.2019, 21:45 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Для "замкнутости", нужны отрезки имеющий минимум два пересечения. Осталось найти среди них "повторы" ... |
|||
:
Нравится:
Не нравится:
|
|||
31.08.2019, 09:22 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
Или рекурсией убрать из пересечений отрезки, не имеющий двух пересечений (концы) Если что останется - то и есть замкнутая кривая ... |
|||
:
Нравится:
Не нравится:
|
|||
31.08.2019, 09:23 |
|
Вопрос по поводу алгоритма
|
|||
---|---|---|---|
#18+
maytonЯ знаю секрет этого форума. Пока никто не запостит прототип кода - ничего не будет. Теоретики будут выдвигать самые смелые теории. Совершенно верное замечание. И единственно правильная методика поведения. ... |
|||
:
Нравится:
Не нравится:
|
|||
31.08.2019, 09:36 |
|
|
start [/forum/topic.php?fid=16&msg=39850596&tid=1339914]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
140ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
others: | 15ms |
total: | 255ms |
0 / 0 |