How to import a constructed TIN data, instead of rebuilding it with tinfour IIncrementalTin

[Little5ive]

I have a TIN data stored in a file, which contains points information as well as triangulation information like "0, 2, 5", meaning the three points form a triangulation in the TIN. Now I want to import the constructed TIN data into the tinfour, instead of rebuilding it with tinfour IIncrementalTin class. Does tinfour provide such functionality?

[gwlucastrig]

Regrettably, Tinfour does not currently implement the feature that you describe. Nobody has ever requested it before. I believe that I could implement something like that. I do not know how much time it would take me to do so. I cannot commit to implementing the feature for you, but I will consider the feasibility. To do so, I will need a few more details.

Do the triangles you provide comply with the Delaunay criterion?

Is the triangular mesh you would provide complete (no gaps or missing triangles)? Does the outer boundary of the set of triangles form a convex polygon?

How many triangles are in your input data set?

Could you provide more detail about the format of the data that you would wish to use?

How much time would be available to implement this feature? When would you need it?

Gary

On Sat, Apr 27, 2024 at 10:33 PM 桑燕五 @.***> wrote:

I have a TIN data stored in a file, which contains points information as well as triangulation information like "0, 2, 5", meaning the three points form a triangulation in the TIN. Now I want to import the constructed TIN data into the tinfour, instead of rebuilding it with tinfour IIncrementalTin class. Does tinfour provide such functionality?

— Reply to this email directly, view it on GitHub https://github.com/gwlucastrig/Tinfour/issues/109, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEWJDYOOUT5QHJZPHTVVKKLY7RNXDAVCNFSM6AAAAABG4SWOTGVHI2DSMVQWIX3LMV43ASLTON2WKOZSGI3DOMZQGM2DEMA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[Little5ive]

Hi Gary. Thank you for your response! Sorry for the late reply! It's on holiday, and some of your questions need to be confirmed with my colleagues. Here is some detailed information:

• The Delaunay criterion is not guaranteed.
• Most of the input trianglar mesh is complete, with no gaps, missing triangles or overlaps, so I figure these problems can be omitted. But usually the outer boundary is not convex, because the triangular mesh may represents a riverbank, a section of a highway, etc.
• The number of input triangles varies from dozens to hundreds of thousands.
• • The file format is like this

    <P id="0">-65358.222999999984 -29870.359000000004 32.074</P>
    <P id="1">-65359.241217474992 -29868.362104055628 33.094811125069</P>
    <P id="2">-65359.228427765956 -29868.362039818014 33.081963602181</P>
    <P id="3">-65359.492652951267 -29869.089984104896 33.348112344488</P>
    //...
    <P id="175">-65359.235999999983 -29868.347000000002 33.074</P>
    <P id="176">-65360.215999999986 -29868.367000000002 34.074</P>
    <P id="177">-65359.93101586181 -29870.359000000004 32.074</P>
    <F>0 1 2</F>
    <F>2 5 6</F>
    //...
    <F>99 6 5</F>
    <F>176 6 172</F>

    Here the tag "P" represents a 3D point(x, y, z) with attribute "id" the id of the point. And the tag "F" containing 3 integers represents a triangle. The 3 integers means the id of three points that forms a triangle.

We hope to input the TIN date from the file, and then calculate the interpolation according to the (x, y) value of the Excavator bucket, to tell how deep the excavator should dig. For now, we just ignore the triangle information in the file, just inputting all points to tinfour and then regenerate Delaunay TIN, which brings some apparent problems. We are looking for solutions for this problem, but I 'm also not sure about the workload. So it will be grateful if you can provide a implemention solution. Hope my question doesn't take you much time.

Thank you again for your response!

[gwlucastrig]

I am working on a modification to the IncrementalTIN class to see if I can support you on this. It will probably take me a couple of weeks since I have another obligation I have to attend to. Would it be possible to supply a test file for me to use for development?

I don't know whether we will encounter problems in working with non-Delaunay data sets. We will not know whether there are problems until we can test the implementation.

