5

I am referring to the paper here, section 2.6.1.

Is there an existing library ( in C++ or .Net) that already has this implemented? Namely, taking two Triangulated Irregular Network (TIN), we create a new TIN by adding or subtracting the two.

Edit: I afraid applying polygon boolean operation between each triangle in one TIN against all the triangles in other TIN is not efficient; from what I know there ought to be efficient algorithm that computes polygon overlay operation; it is this kind of library that I'm looking for.

Improve this question

4 Answers 4

Reset to default
2

Constrained triangulation or boolean operation code should work. Promising places to start looking include

Michael Leonov's guide to 2D boolean operations. This is exactly what you're looking for, but it's a little old. Leonov sells a .Net library, Polyboolean.

CGAL's 2D Triangulation

MathTools.net guide to computational geometry algorithms

Google's computational geometry software directory

"Computational Geometry Software Libraries"

Improve this answer
8
  • @whuber, I think the libraries you introduce touched only on polygon boolean operation between the two. But when you have a lot of triangles and you want to find the polygon boolean operation, you will need something more efficient.
    – Graviton
    Jan 4, 2011 at 2:10
  • I don't understand what you are suggesting by "more efficient": these libraries are intended to implement some of the most efficient algorithms available. Did you look at any of the timings reported on these web sites? Operations with millions of triangles take only tens of seconds--on Pentium IIs! After intersecting two TINs (a basic boolean operation), it's a simple exercise to look up the attributes of the two parent triangles in each output triangle and subtract (or add, etc.) their values: all the geometric work is already done.
    – whuber
    Jan 4, 2011 at 16:10
  • @whuber, like I said. If you are intersecting two polygons, then your suggestion is fine. But let's say you have to repeat this for a million times, then you will need a better algorithm. It's much like when you want to find two line segment intersection, you can use your high school algebra to do, but if you want to do one million two line segment intersection, then you need something like Bentley Ottmann algorithm.
    – Graviton
    Jan 6, 2011 at 1:13
  • @Ngu Soon Hui "Repeat this"? What does "this" mean? These libraries overlay entire TINs, not just one segment on another. Have you taken a look at any of them?
    – whuber
    Jan 6, 2011 at 3:28
  • @whuber,"this" means the two polygon overlay operation. And so far all the libraries here concern themselves with the overlay of two polygon (Yes I have taken a look at all of them, and none of them concern themselves with the overlay of 1 million triangles against another 1 million).But what if I want if I have two TIN, both with 1 million polygon, and I want to overlay those two TINs? You can't expect me to go through each triangle of both TINS and compute the overlay using the libraries you suggest above; that would be very inefficient.
    – Graviton
    Jan 6, 2011 at 6:23
1

I'm not really sure what you want to do: if you want to substract both surfaces, I would create a grid and make the substraction there. Apart from the fact that I think there would be better interpolation methods than using a tin.

If you want to add new points or remove points running the triangulation again only takes a few seconds.

Thinking about it further: if you create a set with only the points of both triangulation surfaces, and overlay that with these surfaces, you can then calculate the sum/difference in each point and then run the triangulation again. I'm pretty sure this is the most efficient way to do it.

If you really want to do polygon overlay: very often used is: http://www.cs.man.ac.uk/~toby/alan/software/

a newer one, which claims to be faster and with a more liberal license: http://angusj.com/delphi/clipper.php

Improve this answer
9
  • @johanvdw, I think doing polygon boolean operation for each polygon on one to one basis is going to be inefficient. So maybe there are some line sweeping algorithm that handles a lot of polygon intersecting with each other?
    – Graviton
    Jan 4, 2011 at 8:57
  • Check my addition on only interpolating the points of the triangulation.
    – johanvdw
    Jan 4, 2011 at 9:05
  • @johanvdw, I think you misunderstand my point; I am OK with the polygon boolean operation, but my problem is now I have to do a lot of it that doing it one by one is not going to be efficient. So I would need a better algorithm for that.
    – Graviton
    Jan 4, 2011 at 13:06
  • +1 For suggesting the pointwise + retriangulation solution. Although it might not respect (i.e., refine) the two original triangulations, you're right that it has to be the fastest way to subtract the TINs. It's likely much faster than using a conversion to grids, too.
    – whuber
    Jan 4, 2011 at 16:13
  • @Graviton: This suggestion doesn't do anything "one by one". It involves just four steps. (1) Interpolate the values of the first TIN onto the vertices of the second TIN. (2) Interpolate the values of the second TIN onto the vertices of the first TIN. (3) Triangulate the union of the vertices. (4) Compute the sum/difference at each vertex. Total computational effort (for an efficient triangulation in step 3 and efficient point-in-polygon search in steps 1 & 2) is O((m+n)lg(m+n)) for m+n vertices. It is not possible to do better than that!
    – whuber
    Jan 5, 2011 at 15:07
0

This might do it.

Delaunay's TIN Project

Otherwise you might need to use esri software. There are probably "Many" applications already built with this in it.

ESRI

Improve this answer
2
  • not to sure about it; this seems to be to be an implementation on Delaunay triangulation, but it makes no mention about how to overlay two TINs together.
    – Graviton
    Jan 3, 2011 at 14:06
  • My apology, I thought that was what the demo program was showing.
    – Brad Nesom
    Jan 3, 2011 at 14:23
0

A lot of people rate 12D as one of the best software packages for TIN analysis. I had some training in it a few years back, and used it for creating flood depth grids. Comparing the results against Esri, GRASS, and Mapinfo's Vertical Mapper, 12D was def the quickest and most accurate package.

Perhaps request a trial license?

Improve this answer
1
  • I'm looking for TIN overlay library that I can write my code on top of it, not a complete product.
    – Graviton
    Jan 4, 2011 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.