ansaurus

Question

Find the outline of a union of grid-aligned squares

Answer 1

+2 A:

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 2010-08-17 11:15:37

Answer 2

+1 A:

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 2010-08-17 15:11:54

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 2010-08-18 02:57:17

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 2010-08-18 07:08:00

@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 2010-08-18 14:59:37

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 2010-08-19 04:32:48

****edited my question as i needed formatting****

ssdesign 2010-08-19 13:56:26

@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 2010-08-19 14:50:37

@ssdesign, re partial vector cancellation, what part of "1.0 up + 0.5 down = 0.5 up" don't you understand?

brainjam 2010-08-19 14:52:20

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 2010-08-19 15:19:58

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 2010-08-19 15:31:12

@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 2010-08-19 16:40:40

ansaurus

tags:

views:

answers:

Find the outline of a union of grid-aligned squares

related questions