Delaunay stay in an infinite loop for the attached dataset

[jzy3d]

Although usually working good, delaunay algorithm hangs with the console message: Warning, ajTriangle(A,B,C) expects points in counterclockwise order. Point [x=17449.85546875, y=0.43204736709594727, z=52.999969482421875]Point [x=15847.58984375, y=0.40541332960128784, z=52.999977111816406]Point [x=9358.6005859375, y=0.29754865169525146, z=53.00000762939453]

Source dataset stand at end of issue.

Delaunay's implementation stand in https://github.com/jzy3d/jzy3d-api/tree/master/jzy3d-jdt-core

---

package org.jzy3d.issues.issue15;

import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List;

import org.jzy3d.analysis.AbstractAnalysis; import org.jzy3d.analysis.AnalysisLauncher; import org.jzy3d.chart.Chart; import org.jzy3d.colors.Color; import org.jzy3d.colors.ColorMapper; import org.jzy3d.colors.colormaps.ColorMapRainbow; import org.jzy3d.maths.Coord3d; import org.jzy3d.plot3d.builder.delaunay.DelaunayTessellatorV2; import org.jzy3d.plot3d.primitives.Shape; import org.jzy3d.plot3d.rendering.canvas.Quality;

public class DelaunayTest extends AbstractAnalysis { public static void main(String[] args) throws Exception { AnalysisLauncher.open(new DelaunayTest()); }

@Override
public void init() throws IOException {
    List<Coord3d> coords = getSurf();

    DelaunayTessellatorV2 tesselator = new DelaunayTessellatorV2();
    final Shape surface = (Shape)tesselator.build(coords);
    surface.setColorMapper(new ColorMapper(new ColorMapRainbow(), surface.getBounds().getZmin(), surface.getBounds().getZmax(), new Color(1, 1, 1, .5f)));
    surface.setFaceDisplayed(true);
    surface.setWireframeDisplayed(true);
    surface.setWireframeColor(Color.BLACK);

    chart = new Chart(Quality.Advanced, getCanvasType());
    chart.getScene().getGraph().add(surface);
}

public List<Coord3d> getSurf() throws IOException {
    File testFile = new File("testPoints.csv");
    System.out.println(testFile.getAbsolutePath());

    BufferedReader reader = new BufferedReader(new FileReader("data/issue15.csv"));

    List<Coord3d> coords = new ArrayList<Coord3d>();

    String line = null;
    while ((line = reader.readLine()) != null) {
        String[] values = line.split(", ");
        assert (values.length == 3);
        Double aVal = Double.parseDouble(values[0]);
        Double bVal = Double.parseDouble(values[1]);
        Double cVal = Double.parseDouble(values[2]);
        coords.add(new Coord3d(aVal, bVal, cVal));
    }
    reader.close();
    return coords;
}

}

---

data/issues.csv

