[DEM]

Собсно по мотивам темы
Перевод формата STL в твердотельную геометрию (Rhino, Salome и другие программы)
Решено сделать программу, т.к. та сетка которая получалась в Salome, делалась довольно таки долго и с непредсказуемыми последствиями.
Файлы в Salome загружались очень долго и т.д.
В качестве программы в которой будет создаваться модель, принят FreeCad соответственно программирование будет на Python.
Сразу оговорюсь, Python принят в качестве языка программирования т.к. потом к нему собираемся через SWIG подключить библиотеку SCAD API на C++.
На данный момент столкнулся с задачкой которую в лоб решить не могу.
У меня есть список отрезков вот такого вида

Код:

[Выделить все]

1я плоскость ['6/41', '6/40', '4/35', '30/31', '5/36', '1/34', '4/30', '5/35', '32/33', '31/32', '33/34', '1/41', '37/38', '38/39', '36/37', '39/40']
2я плоскость
['19/86', '19/87', '102/103', '15/71', '15/70', '95/96', '85/86', '4/104', '3/29', '61/62', '82/83', '84/85', '83/84', '92/93', '65/66', '30/31', '3/101', '90/91', '72/73', '75/76', '71/72', '28/29', '22/99', '32/33', '54/55', '74/75', '24/99', '24/98', '22/100', '21/97', '79/80', '21/100', '73/74', '25/26', '76/77', '2/67', '10/101', '10/102', '59/60', '16/77', '16/78', '1/34', '13/56', '26/27', '1/54', '4/30', '18/82', '18/81', '14/96', '78/79', '103/104', '87/88', '57/58', '58/59', '2/25', '27/28', '88/89', '93/94', '11/66', '94/95', '69/70', '13/57', '55/56', '23/97', '17/80', '17/81', '23/98', '62/63', '20/92', '20/91', '68/69', '14/68', '60/61', '64/65', '11/67', '89/90', '33/34', '12/63', '12/64', '31/32']
3я плоскость
['10/52', '7/42', '10/53', '44/45', '43/44', '42/43', '45/46', '7/53', '48/49', '50/51', '8/47', '8/46', '9/48', '9/47', '51/52', '49/50']

Собсно надо получить списки замкнутых контуров с обходом точек по часовой стрелке....
Типа [19/87, 87/88, 88/89 (и т.д.)]

Координаты точек я так понимаю особо то и не потребуются....
Либо алгоритм нужен, либо код на Paython 2.7
Ну иль просто подсказка в какую сторону копать.....

[VVA]

Сообщение от DEM Собсно надо получить списки замкнутых контуров с обходом точек по часовой стрелке

В качестве идеи Convex Hull с использованием Graham Scan Algorithm



Вроде как Phyton есть готовые решения
graham scan algorithm python

[DEM]

Координаты вообще не хочется использовать....
Тут аналитически можно определить.
Использовать что нибудь типа Граф....

[trir]

1. Строим граф
2. Получаем список вершин, у которых >2 связей
3. Для всех рёбер из этих вершин находим кратчайшее расстояние между вершинами (не считая само ребро конечно)
4. ???
5. PROFIT!

[DEM]

Сообщение от trir 1. Строим граф 2. Получаем список вершин, у которых >2 связей 3. Для всех рёбер из этих вершин находим кратчайшее расстояние между вершинами (не считая само ребро конечно) 4. ??? 5. PROFIT!

В виде кода можно?

[Brandashmыg]

1. А почему 2.7?
2. В Shapely есть возможность создать полигон по точкам и потом получать от него всё что угодно, в том числе координаты наружного контура.

Код:

[Выделить все]

from shapely.geometry import Polygon
polygon = Polygon([(0, 0), (1, 1), (1, 0)])
list(polygon.exterior.coords) #собственно координаты контура

А ещё проще каждый полигон при импорте сделать полигоном, а потом их просто объединить (a.union(b))

