I trying to calculate the visability graph of graph with polygons.

I did it by going throw all the pairs of vertecies of the polygons and separate into 2 cases:

1. the 2 vertecies are in the same polygon: we will check if they are neighbers and if so we add an edge.

2. the 2 vertecies are not in the same polygon: we go throw all the edges (in the C-Space) and see if it cross at least one. if so we will not add edge otherwise we will.

I facing 2 problems.

1. some edges in the polygons wasnt added for some reason
2. as you can see in the pic an edge can cross a shape by going throw the connecting vertex.

can you help me fix that?

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

green – robot.

purple – obsticles.

pink – c-space.

black – edges in the visability graph.

as you can see, the are black edges that crossing c-space edges by going throw the conecting vertex