Работа
GameDev.ru / Работа / Форум / C# Смещенная кривая (12 стр)

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

Страницы: 18 9 10 11 12 13 Следующая »
slepovПостоялецwww12 июля 201814:22#165
aspam1982
Желающих решать нет

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

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

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

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

tegaussПостоялецwww16 июля 201819:40#168
Мне с самого начала понравилась эта задача (понятное и лаконичное условие, вычислительная геометрия — все как надо), ну а после того, как тут отписался разработчик из альтиума, прям совсем интересно стало)

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

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

+ Показать

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

+ Показать

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

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

Правка: 16 июля 2018 19:59

slepovПостоялецwww16 июля 201819:58#169
tegauss
Молодец, уже чтото.
Но O(N*N) конечно им не годится. Не знаю что такое SAP, я бы дальше пошел по пути деверьев на основе Aabb. А потому уже распаралеливание на N потоков (для каждого сегмента свой поток).
tegaussПостоялецwww16 июля 201820:05#170
slepov
Про SAP есть даже статья прямо тут. Это как раз и есть алгоритм, использующий заметающую прямую для быстрого поиска пересечений AABB.
MrShoorУчастникwww16 июля 201820:58#171
tegauss
> Пока что все написано практически в лоб, тупо чтобы проверить работоспособность.
Ну выглядит как надо. Вопросы по реализации позадавать можно?
Какова основная идея, построить вокруг каждого сегмента контур, потом объединить эти контура?
Если да, то как происходит объединение? Строится граф пересечений, считается winding number на циклах, и выбираются по этому числу?
slepovПостоялецwww16 июля 201821:14#172
MrShoor
Если да, то как происходит объединение?

моя версия:

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

tegaussПостоялецwww16 июля 201821:56#173
MrShoor
> Вопросы по реализации позадавать можно?

Можно :)

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

UncleMikeПостоялецwww16 июля 201822:41#174
tegauss
> Алгоритм на самом деле дофига наивный
Браво! Я же говорил все вполне решаемо. Русская школа математики на высоте, а силиконовые мальчики нервно курят...)))
MrShoorУчастникwww16 июля 201823:08#175
tegauss
> В целом работает так: сначала генерятся все возможные куски будущего решения
> (сегменты, из которых будут состоять конечные эквидистантные контуры), потом
> выбрасываются лишние.
Ха, прикольно. То есть тупо выкидываешь новые сегменты, которые нарушают эквидистантность?
slepovПостоялецwww16 июля 201823:33#176
MrShoor
То есть тупо выкидываешь новые сегменты, которые нарушают эквидистантность?

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

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

iKestПостоялецwww16 июля 201823:35#177
А мне кажется что ещё в точках связи сегментов и в конечных точках строятся окружности с радиусом, равным расстоянию до контура. Так мы получим дополнительные дуги на концах и на острых изломах...

Правка: 16 июля 2018 23:36

MrShoorУчастникwww16 июля 201823:40#178
slepov
> Причем тут эквидистантность если вы сами просили контур объединения
Объединить суп из сегментов в контура - вообще не проблема и делается за линейное время.
slepovПостоялецwww17 июля 201810:32#179
MrShoor
Объединить суп из сегментов в контура - вообще не проблема и делается за линейное время.

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

Страницы: 18 9 10 11 12 13 Следующая »

/ Форум / Работа / Разовая работа

2001—2018 © GameDev.ru — Разработка игр