All geek questions in one place

Polygon visibility from the edge

Given that 2D are polygons. I need to find out the polygons visible in the perpendicular direction of view from a given segment lying in this area. eg.

A sample example of the problem

  • Further

    What can be optimizations when polygons have only vertical and horizontal edges.

+2
source share
1 answer

I would suggest the following ...

  • Turn the problem so that the line of sight line is aligned with the x axis.
  • Find the (bounding axis) bounding box (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 parts of the view segment that are no longer visible.
  • For each polygon C (current) in the sorted list ...
    • Use C left and right borders as the starting clipping range.
    • Trim C trim range with the range already marked as trimmed in the "range buffer".
    • Now for each subsequent polygon S of similar depth (i.e., when the lower edge S BR starts below the upper edge C BR) ...
      • loop to next S if it does not overlap horizontally with C
      • determine whether S overlaps left or right (for example, by comparing the horizontal midpoints of B and S). If S overlaps on the right, and S the leftmost vertex is below C of the right vertex, then crop the clipping range of C, respectively. (Similarly, if S overlaps on the left.)
    • If the residual clipping range is not empty, then at least part C will be visible from your view segment. Now add the residual C range to the clipping range buffer.
+2
source

Source: https://habr.com/ru/post/896667/

More articles:


All Articles