Open mlthlschr opened 3 years ago
I'm at work right now and cannot look at this too much. I used to have a utility that looked for intersecting constraints but I don't have it here. I'll look later.
Couple of questions. Are these lines or polygons? Lines are allowed to intersect. But the must include vertices at points of intersection.
Were the articles on the Tinfour wiki any help?
Also, ENC's are an awesome topic. I'd love to hear more about your work.
Gary
On Thu, Dec 10, 2020, 9:34 AM mlthlschr notifications@github.com wrote:
Hi Gary, first of all, thanks for the amazing project. I am currently using it to triangulate enc/s57 data in my thesis.
One annoyance I often meet during my triangulations is some failing triangulation (usually in step 2 of IncrementalTin.processConstraint, h or c == null). I assume this happens because I added another constraint, which unfortunately is overlapping another one somewhere.
I built my own logic which checks for intersections before adding it to tinfour, however the robustness of this approach sometimes is not sufficient.
Can you estimate whether it would be possible to add this feature and how much work it would require? I am not too much into the delaunay algorithm business, that's why for me it is hard to tell.
If you say that it is possible with a fair amount of work, than it would be great to have that feature. Maybe I could help with that.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/gwlucastrig/Tinfour/issues/51, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEWJDYN6KXKPSYXDNNSK2GTSUDMADANCNFSM4UVDJOMA .
Also, there is an open source project called Java JTS which implements a high quality set of geometry classes. They may be useful in terms of finding if polygons overlap and solving for the union or intersections.
I haven't looked at the S57 spec in a while, but I sort of remember the general layout of the thing.
On Thu, Dec 10, 2020, 9:34 AM mlthlschr notifications@github.com wrote:
Hi Gary, first of all, thanks for the amazing project. I am currently using it to triangulate enc/s57 data in my thesis.
One annoyance I often meet during my triangulations is some failing triangulation (usually in step 2 of IncrementalTin.processConstraint, h or c == null). I assume this happens because I added another constraint, which unfortunately is overlapping another one somewhere.
I built my own logic which checks for intersections before adding it to tinfour, however the robustness of this approach sometimes is not sufficient.
Can you estimate whether it would be possible to add this feature and how much work it would require? I am not too much into the delaunay algorithm business, that's why for me it is hard to tell.
If you say that it is possible with a fair amount of work, than it would be great to have that feature. Maybe I could help with that.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/gwlucastrig/Tinfour/issues/51, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEWJDYN6KXKPSYXDNNSK2GTSUDMADANCNFSM4UVDJOMA .
I'm at work right now and cannot look at this too much.
Sure, no worries.
Are these lines or polygons? Lines are allowed to intersect.
Good hint. I am solely using Polygons, but it might also be possible to use lines. I have to think about that.
Java JTS which implements a high quality set of geometry classes
Yeah, JTS is what I am using for all the topological calculations. On some constraints, I use the union
operation, which has been, until now, quite stable. The difference
operation sometimes crashes due to robustness issues (which is also quite heavily described in the jts faq). I am still investigating this and have not found a proper reason for this behavior.
Another way to avoid this could be to use the union operation, take this as constrained polygon, and the omitted lines inside this polygon could be inserted as simple lines.
Were the articles on the Tinfour wiki any help?
Actually, regarding this topic, I have not checked. Regarding a lot of other things, the articles help a lot!
Also, ENC's are an awesome topic. I'd love to hear more about your work
Yes, they truly are. The basic idea of my work is to calculate routes on triangulated S57 data. These triangulations not only represent navigable and non navigable areas, but als respect specific important navigation areas.
Thus I hope for routes which are more organic than other methods currently used in this field (as well as more performant due to the nature of the triangles). Also, the routes should be more reasonable in the navigational sense, as I am respecting not only the depth but also certain meta data.
The line constraints are essentially "breaklines". Typically, they are used for things like cliffs or roads or rivers to indicate a discontinuity in the surface. If you add them, the triangles will not cross breaklines but will line up along its edges. For harbor navigation, I can see them being useful for things like a channel, where you would want to not have triangles crossing the channel boundary. But line features aren't great at representing area features. And in terms of representing things like navigable water, I think that polygons are your primary solution. Also, you should be able to nest polygon constraints (for instance, to represent an underwater obstruction or a wreck in the middle of an area of otherwise navigable water).
It is so cool to see Tinfour being used for a navigation problem.
Thanks for your feedback!
The line constraints are essentially "breaklines". [...] the triangles will not cross breaklines but will line up along its edges [...] where you would want to not have triangles crossing the channel boundary.
Yes exactly. This is where the problem usually happens. I am overlaying channels/navigation areas, where I simply want to have edges marking these areas, on top of my non navigable areas. Both of them are polygons. Maybe a better way would be to keep the non navigable areas as polygons, but use the other ones as lines. Then I would simply need to check for line intersections.
For me, we can close this issue. However, It would be great to hear some other thoughts of you.
It is so cool to see Tinfour being used for a navigation problem.
:-) I chose it for its speed and quality of results. Also, the contour generation is really handy when calculating these navigable areas (even though interpolated values should not be used for navigation, right now it is feasible to prove the point).
One other feature which would be awesome: the possibility of calculating conforming delaunay triangulations, where all edges satisfy the delaunay criterion. It would make calculation of routes with safety margins much easier. I did some shallow research and found that it is not quite trivial to implement.
One other feature which would be awesome: the possibility of calculating conforming delaunay triangulations, where all edges satisfy the delaunay criterion. It would make calculation of routes with safety margins much easier. I did some shallow research and found that it is not quite trivial to implement.
Sorry, let me specify that. Of course, tinfour is already capable of doing a tremendous job at creating conforming delaunay triangulations. However, in my specific case it sometimes does not "feel" like a true CDT as I am having lots of thin, long triangles (such as those ashore on this picture here).
I see it is already on the roadmap. I might be able to take a look at that, but for now I have to focus on my thesis.
Oh, I see... What you're looking for is known as "Delaunay Refinement". It's a technique of improving the appearance of triangulation by inserting artificial vertices, or "Steiner points" into the mesh. The idea is that it inserts vertices into the interior of "skinny" triangles, forcing the Delaunay to reorganize them into a mesh with more "robust" tirangles. There are a couple of algoirithms out there. I've researched Rupert's method and it seems the best suited for a Tinfour implementation. Chew's second algorithm produces slightly more optimal results, but is harder to implement. Generally, the Z values for the artificial vertices are obtained through interpolation over the original mesh and then they are added.
I've been wanting to implement Delaunay Refinement, but haven't had the time to work on it. The challenge in implementing Rupert's method is twofold. First, it involves inserting points after the constraints have been added. The current Tinfour implementation does not allow insertion or removal of vertices after the constraints are added, so I would need to enhance that. Then I'd have to implement Rupert logic itself, making sure that I addressed efficiency issues.
Anyway, there is a brute force solution that will produce somewhat better looking triangles. I used a variation of it when I was working on the Reservoir Volume Model and addressed the "flat triangle" issue. The steps are:
The results wouldn't be as good as Rupert or Chew, but they would reduce the incidence of skinny triangles.
I can try to write some example code for you, but my time is a bit constrained and I don't know if I would get it done in a quick enough time-frame for you. You could look at the Simple Volumetric Model (SVM) code for an example, but I am not sure whether you should use the interpolation I used for that special application or if you should just use the more generic TriangleFacetInterpolator for your purposes.
On Mon, Dec 14, 2020 at 4:20 PM mlthlschr notifications@github.com wrote:
One other feature which would be awesome: the possibility of calculating conforming delaunay triangulations, where all edges satisfy the delaunay criterion. It would make calculation of routes with safety margins much easier. I did some shallow research and found that it is not quite trivial to implement.
Sorry, let me specify that. Of course, tinfour is already capable of doing a tremendous job at creating conforming delaunay triangulations. However, in my specific case it sometimes does not "feel" like a true CDT as I am having lots of thin, long triangles (such as those ashore on this picture here https://raw.githubusercontent.com/wiki/gwlucastrig/Tinfour/images/AboutTheCDT/PearlSoundings01b.jpg .
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/gwlucastrig/Tinfour/issues/51#issuecomment-744717523, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEWJDYJYPRZCGLGYHC7DZ5LSUZ6R5ANCNFSM4UVDJOMA .
A couple of quick questions. Are you working in geographic coordinates (latitude, longitude) or in a projected coordinate system? If you are using a projected coordinate system, do you have the specifications for your map projection and scale (data frame)? The criterion for what makes a "skinny" triangle will depend on your coordinate system.
Are the triangles you wish to refine in the water or on land? It might make a difference in terms of how I recommend generating artificial points. I suggested the TriangleFacetInterpolator because it guarantees that the interpolated point falls within the numeric range of the three vertices of the enclosing triangle... So it is the most defensible when you present your results.
If you need elevation data for the land points, I can give you some leads on using the Shuttle Radar Topography Mission (SRTM) data which provides relatively high-resolution data over most of the world. I've recently submitted an enhancement to the Apache Commons Imaging project to read SRTM data. Although they haven't yet accepted my changes into their code base, I could provide you with my version. I've also been looking into the GEBCO bathymetric data for a different project (https://github.com/gwlucastrig/gridfour) but it is probably not at sufficient resolution for your needs.
On a completely different topic, do you have a requirement to plot the Delaunay data on a map? Tinfour doesn't have any direct support for that, but I can discuss ideas if you'd like.
- Build the mesh, constraints and all.
- Compute the artificial points for insertion, keeping them in a separate list.
- Rebuild the mesh from scratch, adding the artificial points up front.
- Repeat as necessary.
That sounds like a reasonable brute force :-)
I can try to write some example code for you, but my time is a bit constrained and I don't know if I would get it done in a quick enough time-frame for you.
That is so kind! But no worries, I think it will not get into the thesis anyways, as I still have other problems to tackle.
more generic TriangleFacetInterpolator for your purposes [...] It might make a difference in terms of how I recommend generating artificial points. I suggested the TriangleFacetInterpolator because it guarantees that the interpolated point falls within the numeric range of the three vertices of the enclosing triangle... So it is the most defensible when you present your results.
Yeah, that is true.
Are the triangles you wish to refine in the water or on land?
The triangles to be refined are in the water. Actually, I could also discard all the triangles on land, as they do not have any relevance in my pathfinding.
On a completely different topic, do you have a requirement to plot the Delaunay data on a map? Tinfour doesn't have any direct support for that, but I can discuss ideas if you'd like.
I do not have the requirement, but it makes it a lot easier to debug. Also, I think it would be great to have one or two figures of the triangulation in the thesis. I have two ways right now, namely iterating over all edges and converting them to geojson, which I can display in leaflet together with the NOAA S57 layers. For a more scientific plot I am using lets plot, which is basically using Apache Batik as Backend. But both ways have their flaws and are also quite hacky solutions. What would be your recommendation/idea?
I had an idea that, if you had a GeoTIFF in the same Coordinate Reference system (CRS) as your TIN, you could use the Tinfour code, Java's Graphics2D API, and the Apache Commons Imaging library to render your Delaunay triangulation (and other 2D features) directly to the GeoTIFF image. The GeoTIFF could be either an aerial photograph or a conventional map. You could also use the Java Graphics2D functions to draw whatever elements you want to put into the image. You could even use the Tinfour Shapefile classes to draw from Shapefiles (again, provided that the Shapefiles were in the same coordinate reference system).
Again, this is really dependent on having the same coordinate reference system as your source. If the CRS is not the same, then you start needing to transform coordinates and the problem is really outside the scope of what Tinfour does. In such a case, the problem really requires a GIS package to handle it properly.
Unfortunately, I do not use geotiffs. And coordinate-wise I am simply using WGS84, as it is being used in the s57.
By the way, have you ever thought about publishing this project in some journal, e.g. Journal of Open Research Software? Or have you published it already? Your documentation looks like it can be easily reduced to a paper, and for me it would be more easy to cite :-D
Never thought Tinfour was worthy of a peer-reviewed journal. I'll have a look. Since I do not have an academic affiliation, I don't have an institution willing to fund a publication. 400 pounds UK is pretty steep. But maybe they will waive their fee in this case.
On Wed, Dec 16, 2020, 6:56 AM mlthlschr notifications@github.com wrote:
Unfortunately, I do not use geotiffs. And coordinate-wise I am simply using WGS84, as it is being used in the s57.
By the way, have you ever thought about publishing this project in some journal, e.g. Journal of Open Research Software https://openresearchsoftware.metajnl.com/? Or have you published it already? Your documentation looks like it can be easily reduced to a paper, and for me it would be more easy to cite :-D
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/gwlucastrig/Tinfour/issues/51#issuecomment-746175556, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEWJDYMSY6CJYM5RGMSMRJLSVCN6RANCNFSM4UVDJOMA .
Hi Gary, first of all, thanks for the amazing project. I am currently using it to triangulate enc/s57 data in my thesis.
One annoyance I often meet during my triangulations is some failing triangulation (usually in step 2 of
IncrementalTin.processConstraint
,h or c == null
). I assume this happens because I added another constraint, which unfortunately is overlapping another one somewhere.I built my own logic which checks for intersections before adding it to tinfour, however the robustness of this approach sometimes is not sufficient.
Can you estimate whether it would be possible to add the possibility of adding overlapping constraints and how much work it would require? I am not too much into the delaunay algorithm business, that's why for me it is hard to tell.
If you say that it is possible with a fair amount of work, than it would be great to have that feature. Maybe I could help with that.