1

How to get the co-ordinates of the outline shape formed using smaller grid blocks.

For example, If I used 32x32 unit blocks for construct a shape (any shape). Then how can I get overall co-ordinates of the shape, including the negative spaces.

For example: One could arrange the blocks like this: (each block is 32x32 and coordinates refer to bottom left corner of the block)

Block 1 - (0,0)
BLock 2 - (32,0)
Block 3 - 64,0)
Block 4 - (64,32)
Block 5 - (64, 64)
BLock 6 - (32, 64)
BLock 6 - (0 64)
Block 7 - (0, 32)

Now you can see this will create an empty space in the middle.

So what I would like to know is, how to get the coordinates of the above shape such that I get:

Main Block = (0,0), (96,0), (0,96)
Empty space = (32,32), (64,32), (64,64), (32,64)

Is there any mathematical solution to this?

Eventually I will be doing complex shapes.

thanks

******** edit **** Hi,

How to deal with this condition?

<------------------^<----^
|                  ||    |
V------------------>|    |
<------^          /^|    |
|      |<------^ / ||    |
|      ||      |/  ||    |
V------>V------>V-->V---->

i would like the result to be like this

<-------------------<----^
|                        |
V      ^----------->     |
|      |          /      |
|      <-------^ /       |
|              |/        |
V------>------->--->----->
brainjam
  • 18,540
  • 7
  • 52
  • 80
ssdesign
  • 2,627
  • 6
  • 31
  • 49

2 Answers2

3

Think of each square as an outline comprised of four vectors going in a counter-clockwise chain.

<-----^
|     |
|     |
V----->

So for all the squares in your shape, take the union of their outline vectors. If two outline vectors in the union are identical but go in opposite directions, they cancel each other out and are removed from the union.

For example, for two squares that are side by side the union is 8 vectors

<-----^<-----^
|     ||     |
|     ||     |
V----->V----->

which reduces to 6 vectors because the two vertical vectors in the middle cancel:

<-----<-----^
|           |
|           |
V----->----->

For the example you gave, the result of this will be (after cancellations):

<-----<-----<-----^
|                 |
|                 |
V     ^----->     ^
|     |     |     |
|     |     |     |
V     <-----V     ^
|                 |
|                 |
V----->----->----->

You just have to connect up the vectors in the final reduced union to read off the outline paths. Note that the inner outline ("the hole") runs clockwise.

brainjam
  • 18,540
  • 7
  • 52
  • 80
  • Hi, That sound very promising. Basically I am trying to do this with PHP Arrays. I have not been able to find a good Vector class for PHP yet. btw. Any idea how to identify closed loops which are clockwise in direction and segregate them from anticlockwise loops? – ssdesign Aug 18 '10 at 02:57
  • WIll this logic work even if the spahes are odd shaped? For example. What if the second shape was a rectangle (half the height of first square). – ssdesign Aug 18 '10 at 07:08
  • @ssdesign, you don't really need a Vector class, just something that indicates start and end points, or start point+direction+length. You can search StackOverflow for tests that distinguish clockwise vs. counterclockwise. As for odd shapes, I guess you can have vectors partially cancelling one another - so 1.0up + 0.5down = 0.5up. – brainjam Aug 18 '10 at 14:59
  • Hi, I am not a Math person atall :) Its just that I have to deal with this situation while making a web application. So is it possible to give me some more hints on a couple of things? I tried searching StackOverflow about clockwise vs counterclockwise but didnt get anything useful. Anything i missed? Also I would like to know how to cancel vectors partially. --- thanks – ssdesign Aug 19 '10 at 04:32
  • @ssdesign, for CW and CCW, see http://stackoverflow.com/questions/1046542/how-to-represent-a-polygon-with-holes, http://stackoverflow.com/questions/1199428/determine-ordering-of-polygon-3d, http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order/1165943#1165943 – brainjam Aug 19 '10 at 14:50
  • @ssdesign, re partial vector cancellation, what part of "1.0 up + 0.5 down = 0.5 up" don't you understand? – brainjam Aug 19 '10 at 14:52
  • that part i understand. what i didnt understand was, just before the loops have been closed, end condition before the hole is created, how can i know this is the end? and after that, how to I extract the two separate polygons? – ssdesign Aug 19 '10 at 15:19
  • as an afterthought, would it help if I first get the outer shape using 'convex hull' and then would there be a way to find if there are holes inside the hull? edit**** Maybe not. – ssdesign Aug 19 '10 at 15:31
  • 1
    @ssdesign: You know that a loop is closing when the last vertex is the same as the starting vertex. Two outlines are separate if they don't have any vertices in common. – brainjam Aug 19 '10 at 16:40
  • Not really helpful (for me) since it doesn't provide any insight on how to implement this. It's obvious how to do this "graphically", not so, when all you have is just a number of points representing simple polygons and you want to unify/intersect/substract them. – Dan M. Jul 31 '16 at 21:52
  • @Dan: agreed. But the problem here is about finding the union of grid aligned squares. Union/intersection/difference of simple polygons is a larger topic. See the other answer here (http://stackoverflow.com/a/3501778/242848) for a link. – brainjam Aug 01 '16 at 16:31
2

You would probably need to focus on Boolean Polygon Operations, unions in your case. There are plenty of papers covering the 2D boolean polygon operations and constructive planar geometry, see the Wikipedia: http://en.wikipedia.org/wiki/Boolean_operations_on_polygons.

mbaitoff
  • 8,283
  • 4
  • 22
  • 32