This project is read-only.

Triangulation endless loop

Aug 18, 2013 at 12:18 PM
Hello,

Thanks for this great library in advance=).I am using constrained delaunay triangulation it was working fine but then i got in an endless loop what could be causing this. My point list is as follows. I m using sweepline algorithm. I would be really thankful if you could point me in any direction.
                TriangleNet.Geometry.InputGeometry inGeo = new                 TriangleNet.Geometry.InputGeometry(segmentList.Count);
                foreach (var pt in segmentList)
                {
                    inGeo.AddPoint(pt.X, pt.Y);

                }
                for (int i = 0; i < segmentList.Count - 1; i++)
                {
                    inGeo.AddSegment(i, i + 1);
                }
                Mesh triangleMesh = new Mesh();
                triangleMesh.Behavior.Algorithm = TriangleNet.TriangulationAlgorithm.SweepLine;
                triangleMesh.Triangulate(inGeo);
5.16191620588875,4.74489599815306
5.02102521525629,4.7344726196005
5.01208348248456,4.73367336421044
5,4.73257998285177
4.91511208481942,4.7247949658969
4.83282671300839,4.71719148685957
3,4.5558631889464
2.38706774421006,4.49645401183218
2.00901042740101,4.45486547638022
2.005525567705,4.45437543318585
1.18276729996591,4.32774737104215
1,4.27602480527384
0.572810271987014,4.15458918350014
0.0223566278276216,3.72870064690785
0.00962317637117527,3.71904827417058
0.0535143418010542,3.49259703477457
0.0731335379387111,3.46265489173499
0.307072549393047,3.24018401420075
0.524359236291813,3.12902451614457
0.785748191135991,3.04691649562599
1,2.95455470230018
1.35213334242182,2.79475195781052
1.44320264839598,2.76686090428988
1.5367342674238,2.73823575361126
1.54857243633759,2.73453268321805
1.90356622710304,2.62203696909176
1.92408675536428,2.61565745248041
1.94731470020927,2.608396431284
1.9738036384356,2.60007345601322
2.0921529459617,2.56250665748498
2.31786695783887,2.4898925729526
2.12809991836548,2.42245456624611
2.07594967457437,2.40226646667309
1.97452263347559,2.36256936070282
1.94985612088841,2.35254320727545
1.92693574663062,2.34297225638066
1.84524499400463,2.30651255757652
1.82917381266489,2.29999995231628
1.85846105146484,2.29004195829387
1.95967176140747,2.25386783628871
1.97211524016405,2.24965050758107
2.06880869091307,2.21848146077418
2.12809991836548,2.19975426739998
2.36001777950467,2.13431571653108
2.47965980430804,2.10009826322647
2.64446592665339,2.06217625079342
3,1.96918249943337
3.18270304789255,1.92677275382958
3.30100235294152,1.89995419323119
3.43001138591633,1.87132727607597
3.49196211032703,1.85575925178247
3.58832776626803,1.83292157280458
3.66591654438806,1.81625173027053
3.77124722918886,1.79197076653699
3.81101114954226,1.78337768390281
4,1.74239875606186
4.04485256912545,1.73296265931081
4.07849840109768,1.72601496831249
4.10481493858468,1.72069696779535
4.25425032706732,1.68805801331962
4.38946243228564,1.66126282575119
4.43941282757263,1.65115763307712
4.50500011444092,1.63825346114909
4.61961588029388,1.61671656237602
4.79496364267811,1.58357735822284
4.82977260253185,1.57730076423476
4.85119470474919,1.57351429009449
4.95039319652335,1.55651154761861
5.22897898773263,1.50792039278996
5.54426195820521,1.45661024784611
5.54449130633988,1.45656550189442
5.5445870883462,1.45654889443384
5.5455651789085,1.456399289963
5.74036280912079,1.39728811468832
5.82412715848293,1.37221636582089
5.99595274284814,1.32060435044261
5.99970720981729,1.31948109764926
6.13030385271466,1.28063107422709
6.22817480231502,1.25195447634087
6.49940579342618,1.17248114480904
6.67104537396659,1.12298965144303
6.89365213325384,1.06063919989822
7,1.03064503596977
7.03448220352383,1.02104453954598
7.10803375524482,1.0006867845484
7.37640235388167,0.927469289235045
7.45776558144505,0.905166793849379
7.49915119463394,0.893997969471656
7.61344463623006,0.863552884638561
7.99882662361535,0.760409856715376
8.45087120570413,0.64337691908263
8.49909862053278,0.630930960112564
8.80274365185545,0.555563033021054
9,0.506584219508381
9.01326938324268,0.503501997002188
9.99831512735193,0.275672459158149
10.4351130943139,0.189095982471183
11,0.0774544523980982
11.1428584410998,0.0590563248576219
11.615203781935,0
13.5294060407946,8.18586399882184E-18
15.2619225930376,1.05136198238356E-17
16.8759697896876,8.35343200139012E-18
17.5944597818197,6.68388212818752E-18
18.3832816464454,4.64501179918399E-18
19.4764263021268,1.49411669870019E-18
19.6832893000986,8.95758417628319E-19
19.992968764043,0
24.1263861707568,0.258338587919609
26.6056104202759,0.413290103514557
31.5021426717729,0.71932336923312
35,0.937939452247311
39.7649333341491,1.23574778563163
39.9575996398926,1.2477894297406
40.5643970629932,1.28571426868439
44.9151992797852,1.55763940723388
48.9634477931586,1.81065493931972
49.8727989196777,1.86748938472717
50.8501121661426,1.92857146263123
54.8303985595703,2.17733936222046
56.8811206179688,2.30550949087036
59.5930034039047,2.47500216499135
60.6993847961155,2.54415100200453
61,2.57355013009898
61.1170564651006,2.58504807429274
61.1745424854587,2.59053663839076
61.4017777090743,2.63466192327439
61.5632934569836,2.66449823512874
61.6582148327555,2.69884866061036
61.8532401532336,2.76564637503401
61.8912075666194,2.79349742681974
62,2.87529583475716
62.0240810474994,2.89381917379723
62.0503252079414,3.02574229469662
62.0400407422615,3.08897277183506
62,3.15938409986912
61.9485812676005,3.24722578147234
61.6746006847975,3.43496538376621
61.1291459587776,3.78519955176204
61.0365591998728,3.82769729804388
61,3.8435533084047
60.9218755422187,3.87577541689226
60.3009634080862,4.13084894675526
60,4.24510978791411
59.6870408564576,4.35587950577591
59.5863394121064,4.38883661381312
59.5107291089522,4.41213170889827
59.1161003112792,4.53449448337781
58.8721516900682,4.60941452644205
58.639082778477,4.66995535987981
58.3460037292212,4.75519191697964
58.1613395248457,4.79819050398629
57.9196636279115,4.86402023748339
57.6825401389039,4.91202385325552
57.4876413474398,4.96026545411106
57.2025534966786,5.00851913273065
56.4755662956055,5.09831374061988
56.2392627796784,5.14277605624945
55.9359190074425,5.17482139499887
55.2728004455566,5.19844478184449
55.1153979909374,5.19999980926514
53.8171111345069,5.19999980926514
53.149558456284,5.19999980926514
51.559445836088,5.19999980926514
48.1929657122852,5.19999980926514
47.0145907999899,5.19999980926514
46.6789283752441,5.19999980926514
42.4697378171834,5.19999980926514
40.8394660949707,5.19999980926514
39.6181955139549,5.20000000871734
35,5.20000043953888
32.9345439644304,5.2000004635605
30.7054067206098,5.20000048948576
28.9789485931396,5.20000088962676
26.6840118491408,5.20000123977661
25.3035188631837,5.20000123977661
22.9578990936279,5.20000123977661
21.5627774207489,5.20037842469721
21.2663936485012,5.2004783424723
20.6974081182889,5.20028830260857
19.5750999450684,5.20003964067943
19.4997801015388,5.19995218447733
18.6702870435184,5.19914359350166
18.6000003814697,5.19908224559873
18.2488027380631,5.19806277600826
18.0199866224518,5.19738990542209
17.7999330359678,5.19644022005243
17.580714608161,5.19501718714565
17.3695310951802,5.19389997497131
17,5.19196750050261
15.9483915750899,5.18132190078849
15,5.17092094712703
14.5325383139421,5.16349071534255
14.3544976867168,5.1600560249118
13.7770241129465,5.14966973834032
13.3284311102577,5.13877201556674
13,5.13221865051803
12.881714930687,5.12855388457531
11,5.07478822967406
10.7188300835244,5.06252454653892
9.37534315087567,5.00776919474409
9.18885648575051,5.00073094519747
9,4.99295068434131
8.61691229431714,4.97507980349042
7.70899003646492,4.92227704536304
7,4.87866400061863
6.88062632838523,4.87166621878271
6.76122584488123,4.86428022808233
5.16191620588875,4.74489599815306
Aug 18, 2013 at 4:10 PM
Edited Aug 18, 2013 at 4:10 PM
I can't reproduce an endless loop. But you have duplicate points in your input (first and last). To close the polygon just do something like
int n = points.Length;

var geometry = new InputGeometry(n);

for (int i = 0; i < n; i++)
{
    geometry.AddPoint(points[i].X, points[i].Y);
}

for (int i = 0; i < n; i++)
{
    geometry.AddSegment(i, (i + 1) % n);
}
Though duplicate points should be handled just fine by the sweepline algorithm. Could you post a complete, working example which leads to the endless loop?
Aug 18, 2013 at 7:34 PM
Thanks for the quick response=) You are right about the endless loop casting to float solved that problem.
for (int i = 0; i < n; i++)
{
    geometry.AddPoint((float)points[i].X, (float)points[i].Y);
}
But i am still getting some other exception "unable to find a triangle on path".How can i get over this? I uploaded an example project as you requested with three different polygon cases=). Thanks again for your help.

ExampleProject
Aug 18, 2013 at 9:37 PM
Edited Aug 18, 2013 at 9:50 PM
I think you are reading your data the wrong way and hence producing some garbage input. Your intention is probably to read floating point values, but if you are trying to parse a number like "6.8275188916581", Convert.ToSingle(string) might not give you what you expect, depending on your system culture (the problem is, that the decimal seperator isn't recognized, and thus you are reading some really large integers). Try reading your data with the following code (and notice the use of the NumberFormatInfo):
static InputGeometry LoadTextFile(string filename)
{
    var points = new List<TriangleNet.Geometry.Point>();

    using (var reader = new StreamReader(filename))
    {
        string[] line;
        double x, y;

        // This is important!
        var format = CultureInfo.InvariantCulture.NumberFormat;

        while (!reader.EndOfStream)
        {
            line = reader.ReadLine().Split(',');

            if (line.Length >= 2)
            {
                x = double.Parse(line[0], format);
                y = double.Parse(line[1], format);
                points.Add(new TriangleNet.Geometry.Point(x, y));
            }
        }
    }

    int n = points.Count;

    if (points[0] == points[n - 1])
    {
        // Remove duplicate point
        points.RemoveAt(n - 1);
        n--;
    }

    var geometry = new InputGeometry(n);

    for (int i = 0; i < n; i++)
    {
        geometry.AddPoint(points[i].X, points[i].Y);
    }

    for (int i = 0; i < n; i++)
    {
        geometry.AddSegment(i, (i + 1) % n);
    }

    return geometry;
}
Aug 19, 2013 at 10:52 AM
I changed the code as you suggested and added more samples this time. There are still plenty of "unable to find triangle on path" exceptions. What am i doing wrong? I checked polygons with rhinoceros they are all simple and closed.

ExampleProject-001
Aug 19, 2013 at 12:44 PM
Edited Aug 19, 2013 at 12:45 PM
Thanks for providing more examples. I can reproduce the problems and will have a look on it as soon as possible. Using the default triangulation algorithm (divide and conquer), only the sample4.96 will fail (sweepline works for this one).

I will open two work items (one for sweepline, one for d&c), so you can track progress on the issue.
Aug 19, 2013 at 12:46 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Aug 20, 2013 at 4:01 PM
Edited Aug 20, 2013 at 4:04 PM
Please check out the latest code and use the default divide and conquer algorithm for triangulation. Sweepline will still fail on some of your polygons, but so does the original C code (for example sample4.36 will crash and sample4.37 displays an error message "Internal error in finddirection(): Unable to find a triangle [...]").

So at the moment I have no plans to dig deeper.
Aug 21, 2013 at 7:33 AM
Thanks for checking it quickly I will try out the latest code.