CODEWITHSUNDEEP
javaalgorithmmathgeometry
mmierins
mmierins

Reputation: 3774

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

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

Upvotes: 1

Views: 1560

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

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 :-

  1. Find all intersection point inside or on rectangle by the lines.

  2. 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.

  3. 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);

Upvotes: 2

coproc
coproc

Reputation: 6257

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.

Upvotes: 0

Related Questions