I have a file with a list of non-overlapping trapezoid covering the entire 2D space (they are adjacent if they share a segment of finite length not a point). The trapezoid are 4 points polygons which in this case are allowed to have only 90, 45, 135 degrees angles. This means their sides are parallel to x,y axis or tilted 45 degrees with respect to them (these conditions I suppose should simplify the problem).
I would like to plot efficiently the graph edges that connect each shape center point with the adjacents trapezoid center points. Which is the best algorithm to find all the adjacent shapes in x and y directions?
Note: extension of a similar question that you find here with a good answer Data structure for adjacent rectangles