Почему лучше так, а не повторением алгоритма обхода точек самостоятельно - библиотеки в питоне обычно быстрее, т.к. "узкие" участки переписаны на С++.

[DEM]

Brandashmыg
1. Потому как Freecad на 2.7 а для построения и редактирования схем я его хочу использовать.
2. Да тут как бы можно и без библиотеки обойтись, ведь задача чисто аналитическая.

[Sleekka]

До точек падать нельзя, нужно оставаться на уровне отрезков, упав до точек - будет неверный результат, Грэхем не решит задачу правильно.

Нужно использовать именно массив отрезков или полигонов.

[Brandashmыg]

Почему аналитическая? Выше пример привели - всё через координаты точек. Сами отрезки не нужны. Но тогда может какую-либо область "срезать". Поэтому и проще идти через объединение полигонов - тогда и отверстия и "выгрызы" останутся.

[DEM]

Ну вот я граф нарисовал, и там все довольно простг получается...

[Brandashmыg]

По количеству рёбер? У 62 узла и у 310 одинаковое количество отрезков.

[Sleekka]

Сообщение от DEM Ну вот я граф нарисовал, и там все довольно простг получается...

Граф рисуется по точкам, но не по отрезкам, следовательно достоверность совпадения графа с контуром не 100%-я вопрос лишь когда и на каких данных вылезут различия.

[DEM]

Brandashmыg
Так просто чтобы сделать как ты показал, придется координаты преобразовывать в 2d....
Sleekka
http://pythontutor.ru/lessons/graphs/
http://pythontutor.ru/lessons/dfs/
Реализация графа в ребрах представлена...

[Brandashmыg]

DEM
Shapely поддерживает 3д
The Polygon constructor takes two positional parameters. The first is an ordered sequence of (x, y[, z])

[DEM]

Сообщение от Brandashmыg По количеству рёбер? У 62 узла и у 310 одинаковое количество отрезков.

Чего-то не понял тебя....
Представленно 3 плоскости....
В них различные контуры представлены.
Часть узлов уже удалена, т.к. они не нужны.
Это те узлы которые находятся внутри контура....

----- добавлено через ~9 мин. -----
Зы. А по части Shapely ты по моему не прав....
Там все таки надо по порядку задавать грани...
Но там вроде как есть создание полигона по точкам...
Да и в чистом пайтоне я встречал алгоритм для 2d

[Brandashmыg]

Сообщение от DEM Там все таки надо по порядку задавать грани...

Каждый КЭ СРАЗУ после чтения загоняешь в полигон, потом делаешь для всех union и получаешь обобщённый полигон плиты.
А для чего это всё? Опалубку вытаскивать?

-----------------
Пример:
https://github.com/kuvbur/asf-reinfo...aster/parse.py
класс asf функция get_element

[DEM]

Brandashmыg
Да хочу получить геометрическую модель а не сеточную.
Чтобы потом проще править было.
Сетку потом буду делать в gmsh, или перекидывать в dxf и в Робот загонять.
Вообще-то идея создание своего препроцессора и постпроцессора.

Потом можно будет и армирование просматривать, в том же Freecade и сразу распечатку делать.
Много чего задумано....

----- добавлено через ~8 ч. -----

Сообщение от Brandashmыg 1. А почему 2.7? Код: [Выделить все] from shapely.geometry import Polygon polygon = Polygon([(0, 0), (1, 1), (1, 0)]) list(polygon.exterior.coords) #собственно координаты контура

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

[Brandashmыg]

Для четырёх узлового КЭ порядок точек будет не важен. Посмотри код на гитхабе - там просто список скармливаешь ему и всё.

[trir]

у меня проблемы с п.3 - не могу добиться нужного результата...

[Brandashmыg]

Сообщение от trir у меня проблемы с п.3 - не могу добиться нужного результата...

Сообщение от trir 3. Для всех рёбер из этих вершин находим кратчайшее расстояние между вершинами (не считая само ребро конечно)

А почему самое короткое ребро обязательно внешнее?