Войти
РаботаФорумРазовая работа

C# Смещенная кривая (12 стр)

Страницы: 19 10 11 12 13 14 Следующая »
#165
14:22, 12 июля 2018

aspam1982

Желающих решать нет

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

Как решите - напишите хоть немного о решении: сложность алгоритма, расходы по памяти, распаралеливание.. Основные метрики же не выдадут вашей оригинальной идеи.  Всем же интересно


#166
14:24, 12 июля 2018

aspam1982
У Вас достаточно специфичный проект, с не менее специфичным, для данной сферы языком программирования (как правило, такое делают на Java, реже на  С++). Причем, исходя из сложности задачи, стоимость разработки в рублях составит цифру с шестью нулями, а сроки - явно больше одного месяца. Не думаю, что кто-то будет делать этот проект просто под обещание оплаты после завершения...

#167
14:27, 12 июля 2018

iKest

реже на  С++

как раз на C/C++ и пишут такие задачи.  Потому что перфоманс без pointer арифметики не мыслим.

#168
19:40, 16 июля 2018

Мне с самого начала понравилась эта задача (понятное и лаконичное условие, вычислительная геометрия — все как надо), ну а после того, как тут отписался разработчик из альтиума, прям совсем интересно стало)

Так что вот за несколько вечеров накодил.

Исходные данные из картинок в профиле топикстартера:

+ Показать

Исходные данные, в которых есть дуги:

+ Показать

Некоторые подробности:

1) Написано с нуля на c++, использованы контейнеры из стандартной библиотеки (на самом деле, контейнеры из Qt, но это практически одно и то же), код для работы с геометрическими примитивами полностью свой.
2) Я не очень силен в оценке сложности, но как минимум она будет тут квадратичной. Сильно зависит от входных данных. Думаю, алгоритм можно существенно ускорить, заюзав что-то типа SAP для поиска пересечений и отсечения. Приложение работает в один поток. Пока что все написано практически в лоб, тупо чтобы проверить работоспособность.

#169
19:58, 16 июля 2018

tegauss
Молодец, уже чтото.
Но O(N*N) конечно им не годится. Не знаю что такое SAP, я бы дальше пошел по пути деверьев на основе Aabb. А потому уже распаралеливание на N потоков (для каждого сегмента свой поток).

#170
20:05, 16 июля 2018

slepov
Про SAP есть даже статья прямо тут. Это как раз и есть алгоритм, использующий заметающую прямую для быстрого поиска пересечений AABB.

#171
20:58, 16 июля 2018

tegauss
> Пока что все написано практически в лоб, тупо чтобы проверить работоспособность.
Ну выглядит как надо. Вопросы по реализации позадавать можно?
Какова основная идея, построить вокруг каждого сегмента контур, потом объединить эти контура?
Если да, то как происходит объединение? Строится граф пересечений, считается winding number на циклах, и выбираются по этому числу?

#172
21:14, 16 июля 2018

MrShoor

Если да, то как происходит объединение?

моя версия:

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

#173
21:56, 16 июля 2018

MrShoor
> Вопросы по реализации позадавать можно?

Можно :)

Графы вообще не используются, winding number, соответственно, тоже. В целом работает так: сначала генерятся все возможные куски будущего решения (сегменты, из которых будут состоять конечные эквидистантные контуры), потом выбрасываются лишние. Алгоритм на самом деле дофига наивный (и, кстати, на данном этапе вообще не содержит костылей), и я все это закодил в основном просто для того, чтобы посмотреть будет ли работать. Работает :) Ну, во всяком случае, на данных, которые пробовал.

#174
22:41, 16 июля 2018

tegauss
> Алгоритм на самом деле дофига наивный
Браво! Я же говорил все вполне решаемо. Русская школа математики на высоте, а силиконовые мальчики нервно курят...)))

#175
23:08, 16 июля 2018

tegauss
> В целом работает так: сначала генерятся все возможные куски будущего решения
> (сегменты, из которых будут состоять конечные эквидистантные контуры), потом
> выбрасываются лишние.
Ха, прикольно. То есть тупо выкидываешь новые сегменты, которые нарушают эквидистантность?

#176
23:33, 16 июля 2018

MrShoor

То есть тупо выкидываешь новые сегменты, которые нарушают эквидистантность?

ууу.. походу вы сами пятилетку писать будете этот алго

Причем тут эквидистантность если вы сами просили контур объединения

#177
23:35, 16 июля 2018

А мне кажется что ещё в точках связи сегментов и в конечных точках строятся окружности с радиусом, равным расстоянию до контура. Так мы получим дополнительные дуги на концах и на острых изломах...

#178
23:40, 16 июля 2018

slepov
> Причем тут эквидистантность если вы сами просили контур объединения
Объединить суп из сегментов в контура - вообще не проблема и делается за линейное время.

#179
10:32, 17 июля 2018

MrShoor

Объединить суп из сегментов в контура - вообще не проблема и делается за линейное время.

Вот именно, о чем тогда речь. Эквидистантность заложена в том что пересекают эквидистантные контуры примитивов. Т.о. слово эквидистантность можно вообще забыть и формулировать задачу как "построить контур объединения". Такая задача сводится к поиску точек пересечения и вывода контуров объекдинения. Где тут место эквидистантности?

Страницы: 19 10 11 12 13 14 Следующая »
РаботаФорумРазовая работа

Тема в архиве.