0

I have a project that requires me to check if there are any overlapping labels over the component layout. However, this is simple if I am comparing 2 polygon (or less than 50 or so). But in this case i have about over 1000 polygon that needs to be tested for not overlapping. Can anyone advise me on the better solution to this rather than comparing each rectangles as it will take quite alot of time to run.

  • An idea: Project the the polygons down to 1D intervals. Use a sliding window to find overlapping intervals. Repeat along other axis. Any polygons who's intervals overlap on both projections can then be checked for actual polygon overlap. – Dillon Davis Oct 18 '22 at 05:24
  • So if a polygon overlaps on both axis, then there might still be a chance for none overlap? –  Oct 18 '22 at 05:29
  • @Alexong123 are those general polygons or specifically axis-aligned rectangles? – Yakov Galka Oct 18 '22 at 05:29
  • @YakovGalka those are general polygons that might or might not be aligned to the axis –  Oct 18 '22 at 06:34
  • 1
    Add them one by one to some kind of spatial data structure like a quadtree, testing each against the polygons already in the structure as you add it. The structure will let you efficiently choose which polygons you need to test against. – samgak Oct 18 '22 at 07:24
  • 1
    If your polygons are nice (which they probably are if they are labels): construct bounding boxes, and only compare polygons whose bounding boxes intersect. Even O(n^2) comparison of the bounding boxes should be fast (essentially instant) with only 1000 polygons. Otherwise, you can follow https://stackoverflow.com/questions/40622016/efficient-way-to-find-overlapping-of-n-rectangles?rq=1 – Paul Hankin Oct 18 '22 at 07:29
  • Are you interested in a particular programming language to implement this? – blunova Oct 18 '22 at 08:28
  • @blunova i will be using vbscript –  Oct 18 '22 at 10:14

0 Answers0