How to find regions inside a rectangle which is crossed by multiple lines?

Question

Imagine you have a number of lines (each one represented by two points). Also you have a rectangle of a specific size and you know coordinates of its upper left corner. Now you have to identify which of these lines intersect with rectangle and for all those that do - find regions created inside the rectangle by the lines and calculate areas of those regions.

enter image description here

You need to calculate the intersection points of your rectangle and the lines. And with those points you should be able to calculate the area of the rectangle — Blub, Dec 01 '13 at 19:53
You question is currently a bit unclear. Can you add an example (image with explanation) to better explain what you mean? (It would also help to show how you've tried to solve this problem yourself) — Bernhard Barker, Dec 01 '13 at 20:10

Vikram Bhat · Accepted Answer · 2013-12-10T11:50:52.010

Here is simple algorithm which can be improved by deeper thinking : -

Use line clipping algorithm in the rectangle.

Line clipping

Use Flood Fill algorithm for getting different regions & areas

Flood Fill

Use convex hull for each region to get vertices of regions

Graham Scan for convex hull

Edit:-

If floodfill needs to be avoided or co-ordinate system is not discrete then use following :-

Find all intersection point inside or on rectangle by the lines.
Construct a graph from intersection such that there exist an undirected edge from each intersection to other intersection if they both exist on some common line in rectangle. And also the distances between them as edge weights. Only construct edge between closest pair on a given line. This can be done by just sorting all intersections on a line and just adding edge on between each point in the sorted sequence.

Use following to get all polygons

Find_polygon(vertex u,int iter,vertex[] path)  {

         if(!visited[u]) {
               visited[u] = true;
               path[iter] = u;
               if(iter==1) {
                  source = u;
                  for all edge(u,v)
                    Find_polygon(v,iter+1,path);

               }
               else {

                    for all edge(u,v) {
                      if(slope(u,v)!=slope(path[iter-1],u)) {
                             Find_polygon(v,iter+1,path);
                      }
                    }
               }      
            }

         else  {       //loop 

                      index = findIndex(u,path); // can use array for O(1)
                      polygons.add(path[index to iteration])


         }

       }

  polygons = [];
  for all vertices v in graph :
          Find_polygon(v);

Although it was extremely helpful to get ideas from the info you pointed to, I still have not solved the problem yet. So far I'm done with determining coordinates of all vertices inside the rectangle. I'm building graph out of them. What's the algorithm for walking the graph so that I get regions depicted in the picture above? — mmierins, Dec 07 '13 at 20:09
@Davidgale have you done with floodfill then the each new call to floodfill denote a region in rectangle. — Vikram Bhat, Dec 07 '13 at 20:20
@davidgale Or you can construct graph out of it and find all loop in it using DFS to find the regions — Vikram Bhat, Dec 07 '13 at 20:22
it seems that in order to use flood fill algorithm i have to construct 2d array and mark in it 'pixels' of every line which is crossing in it. which means that i have to investigate various line drawing algorithms as well. i'm trying to find more analytic approach. — mmierins, Dec 09 '13 at 20:12
@davidgale If your co-ordinate system is discrete then thats the way to go otherwise if it is continuous that i fear your problem is more mathematical that programming based. Here is link to formula that does it http://www.mathopenref.com/coordpolygonarea.html — Vikram Bhat, Dec 10 '13 at 07:06

score 0 · Answer 2 · edited May 23 '17 at 12:19

Given a function Intersect(Polygon, Line) -> List<Polygon> that intersects a convex polygon with a line and returns a list of polygons (that contains only the original polygon if the line does not intersect it or the two resulting polygons if the line does divide the origonal one) you can do something like the following to get all resulting polygons inside the rectangle:

List<Polygon> Divide(Rectangle rect, List<Line> lines)
{
  // initialize result list with given rectangle as polygon
  List<Polygon> polys;
  polys.add(Polygon(rect));

  for (Line line: lines)
  {
    List<Polygon> polysNew;
    for (Polygon poly: polys)
      polysNew.addAll(Intersect(poly, line));
    polys = polysNew;
  }

  return polysNew;
}

For calculating the area of the polygons see e.g. here.

How to find regions inside a rectangle which is crossed by multiple lines?

2 Answers2