cascaded_union(polygons) восстановить индексы точек окружности

Мой вопрос прост, но решение может быть очень сложным. У меня есть коллекция треугольников, и я хочу найти их объединение. Треугольники задаются стандартным образом: списком координатных точек (по 2 координаты на каждую точку) и списком соединений, где каждая линия представляет собой треугольник, заданный индексами его вершин:

точки:

[ 15.02716923  81.72425842]
[ 21.42242702  79.91459549]
[ 24.87068939  79.0222168 ]
[ 29.25767326  77.96657562]
[ 34.07667923  76.65890503]

треугольники:

7 8 9
8 18 20
8 20 10
8 10 9
9 10 11
9 11 108

Я могу очень эффективно найти союз, используя cascaded_union:

import shapely.geometry as geometry
from shapely.ops import cascaded_union, polygonize

polys = [geometry.Polygon([[points[point, 0], points[point, 1]] for point in triangle]) for triangle in triangles]
result = cascaded_union (polys)

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


python shapely
person John    schedule 29.03.2017    source источник
comment
Означает ли это, что вам нужна выпуклая оболочка?   -  person Bill Bell    schedule 29.03.2017
comment
@BillBell Нет, мне нужен вогнутый корпус. Однако мне не нужно находить альфа-формы, так как я уже знаю треугольники соединения. Поэтому мне нужно только объединить их и создать результирующую форму.   -  person John    schedule 29.03.2017
comment
что вы ожидаете получить от точек внешнего кольца объединения, которых нет в вашем списке? (это легко может случиться).   -  person eguaio    schedule 29.03.2017
comment
@eguaio Не уверен, в чем именно заключается ваш вопрос, но вот что мне нужно: на данный момент мой код выше дает внешнее кольцо в виде ряда координат: (x1 y1, x2 y2, ..., xn yn). Вместо этого я хочу это с точки зрения точечных индексов, где индексы - это те, которые использовались для обозначения треугольников. Таким образом, внешнее кольцо будет иметь вид (p1, p2, ..., pn), где pi будет индексом в массиве points, а точка pi будет иметь координаты xi, yi. Однако cascaded_union может возвращать только серию координат, а не серию точечных индексов (или точечных объектов, если уж на то пошло).   -  person John    schedule 30.03.2017
comment
Я проиллюстрирую, что я имею в виду, на примере. Если вы сделаете объединение двух треугольников [(0,0),(1,1),(1,0)] и [(0,0), (0,1),(1,0)] многоугольник вы получаете, задается координатами: [(0,0),(0,1),(sqrt(2)/2,sqrt(2)/2),(1,1),(1,0)]. Точка (sqrt(2)/2, sqrt(2)/2) не является точкой ни в одном из исходных треугольников (поскольку это новая точка, образованная двумя пересекающимися линиями). Вопрос в том, какой индекс вы ожидаете получить в тех точках, которые не принадлежат исходным треугольникам. Я могу представить себе примеры, где есть последовательность многих неоригинальных точек.   -  person eguaio    schedule 30.03.2017
comment
@eguaio Нет, на самом деле этого не должно происходить с моими треугольниками, поскольку они являются частью сетки треугольников.   -  person John    schedule 30.03.2017
comment
Есть ли у вас определение «треугольной сетки», которое можно использовать для создания набора случайных треугольников?   -  person Bill Bell    schedule 30.03.2017
comment
Я не думаю, что shapely имеет какую-либо функциональность для этого конкретного случая. Кроме того, в этих условиях вы можете построить специальный алгоритм, как вы предложили, который превзойдет по производительности красивое объединение, потому что геометрия действительно не нужна. Единственное условие, которое, по моему мнению, могло бы упростить алгоритм, это если треугольники в списке уникальны и не перекрывают друг друга, кроме как по краям (что верно, если моя интерпретация «сетки» верна).   -  person eguaio    schedule 30.03.2017

Ответы (1)


arrow_upward
0
arrow_downward

Если объединение всегда возвращает полигоны с точками из вашего списка, вы можете просто искать индексы. Создайте словарь, в котором кортеж координат указывает на используемый вами индекс (с именем coord_to_pointer в коде), тогда вы сможете легко получить индексы:

polys = [geometry.Polygon([[points[point, 0], points[point, 1]] 
                          for point in triangle]) for triangle in triangles]
result = cascaded_union (polys)
geom_indexes = [coord_to_pointer[p] for p in list(result.exterior.coords)]
person eguaio    schedule 31.03.2017