0

I am new here and new to C#, and am having what I hope is a simple problem to solve.

(I use gmaps.net for winforms for this, but will also use the method via the web API maps version as well).

We have a database of zipcodes and areas in our database. Each area contains multiple zipcodes. Each zipcode has a series of coordinates that create a google maps polygon for that zipcode.

Presently if we want to display our "area" on the map, we do so by drawing the polygons for each of the area's zipcodes without borders and all of the same color (so it appears as one large polygon, just without a border).

Now ive been tasked to add a border to it, but only an outer border - not the borders for each internal zipcode.

Now, I'm not a math genius by any means, but it seems to me there should be a way I can run each group of zipcodes' coordinates (all combined to a single list of PointLatLng), thru a method that will discard all of the "internal" points leaving only the outer border points which we can then use as one single polygon (with border!) for our "Area"... is this possible? CAn someone give me a kick in the right direction for figuring out how to do it?

Thanks!

Jason

Jason Neering
  • 23
  • 5
  • 1
    It sounds like what you want is a Convex Hull algorithm. If so, they are all over the internet and very easy to find with a Google search. For example: http://stackoverflow.com/questions/14671206/convex-hull-library – Abion47 Oct 08 '16 at 09:07
  • Easy to find if you know what to search for :) ill give that a try. Thank you very much. – Jason Neering Oct 08 '16 at 09:21
  • Ok, it looks like this will *not* work, because it will lose a lot of points in the process. Looking at the samples I see, if a zipcodes points extend a sliver of land out a ways from the bulk and then back inward (think like florida), it would round out the border and lose the shape. I'll have to keep looking. – Jason Neering Oct 08 '16 at 09:45
  • What do you mean? In your question, you said the goal *was* to discard the internal points. – Abion47 Oct 08 '16 at 17:53
  • To discard the internal points without changing the external structure. – Jason Neering Oct 08 '16 at 20:09
  • I still don't follow. In what circumstance would discarding a point that is fully within an enclosing polygon change the shape of the polygon? – Abion47 Oct 08 '16 at 20:46
  • It shouldn't, but the convex hull algorithm linked above (and 2 more linked beyond that), do drastically change the shape of the polygon as part of what they do. In one instance, consider a polygon that has a florida shaped finger coming off the side and snapping back in to form a thin strip of land. With all the above algorithms that "finger" becomes a rounded or beveled corner instead. it still hits the outermost point of the "finger", but skips the points that bring it back around in a finger shape. – Jason Neering Oct 09 '16 at 15:30
  • So you want an algorithm that can create concave polygons out of a series of points (like, say, a pac-man shape) while intelligently removing points that are " within" the polygon? That's quite a bit more complicated, and I don't believe there will be an algorithm that you can just drop into your program that will just work. (And the solution might involve making something akin to a convex hull anyway.) – Abion47 Oct 09 '16 at 17:04
  • Just so we're clear, is this more like something you were trying for? http://imgur.com/a/vV7EO – Abion47 Oct 09 '16 at 18:19
  • Exactly so Abion47. That is exactly what I was looking for, and exactly what the convex hull is doing. In my case it is much more pronounced since there are so many irregularities in the point placements since it is geographical in nature, but exactly the same concept. – Jason Neering Oct 12 '16 at 21:17

1 Answers1

0

Okay, so what you're looking for is a concave hull instead of a convex hull. Unlike a convex hull, which has only one solution for any given set of points, a concave hull has many solutions and many ways to achieve them. The two most common approaches are alpha shapes or Delauney triangulation, and of the two I'd recommend triangulation.

The short explanation for a Delauney triangulation is the creation of a triangular mesh from a set of points such that the minimum interior angle of any given triangle is as large as possible. There are a lot of existing libraries that can create a Delauney Triangulation for you. (The most highly recommended one seems to be Triangle.NET.)

Once you have a triangulation performed on your set of points, you essentially discard the triangle side information for all sides that are shared between two triangles. This leaves you with only sides that are exclusive to a single triangle, which corresponds to the perimeter of the polygon:

enter image description here

(Credit to Timothy Shields on this question for the image.)

Once you have this graph of edges, you can simply traverse them (by going from edge to connected node to connected edge and so on) to get an array of points defining your concave hull:

(Pseudocode)

public Point[] GetPolyFromEdgeGraph(Edge[] edges)
{
    List<Point> poly = new List<Point>();

    Edge edge = edges[0];
    Point start = edge.PointA;
    Point point = start;

    do 
    {
        poly.Add(point);

        edge = point.EdgeA != edge ? point.EdgeA : point.EdgeB;
        point = edge.PointA != point ? edge.PointA : edge.PointB;
    } while (point != start);

    return poly.ToArray();
}
Community
  • 1
  • 1
Abion47
  • 22,211
  • 4
  • 65
  • 88