Need Help - Merging Polygons

[php2010]

What I'm looking to do is analyze an array of coordinates and generate a convex-hull type outline of all independent polygons merged. Convex hull isn't ideal for my situation as I need the outline detailed.

 

From:

 

To:

 

This is how the data is arranged (The keys are just for reference):

 

$array['Group_01']['Polygon_01'] = array('latitude, longitude', 'latitude, longitude', 'latitude, longitude', etc.);

$array['Group_01']['Polygon_02'] = array('latitude, longitude', 'latitude, longitude', 'latitude, longitude', etc.);

$array['Group_01']['Polygon_03'] = array('latitude, longitude', 'latitude, longitude', 'latitude, longitude', etc.);

 

$array['Group_02']['Polygon_01'] = array('latitude, longitude', 'latitude, longitude', 'latitude, longitude', etc.);

$array['Group_02']['Polygon_02'] = array('latitude, longitude', 'latitude, longitude', 'latitude, longitude', etc.);

 

etc.

 

Basically in that scenario I would like to join ALL of the coordinates to form an outline in both 'Group_01' and 'Group_02' based on the polygons in 'Polygon_xx' under that group. Each outline independent of itself. So 'Group_01' would be a union of $array['Group_01']['Polygon_01'], $array['Group_01']['Polygon_02'], and $array['Group_01']['Polygon_03']. Then 'Group_02' would be a union of $array['Group_02']['Polygon_01']  and $array['Group_02']['Polygon_02'].  This would output an array of something like $array['Group_01']['Unified'] and $array['Group_02']['Unified'] etc.

 

Is this possible? Any help would be greatly appreciated.

 

Thanks.

[btherl]

Do you have an algorithm that you would like to implement in PHP, or are you at the stage of looking for an algorithm?

[php2010]

Well I've read plenty on this topic but I haven't found something that's really ""stuck out"" to me. Stuff like this and so forth.

[btherl]

I'm not sure clipping algorithms can apply here.. and the standard convex hull algorithms don't work either.  Do you have a precise definition of what you are trying to find?  The question I keep asking is, for example with the top left and the top polygons, how do you know you should link the two corners of those polygons and not any other?  Is it because the corners are close to each other?

 

How about this:

 

1.  Find the outermost points, where outermost is yet to have a formal definition (defining this doesn't seem obvious to me)

2.  If an edge already links two outermost points, include that edge in the final polygon

3.  If two edge sets linking outermost points are not linked together, link them together using the closest points available (only considering points that mark the start and end of a set of edges).

[php2010]

I don't really know what you would call it. Something like how GIS software ""dissolves"" boundaries together. Merging all polygons to form one and eliminate any spaces. Seems very difficult.

[btherl]

It sounds like proximity is the key.  If points from different polygons are close to each other, they probably should be merged.  But you still need to determine which points lie on the edge.  I have an idea for how to do that but no time to formalize it now.  The idea is to define the center, then find points which lie furthest away for each polygon (where furthest away is defined as not being behind any line formed by any other 2 points of the same polygon).  Then link those far points according to whichever far points on another polygon are closest.

[php2010]

Sounds interesting. If you come up with anything let me know. I appreciate all the help. I'm gonna try some more stuff after work today. 

[php2010]

I've been digging and I found this. Really wish I understood GIS a little more. :-\