0

I have one bigger rect and have coordinates of that rect ( clockwise ) and I have list of smaller rects ( also given with coordinates clockwise ). I have to remove from bigger ( base rect ) all smaller rect so I get polygon where points inside that rect do not belong to any smaller rects ( basically difference between bigger and all smaller rects ). Can anyone suggest me algorithm by name for this ?

Like on image below, my Base rect is ABCD and I have 6 smaller which I want to crop ( dark rects on image ) and result should be polygon ( counterclockwise but direction not important ) with vertexes as ( white part )

A E F G H I J K L M N O P Q B C R S T U V W Z D

enter image description here

Damir
  • 54,277
  • 94
  • 246
  • 365
  • I don't think I understood you much if at all. But I guess it sounds like a psuedo- bin packing problem? (https://en.wikipedia.org/wiki/Bin_packing_problem) – KDecker Oct 13 '16 at 16:49
  • What GUI platform? WPF? Winforms? GDI+? "Shapes" are tied to a platform. You'd need something that supports geometries. Then you create a geometry for the main rectangle and subtract off each of the smaller rectangles and you are left with a shape with all the holes punched in it. You can't do it if all you have are rectangles (unless you want a bunch of rectangles to represent the left over region?). – SledgeHammer Oct 13 '16 at 16:49
  • 1
    If I have rectangle {(0,0),(10,10)} and I remove rectangle {(3,3),(5,5)}, the result is **not** a polygon. – user3386109 Oct 13 '16 at 17:00
  • See posting : http://stackoverflow.com/questions/17950684/looking-for-algorithm-cut-a-shape-with-holes-into-a-group-of-shapes-without-hol – jdweng Oct 13 '16 at 17:15
  • 1
    You can't have an algorithm if you don't know what output you need. You need to define the output and perhaps explain the use case. – Amit Oct 13 '16 at 18:28
  • @Amit I edited and explained with image – Damir Oct 13 '16 at 18:47
  • @SledgeHammer I am using c# but I need this in coordinates for logic not for drawing directly on screen, basically to find area where my soldier can walk ( black rects are walls in this case ) – Damir Oct 13 '16 at 18:48
  • 1
    I think you have a typo after M. Anyway, is it guaranteed that the walls are always connected (no "wall in the middle", without touching any of the outer walls)? – Amit Oct 13 '16 at 19:08
  • @Amit Yes, walls are generated in that way that I cannot get holes inside ( like island ), basically you can iterate through all vertexes of polygon from any vertex as start point ( no isolated islands after cutting ) – Damir Oct 13 '16 at 19:21
  • Seems to me like a brute force "find a vertex on a line" algorithm is fairly simple to implement, are you sensitive to performance issues? Is your "*n*" very large?? – Amit Oct 13 '16 at 19:28
  • @Amit I would say that the algorithm is fairly **tedious** to implement. Find all points with the same `y` value or the same `x` value, depending on which direction you're going. Sort ascending or descending, again based on direction. Then choose the new point and the new direction. And in every step, make sure to ignore already used points. There's just a lot of nitpicking details to get right, and not much of an algorithm. – user3386109 Oct 13 '16 at 20:03
  • If you just need this for a boolean decision (can walk or cannot walk), then you should just keep the rectangles. Checking for rectangle inclusion is quite easy. Checking for polygon inclusion is a bit harder. Holes in polygons are usually stored as separate polylines. Thus, your representation wouldn't change much. – Nico Schertler Oct 14 '16 at 12:41

0 Answers0