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?

Thank you.

Note: extension of a similar question that you find here with a good answer Data structure for adjacent rectangles

  • $\begingroup$ The "non-overlapping" trapezoids are overlapping at common boundary portions right? Do you have the trapezoids only as individual polygons or is it already a PSLG that partitions the plane in these trapezoids. $\endgroup$
    – gue
    Commented Mar 16, 2018 at 13:06
  • $\begingroup$ @gue Yes the trapezoids overlap only at the common boundary portions. They are provided as individual polygons with the 4 points coordinates available. $\endgroup$
    – Enialis
    Commented Mar 18, 2018 at 17:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.