Algorithm for translating a list of walls into a coherent polygon

Question

I have a list of points that in pairs describe a polygon, for example:

<0,0> <0,1> <0,1> <1,0> <1,0> <1,1> <1,1> <0,0> which is a square. Note that each pair of points describes a line, so our square consists of lines

<<0,0> <0,1 l → &; <0.1> <1.0 L → &; <1.0> <1.1 L → &; <1.1> <0.0 →

However, I have to draw these polygons, which work fine when all the points are in order and there are no holes. Unfortunately, this sometimes happens incorrectly when input is similar to

<0,0> <0,1> <1,1> <0,0> <0,1> <1,0> <1,0> <1,1> and the resulting polygon is strange or when in

there are several holes

<0,0> <0,2> <0,2> <2,0> <2,0> <2,2> <2,2> <0,0 <1,1 <1,1,5 < 1,1,5 <1,5,1,5 <1,5,1,5 <1,1>

In these situations, the naive thing of drawing these polygons with drawpoly (dots) will not work.

This is in C #, and actually the input is List<GeoData> , where GeoData contains 2 points (and some other misq data). For the conclusion, I was thinking of creating a list and list>, where the first set of points is the outer line and the second list is the holes, will this work? I need to do a few extra calculations with polygons besides drawing, but I think that this will be easiest with a special list of holes.

Here is an example:

On the left - what I am getting right now is the entrance.

Answer 1

In your example, I see that you draw a single polygon. You must call the draw polygon ( drawpoly(points) ) method several times for each individual polygon.

I think it’s easier to draw holes instead of walls, following the KISS principle.

To do this, you can save the polygons (holes) that you want to draw in the list. If we analyze the data, we see that the bolded data shows the beginning and end of the polygon.

<0,0> <0,2> <0,2> <2,0> <2,0> <2,2> <2, 2> <0,0> <1,1> <1,1.5> <1,1.5> <1.5,1.5> <1.5,1.5> <1,1>

And we present this in code, as shown below:

 public List<List<GeoData>> Split(List<GeoData> points) { List<List<GeoData>> polygons = new List<List<GeoData>>(); GeoData firstPoint = null; List<GeoData> currentPolygon; foreach(var point in points) { if(firstPoint == null) { firstPoint = point; currentPolygon = new List<GeoData>(); currentPolygon.Add(point); } else { currentPolygon.Add(point); if(point == firstPoint) { firstPoint = null; polygons.Add(currentPolygon); } } } return polygons; } 

Using:

 List<List<GeoData>> polygons = Split(points); foreach(var polygon in polygons) { drawpoly(polygon); }