python - Mapping obstructions coordinates in 2D to undirected Lattice graph

Question

Context: I want to do shortest path search for a mobile detector, source system operating in 2D Cartesian coordinates i.e. a 20 m x 10 m space. Using igraph for python, I have created a Lattice graph over these dimensions with vertices corresponding to coordinates that the detector can travel to and edges connecting neighboring vertices. The figure below is created using the layout_grid method from igraph

.

I want to add a simple rectangular obstruction to the space similar to the figure below and correspondingly to the Lattice graph :

Problem: I know that the vertices and edges corresponding to the 2D coordinates of the obstruction need to be removed using the delete_vertices method but I'm not sure how to map the 2D obstruction coordinates to the vertices in the Lattice graph. Any suggestions are appreciated.

Example code:

import numpy as np
from igraph import Graph
#Rectangular obstruction
obstruction = [[5, 0], [10, 0], [10, 5], [5, 5]]
#Create graph
g = Graph().Lattice([20.0,10.0],nei=1,circular=False)
g.delete_vertices([***obstruction coordinates***])
#Coordinates to 2D grid
coords = np.asarray(g.layout_grid(width=int(search_area[2][0])).coords)

标签： pythonigraphundirected-graph

Answer 1

原始igraph文档描述了它们是如何标记的。如果x是列，y是行并且h是格子的高度（第二维），则以下函数将格子中的坐标转换为顶点 ID。

def coordinate_to_id(x, y, h):
    """Convert coorindate (x, y) to ID for a lattice of height h."""
    return y * w + x

请注意，您必须一次删除所有顶点，因为igraph将更新其内部标识符。