You may find it useful to visit the Tinfour wiki and read the article Using Polygon-based Constraints.

There is also an article on Iterating through vertices, edges, and triangles.

Gary

P.S. Will you be giving Tinfour a name in Chinese? If so, I would be curious to learn what you use. The name doesn't need to be a literal translation of the English. The "four" in the name doesn't actually refer to the number four. I pciked "four" because it is the French word for "oven". So you could use something like "TIN oven" or "TIN fire". Or maybe you have better idea.

[Little5ive]

Sure! I will send you a test file to your email later on.

I have read the articles on the wiki page before. But still I feel it a big challenge to me to implement the function(sigh...

As for a Chinese name, I come up with "三角炉". Since TIN is called "不规则三角网" in Chinese, which can be short to "三角", and the word "oven" means "炉子". So "三角炉" is what I got.

[gwlucastrig]

I am working on your request. There are a few challenges in the implementation. These challenges may make Tinfour unsuited to your problem. At this point, I do not know whether that assessment is correct. But, since you already have triangles from your own data systems, perhaps it would be useful to work from them directly. I am, of course, motivated to have people use Tinfour. But I do not want to steer you in the wrong direction. It is possible that you may solve your problem using another approach.

One other possible solution is to use original input data, sample elevations as inputs and your bounding polygons as constraints with the existing IncrementalTIN class. I can give you more information on that if you are interested.

Based on your description of the excavator problem above, I hypothesize that you have two items of interest. First, you would like to interpolate a depth at a certain point to know how deep you have to dig. Second, you would want to compute how much material you need to dig (and subsequently transport). You can interpolate from a triangle directly. The math is straightforward, and you can find an example in Tinfour's TriangularFacetInterpolator class. The volume calculation is described in my notes on Using the Delaunay to Compute Lake Volume. The math for the calculation is taken from The Math Pages Volume Under a Triangle

The Challenges

I looked at the existing interpolators and they are not suited to your data. Tinfour's best interpolator uses the Natural Neighbor Interpolation method. Natural Neighbors depends on the triangulation being properly Delaunay. So it won't work with your traingle set. The alternate interpolator is the TriangularFacetInterpolator. It does a good job, but it depends on the triangulation being fully populated (with no holes). I am looking at a method to "fill in" the missing triangles based on your data set. But the implementation will take some time.

Hope this information helps. I wanted to update you on my slow progress so that you would not delay your project while waiting for me to come up with a solution.

[Little5ive]

Thanks for your advice!

One other possible solution is to use original input data, sample elevations as inputs and your bounding polygons as constraints with the existing IncrementalTIN class. I can give you more information on that if you are interested.

This is similar to what we a doing now, except that we have trouble getting the boundary of the input:

List<Vertex> vertices = new ArrayList<>();
// read the file, add points to vertices
//...
IncrementalTin oriTin = new IncrementalTin();
oriTin.add(vertices, null);
IInterpolatorOverTin interpolator = new NaturalNeighborInterpolator(oriTin);

My origional idea is to reconstruct the TIN structure and then gather the bound polygons through an ergodic. But it seems not viable now.

The volume calculation is not in need for now, since we only have the proposed elevation but no existing elevation information. But I have read the articles about the Simple Volumetric Model (SVM) in the TinfourDocs. Will refer to that if needed.

We're also looking into other options. There're 2 options in progress:

• Recently I found that the JTS provides a method to construct a custmized TIN data by TriangulationBuilder.build() method(here is the javadoc: https://locationtech.github.io/jts/javadoc/org/locationtech/jts/triangulate/tri/TriangulationBuilder.html). It can build a TIN that satisfies quadedge structure from a list of triangles, Yet it lacks the ability of interpolation.

• Another direction is to fit a mathmatical interpolator using the points of the input. It can be managed with Apache Commons Math library(section 4.4 at page https://commons.apache.org/proper/commons-math/userguide/analysis.html). This is simpler, but also loses the structure information including the boundary.

I understand that this request is kind of niche. This is more of a business scenario issue rather than a technical one. So please don't let it bother you too much. Thank you again for your advice!