Overlapping Constraints #51
Comments
|
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 ***@***.***> 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
<#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 ***@***.***> 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
<#51>, or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AEWJDYN6KXKPSYXDNNSK2GTSUDMADANCNFSM4UVDJOMA>
.
|
Sure, no worries.
Good hint. I am solely using Polygons, but it might also be possible to use lines. I have to think about that.
Yeah, JTS is what I am using for all the topological calculations. On some constraints, I use the 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.
Actually, regarding this topic, I have not checked. Regarding a lot of other things, the articles help a lot!
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!
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.
:-) 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. |
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:
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.
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 ***@***.***> 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
<#51 (comment)>,
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. |
That sounds like a reasonable brute force :-)
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.
Yeah, that is true.
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.
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 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 ***@***.***> 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
<#51 (comment)>,
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.
The text was updated successfully, but these errors were encountered: