5

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.

enter image description here

enter image description here

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.

enter image description here

enter image description here

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).

Cœur
  • 37,241
  • 25
  • 195
  • 267
Charles
  • 548
  • 1
  • 7
  • 25
  • Just for clarification, would you start with the 6 points and determine polygons and lines from it, or determine what the polygons are from lines the user inputs? – Qwerty01 Nov 24 '13 at 16:46
  • You'd start from multiple linked points (when the user created a line, it creates a line with a point at the start and end that he either leaves free or hold shift which links it to the nearest point of another line ). I hope I'm being clear enough. – Charles Nov 24 '13 at 16:50
  • i dont fully get the end result but it seams a job for the graphicspath. – terrybozzio Nov 24 '13 at 16:53
  • GraphicsPath would assume something different then what I'm doing. Basically, I'm testing out some ideas on a game based on risk. The lines are all supposed to borders to countries, so when the borders form a closed polygon, the inside of the border become an editable country. I'm working on making the country object from points I am giving the computer already, but I have no idea how to determine if the points on the closed border will form a closed polygon. – Charles Nov 24 '13 at 17:03
  • points,graphicspath figure,a region out of a graphicspath,your object with a region property.....just some ideas. – terrybozzio Nov 24 '13 at 17:09
  • I don't see how a this would help. Thanks terry, but what I'm trying to do is find the polygon not fill the polygon. Basically, all the yellow dots in the picture are connected, all I need to do if figure out how to find 1, 2 and 3 give all the connected yellow dots. The red lines indicate which dots are connected to which. I was thinking of doing it by nearest point from the last connected point ,but that would create a problem on long slender areas. I was thinking of doing a count of every point and using the shortest way around, but that would create a box if I input the picture. – Charles Nov 24 '13 at 17:25
  • Are you trying to find the connections (red lines), or are they already known? – Sam Axe Nov 24 '13 at 17:49
  • The connections (the red lines) are already know. The dots (the yellow dots) are already connected one to another, to form the polygons. What I am trying to find is the polygon the dots create, which in this case are represented as the black spaces with the #1, #2 and #3 in the second picture. – Charles Nov 24 '13 at 21:27
  • 1
    From what I understand of your question, you have a set of vertices and edges. And you want to find all ***Simple Cycles*** in the graph. There are plenty of algorithms available to help you with that(for eg. [here](http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs) is a stackoverflow thread about the same). Once you have your cycles, you need to distinguish the ones that you want from the set. – Samy S.Rathore Dec 16 '13 at 06:16
  • 1
    Still your question is to wide to get any srs answer. Also, there is no thing like "open polygon", I guess term "curve" would suit better. – athabaska Dec 16 '13 at 07:35

5 Answers5

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:

EvenOdd and NonZero fillrule example

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...

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.

  • Polyline may be helpful to others, but is not helpful to my situation since I need vector3[] polygons outputs to work with a earclipping algorithm to make shapes. Thanks though =) (if polyline has a hidden feature that gives back vector lists or arrays. . . I'm going to scream) – Charles Jan 07 '14 at 07:15
0

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

Géry Arduino
  • 490
  • 5
  • 16
  • Sorry I haven't been answering much, been reading up on graph cycles when I can to figure this out. Just to note, when I said "find 1,2,3" in the picture, I do not mean simply filling so the polyline class won't work (thanks for it though, it may be useful in the future and I know it exists now). I'm actually passing the found cycle to an ear clipping algorithm that needs closed cycles to then get a mesh out - so I'm trying to find a list of points that form an enclosed polygon right now. You'll probably get the bounty since I've been slow, so I'm just giving it to you. Thanks everyone. – Charles Dec 23 '13 at 06:52
0

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.

drankin2112
  • 4,715
  • 1
  • 15
  • 20
  • @Charles - "I want it to generate an internal polygon (marked by the black 1, 2 and 3)." This isn't possible the way it's stated. If you just want to make it black, then you can just draw a black bg before you draw everything else. Otherwise, you create `Paths` out of your lines. Then you can call `Graphics.FillPath` on each of the 3 paths in your model. You can also combine paths into `Regions` if you really need a single object to work with. – drankin2112 Dec 22 '13 at 04:59
0

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.

Community
  • 1
  • 1
Jonas Bötel
  • 4,452
  • 1
  • 19
  • 28
0

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.

Charles
  • 548
  • 1
  • 7
  • 25