0
$\begingroup$

I have rectilinear polygons present, and they are surrounded by grids(grey rectangle with dots denoting center) as shown in the diagram below. There are some areas where grids are not present - like the big grey and red polygons.

enter image description here

The grids are perfectly stacked horizontally and vertically. I have with me the coordinates of the edges (x,y) and the centre points of the grids (vector<pair<int,int>>). The grids may or may not intersect with the polygon edge.

I need to find all the grid points that are immediate neighbours to that edge in the respective orientation (left,top,down,bottom).

If the red polygon were not there, I could simply find the grid point closest to the edge corners and fill the rest of the matrix, but the red box messes up the continuity. The red box is also a polygon with edge coordinates known.

Input is the vector of grid centers : vector<pair <int,int>> and map of vector to store the polygon coordinates: map <string,vector<pair<int,int>> polyLst[shape1] = {x0,y0} {x1,y1} {x2,y2} {x3,y3} ,{x4,y4} ,{x5,y5} ,{x0,y0}

The polygons are closed. I have ~300 such polygons with varying edges total sum of which is ~120000. The grid is of ~600000 points.

Required output is the set of points closest to the edge (the orange ones). It should be per edge ( edge 1 (x0,y0 to x1,y1) has p1,p2,p3,... grid points as neighbour).

Any performant approach to solving this?

Improve this question
$\endgroup$
4
  • $\begingroup$ do this I have an idea about what the input is for the polygons. Please add to your question: How is the grid specified? What is the required output? $\endgroup$
    – greybeard
    May 10 at 5:55
  • $\begingroup$ In your explanation, the red polygon all of a sudden falls from the sky. You should describe more precisely the geometry of the problem. How many polygons do you process at a time ? $\endgroup$
    – user16034
    May 10 at 8:10
  • $\begingroup$ @YvesDaoust- updated the information about red polygon.. red is just another polygon like the big grey one - only difference is that i need to find the points closest to the grey's edges. I process ~300 polygons with varying edges - the total sum of which is ~120000 edges . $\endgroup$
    – kil47
    May 10 at 11:03
  • $\begingroup$ @greybeard : modified the description with input, outputs and current state $\endgroup$
    – kil47
    May 10 at 11:15

1 Answer 1

Reset to default
0
$\begingroup$

Hints:

Scan every red polygon and determine the cells it overlaps. Some are wholly overlapped, some partially. For the partial overlaps, you need to record the intersections between the polygon and the cell. This can be done using the Sutherland-Hodgman clipping algorithm. For every cell, keep a list of the overlaps.

Then for a given gray shape, it should not be too difficult to find the surrounding cells, and to remove those the center of which is covered by a red cell.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "it should not be too difficult to find the surrounding cells" - any proposal here - i could find any line sweep approach .. what i have with me finding closest grid to the edges and fill the rest in between... and while filling check if the cell does not overlap with red- anything better than this ? $\endgroup$
    – kil47
    May 10 at 12:56
  • $\begingroup$ for clipping - i used the angus clipper -worked well :-) $\endgroup$
    – kil47
    May 10 at 12:56
  • $\begingroup$ @kil47 Finding the cells is virtually Bresenham line segment drawing. If axis parallel, this is trivial. $\endgroup$
    – user16034
    May 10 at 14:54
  • $\begingroup$ @kil47: No filling. And checking the overlap is done in time O(1), what more do you want ? $\endgroup$
    – user16034
    May 10 at 14:55
  • $\begingroup$ @kil47: using Clipper for this task is overkill. $\endgroup$
    – user16034
    May 10 at 14:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.