Overlapping Constraints about tinfour HOT 12 OPEN

from tinfour.

from tinfour.

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 differenceoperation 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.

from tinfour.

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.

from tinfour.

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.

from tinfour.

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.

from tinfour.

from tinfour.

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.

from tinfour.

1. Build the mesh, constraints and all.
2. Compute the artificial points for insertion, keeping them in a separate list.
3. Rebuild the mesh from scratch, adding the artificial points up front.
4. 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?

from tinfour.

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.

from tinfour.

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

from tinfour.

from tinfour.