Реализация графа видимости в планировании движения: дилемма с вершинами ⇐ Python

[Anonymous]

Я пытаюсь вычислить граф видимости графа с многоугольниками.
Я сделал это, выбрав все пары вершин многоугольников и разделив их на 2 случая:

• 2 вершины находятся в одном многоугольнике: мы проверяем, являются ли они соседями, и если да, то добавляем ребро.
  < /li>
  2 вершины не находятся в одном многоугольнике: бросаем все ребра (в C-пространстве) и смотрим, пересекают ли они хотя бы одно. если да, то мы не будем добавлять преимущество, иначе мы это сделаем.

Я столкнулся с двумя проблемами.

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

Можете ли вы помочь мне исправить это?

Код: Выделить всё

def is_visible(p: Point, v: Point, expanded_obstacles: List[Polygon]) -> bool:
#case 1 - p and v in the same polygon
for polygon in expanded_obstacles:
if p.coords[0] in polygon.exterior.coords and v.coords[0] in polygon.exterior.coords:
exterior_coords = list(polygon.exterior.coords)
idx1 = exterior_coords.index(p.coords[0])
idx2 = exterior_coords.index(v.coords[0])

# Points are adjacent if their indices differ by 1 (cyclically)
return abs(idx1 - idx2) == 1 or abs(idx1 - idx2) == len(exterior_coords) - 1

#case 2 - p and v not in the same polygon
line_pv = LineString([p, v])
#if p and v in the same obsticale than add if and only if they neuighbers
for obstacle in expanded_obstacles:
for i in range(len(obstacle.exterior.coords)):
edge = LineString([obstacle.exterior.coords[i], obstacle.exterior.coords[(i + 1)%len(obstacle.exterior.coords)]]) # modulo for n  0
if line_pv.intersects(edge) and not line_pv.touches(edge):
return False
return True

def get_visibility_graph(obstacles: List[Polygon], source=None, dest=None, r=0) -> List[LineString]:
"""
Get the visibility graph of a given map.
:param obstacles: A list of the obstacles in the map.
:param source: The starting position of the robot. None for part 1.
:param dest: The destination of the query. None for part 1.
:param r: The radius of the robot (used for Minkowski sum expansion).
:return: A list of LineStrings holding the edges of the visibility graph.
"""
# Expand obstacles using Minkowski sum
# expanded_obstacles = [get_minkowsky_sum(obstacle, r) for obstacle in obstacles]
expanded_obstacles = obstacles
vertices = set()  # Use a set to avoid duplicates
# Extract all vertices from expanded obstacles
for obstacle in expanded_obstacles:
vertices.update(obstacle.exterior.coords[:-1])  # Avoid duplicating the closing point

# Add source and destination if provided
if source:
vertices.add((source[0], source[1]))
if dest:
vertices.add((dest[0], dest[1]))

vertices = [Point(v) for v in vertices]
visibility_edges = []

# Evaluate visibility for each pair of vertices
for p in vertices:
for v in vertices:  # Avoid duplicate checks
if v.coords[0][0] == -5 and p.coords[0][0] < -5:
f=3
if is_visible(p,v, expanded_obstacles):
visibility_edges.append(LineString([p, v]))

return visibility_edges

зеленый — робот .
фиолетовый — препятствия.
розовый — c-пространство.
черный — края в видимости график.
как видите, это черные ребра, которые пересекают ребра c-пространства, проходя через соединяющую вершину

Подробнее здесь: https://stackoverflow.com/questions/792 ... -vertecies