CODEWITHSUNDEEP
visibilitypolygoncomputational-geometry
Xolve
Xolve

Reputation: 23220

Visibility of polygons from an edge

Given is a 2D are with the polygons. I need to find out the polygons visible in a perpendicular line of sight from the a given line segment lying within that area. e.g.

A sample example of the problem

Upvotes: 2

Views: 865

Answers (1)

Angus Johnson
Angus Johnson

Reputation: 4643

I'd suggest the following ...

  • Rotate the problem so your 'line of sight' segment is aligned to the x axis.
  • Find the (axis aligned) bounding rectangle (BR) of each polygon.
  • Sort the polygons using the Y coordinate of the bottom edge of each BR
  • Create a clipping 'range buffer' to mark the portions of the viewing segment that will be no longer visible.
  • For each polygon C (current) in the sorted list do ...
    1. Use C's left and right bounds as its initial clipping range.
    2. Trim C's clipping range with the range already marked as clipped in the 'range buffer'.
    3. Now for each subsequent polygon S of a similar depth (ie where S's BR bottom edge starts below C's BR top edge) ...
      • loop to next S if it doesn't overlap horizontally with C
      • determine if S is overlapping from the left or right (eg by comparing the BR horizontal midpoints of S and C). If S overlaps from the right and S's left-most vertex is below C's right-most vertex, then truncate C's clipping range accordingly. (Likewise if S overlaps from the left.)
    4. If the residual clipping range isn't empty, then at least part of C is visible from your viewing segment. Now add C's residual clipping range to the clipping 'range buffer'.

Upvotes: 2

Related Questions