7161.0483, 0.30963045, 151.00002 16255.689, 0.48511374, 199.99998 9131.444, 0.298237, 62.00001 13330.93, 0.42806372, 183.0 13717.669, 0.39729, 107.999985 9571.9795, 0.36061943, 173.00002 17343.656, 0.4327622, 57.99997 6057.7993, 0.3061724, 181.00002 5594.6025, 0.29698473, 178.00002 14249.807, 0.40911177, 113.999985 14637.931, 0.44185314, 167.00002 13768.088, 0.4323543, 177.0 15791.425, 0.40745592, 58.999977 13684.161, 0.4309592, 177.0 9536.3545, 0.32629707, 105.00001 5962.716, 0.30459186, 181.00002 5973.0747, 0.30426803, 180.00002 9488.609, 0.32451135, 103.0 16533.953, 0.45104876, 122.0 7026.6133, 0.30441958, 145.0 7387.569, 0.2970268, 118.000015 13783.514, 0.39739245, 105.999985 9094.304, 0.35416722, 176.00003 5741.862, 0.29893655, 177.00002 17380.959, 0.4725688, 137.0 13739.271, 0.4026094, 117.99998 7224.8184, 0.2953135, 120.000015 5731.4233, 0.30025113, 180.00002 17195.875, 0.4694922, 137.0 9296.218, 0.30544025, 71.00001 14859.228, 0.4455317, 167.0 17449.855, 0.43204737, 52.99997 9597.583, 0.3263228, 103.00001 5367.045, 0.30560288, 203.0 6803.886, 0.30815774, 160.0 16513.312, 0.4526898, 125.99999 17536.574, 0.43348885, 52.99997 7285.669, 0.2973171, 122.000015 15847.59, 0.40541333, 52.999977 7305.12, 0.29664835, 120.000015 9464.553, 0.3280797, 111.00001 9324.872, 0.32476577, 109.00001 9017.249, 0.3533824, 177.00002 13190.681, 0.42474034, 181.0 6780.183, 0.31123593, 167.0 9181.413, 0.35611126, 177.00003 7605.19, 0.30362046, 124.00002 8898.659, 0.3355381, 145.0 16808.873, 0.48934886, 190.0 16706.693, 0.4559043, 126.0 8485.048, 0.35693657, 202.00003 9385.696, 0.32280064, 103.00001 7032.556, 0.30997473, 156.00002 13538.433, 0.42804077, 176.0 8731.88, 0.36550388, 211.00003 16141.964, 0.494136, 221.99998 7365.892, 0.30361092, 132.00002 6847.507, 0.3054106, 153.00002 17492.932, 0.47443008, 137.0 7460.233, 0.29922673, 120.000015 11913.204, 0.37225518, 117.99999 6958.781, 0.30329204, 145.0 11755.889, 0.36914414, 116.99999 9213.817, 0.32440785, 112.00001 8410.88, 0.360664, 212.00002 16614.426, 0.45238644, 122.0 13450.875, 0.42856944, 180.0 16287.485, 0.48564228, 200.0 9404.828, 0.30625358, 69.00001 17024.838, 0.4929388, 190.0 16978.607, 0.4921703, 190.0 9102.313, 0.3572766, 182.00003 9812.29, 0.364118, 172.00002 8548.596, 0.35848895, 203.00003 13805.789, 0.39627463, 102.99998 7507.1665, 0.29802278, 116.000015 8843.137, 0.35396042, 184.00003 5907.287, 0.30317447, 180.00002 5758.3403, 0.2997065, 178.00002 14927.74, 0.44667056, 167.0 9572.025, 0.30159238, 54.00001 10065.506, 0.3440216, 123.00004 13410.181, 0.42838904, 181.0 9195.894, 0.32063767, 105.00001 8886.632, 0.36758024, 210.00003 17353.852, 0.4721182, 137.0 13622.225, 0.43141773, 180.0 13905.241, 0.40338415, 113.999985 11114.987, 0.333193, 66.0 9358.601, 0.29754865, 53.000008 7012.961, 0.30369663, 144.0 7014.125, 0.30470803, 146.0 5783.135, 0.29863054, 175.00002 16718.389, 0.45461062, 123.0 5694.3413, 0.29864264, 178.00002 6464.2197, 0.30300757, 161.0 7456.811, 0.30413017, 130.00002 9761.314, 0.36376667, 173.00002 13676.086, 0.431321, 178.0 8922.619, 0.3349443, 143.0 5971.3345, 0.29927877, 170.00002 9314.405, 0.32260767, 105.00001 9506.423, 0.35704952, 168.00002 8806.123, 0.34094435, 159.0 7610.411, 0.30172312, 120.000015 9328.566, 0.35954943, 179.00003 16856.064, 0.49013332, 190.0 8944.172, 0.3685367, 210.00003 7655.6064, 0.3029704, 121.00002 11374.295, 0.33055896, 52.0

[jzy3d]

Remark from Benoît (https://github.com/benoit74)

https://github.com/jzy3d/jzy3d-api/blob/master/jzy3d-jdt-core/src/main/java/il/ac/idc/jdt/Triangle.java

Ligne 204 : à mon avis c'est plutôt "return false" (si le point est à un coin du triangle, dans ce cas il est sur la frontière et vu que la frontière ne fait pas partie du triangle dans cette fonction ...)

in english : it should be "return false" (if a point is at the corner of a triangle, then it stand on the edge... but in this function the border does not take part of the triangle)