Programmatically link all points

Question

REWRITE: I wasn't getting much feedback on this question, I assume I did not write it properly and am attempting to clarify.

I am making a program that lets people created countries. The thick red lines in the picture below are the borders to said countries. I am trying to figure out how to generate a polygon that will fill the entire area inside of the "border" lines. I have the triangulation code that accepts the polygons working - I tested that out with a polygon I entered manually - now I'm trying to figure out how to generate the polygon from the lines/linked point.

For more info - all the red lines are how the yellow dots are linked together. The users drag the yellow dots together to link the lines. It is possible for the polygon to have a hole inside and be open - what I am trying to do is make code that handles open polygons and polygons with holes inside it and generates an output of all the yellow dot's locations (vector3's with x and z as it lies at 0 on the y plane) for my triangulation code.

I'm still looking up way to figure this out but I haven't come up with even where to start looking for solutions. Thanks for all the help.

OLD QUESTION BELOW

I'm trying to find a way to link points together to form an internal polygon. Basically, I'm creating a program that lets people link lines together. After a closed polygon is made, it is supposed to generate a new polygon object inside the lines.

I'm not too sure how to do this - I have made it so they can generate the lines and link them together, but how to do a closed polygon escapes me. I looked at convex hulls but this isn't the same, and tried looking or thinking up a few different things that don't seem to work. I'm curious if anyone can point me in the write direction/a tutorial or idea on how to continue on my creation.

I have two pictures uploaded to help show my point.

Above is what I am trying to do but not too sure how - basically, when the user finished a closed polygon (all the yellow dots are the polygon's external points), I want it to generate an internal polygon (marked by the black 1, 2 and 3).

Answer 1

You may be interessted in Polylines. This could help you to prevent lots of research on graph theory. Like the Polygon class, you can fill a Polyline object. The documentation says:

This object is similar to the Polyline object, except that this object must be a closed shape.

Since you want your shape to be "open", this could help you.

And the linked manual page even includes an example of how to create the Polyline programmatically:

// Add the Polyline Element
myPolyline = new Polyline();
myPolyline.Stroke = System.Windows.Media.Brushes.SlateGray;
myPolyline.StrokeThickness = 2;
myPolyline.FillRule = FillRule.EvenOdd;
System.Windows.Point Point4 = new System.Windows.Point(1, 50);
System.Windows.Point Point5 = new System.Windows.Point(10, 80);
System.Windows.Point Point6 = new System.Windows.Point(20, 40);
PointCollection myPointCollection2 = new PointCollection();
myPointCollection2.Add(Point4);
myPointCollection2.Add(Point5);
myPointCollection2.Add(Point6);
myPolyline.Points = myPointCollection2;
myGrid.Children.Add(myPolyline);

Your second requirement is, that your shape can have "holes".

Notice, that you don't have to take care of filling the Polyline. By setting myPolyline.FillRule you can have "holes" inside of your shape. See the Polyline.FillRule page on MSDN, which shows:

If you have further wishes on how to make "holes", have a look at the Geometry.Combine Method and especially the GeometryCombineMode.

An example that demonstrates GeometryCombineModes...

Have fun : )

Pictures and code are example content, provided by Microsoft and were extracted from MSDN. Please take care of the copyrights, which are available through the given links, when reusing it. For using those contents here, I want to refer to the Microsoft Limited Public License.

Answer 2

What about a derivative of Marching Quads? you could have something like this :

for each three points (grouped in creation order inside of the mesh) find the center of the polygon and let the user assign a bool value to it which will define if this polygon is inside or outside the mesh and then draw it or not

Answer 3

You can't create an open polygon. It's only becomes a polygon when it's closed. But, here is an approach that might serve your needs.

Create a closed polygon by connecting all of the available lines, and then calculate the final line that links the starting point with the end point while it's in an intermediate state.

Then,

1. Draw (not fill) the polygon with a different color than the background.
2. Draw the final calculated line with the background color so it disappears.

That approach, or a modified version, will create the illusion of an open polygon.

Answer 4

Commenter @SamyS.Rathore is right. If your question is "How do I find the closed areas (polygons) in a planar graph given its vertices and edges?" then you want to look into Simple Circle algorithms like https://stackoverflow.com/a/14115627/642532 there.

However after finding those circles additional work is required to support holes. Basically what you want to do is to detect wether a polygon is inside another one and then geometrically subtract it.

Simple Circles doesn't deal with partially opened areas. But that shouldn't be a problem in your case, because those areas can only exist at the outer borders of the playing field and the user can easily close them at will.

Answer 5

I got this done by taking every point and linking it to a class that had a base vector3 that was the location of the point, as well as every linked line that went out from it. Basically.

class DoubleV3 Vector3 MiddleVector List LinkedVectors

I also take care of people having accidentally or purposefully put the same entries multiple times right now by remove all redundant lines.

After that I go through the entire thing and check every doubleV3's linked vectors, I go from every linkedvector to the left-most vector beyond it (basically, I check the last vector and next vector of every linkedvectors list to a north vector 1 up from the middle and take the smallest angle). This gives me a bunch of closed polygons (yes, I know now the proper term is cycle, I now use that). This deals with open cycles (which I do not want). It won't deal with complex cycles that come from overlapping lines, but I deal with that in another method.

After that I simply remove all duplicate polygons and check to make sure no polygon in inside another (I also throw out all internal cycles that aren't part of the outer hull).

Thanks everyone for helping me ^.^ This is how I ended up doing it in case anyone else is in my situation.