LogoCDT: incorrect result with restoreConformity = true about tinfour HOT 13 CLOSED

from tinfour.

JTS validation - no error

Integrity Check Results:
No Error Detected
No Delaunay violations detected

restoreConformity=FALSE

restoreConformity=TRUE

from tinfour.

from tinfour.

The picture was a big help. Thanks again.

The issue occurs when the restore-conformity operations create new edges. For example, note that the left edge of the letter D gets split into two smaller edges when conformity is restored. Unfortunately, the code is not correctly transcribing all the area-related attributes when the new edges are created. I will be reviewing the code and making sure that these get added. Doing so will require some care because the details are important to the correct functioning of the code. I intend to make these changes in the incremental-TIN classes, but it may be better to add a new "edge-split" method to the edge pools to accomplish this.

from tinfour.

Martin,

While you're waiting for me, here's something you can try. In SemiVirtualIncrementalTin.java, about line 2120, there is a line that reads am.setConstrained(mb.getConstraintIndex()). On the next line, add the following block

if(mb.isConstrainedAreaMember()){ am.setConstrainedAreaMemberFlag(); }

This occurs in the restoreConformity method where the line is split. I need to check my notes and think a bit about the way the constraint flags are set. This may be all that's needed. But there may be a few more changes required, particularly with regard to preserving which side of the edge the area flags are assigned to.

In the line above, "mb" is the original line before the split, "am" is the new line that was created.

from tinfour.

I am working on a fix for this issue. The temporary fix that I suggest to Martin will become part of the permanent code. I hope to have an update ready sometime in the next week or two.

Unfortunately, the feature the issue describes is not well documented. In fact, I had to refer back to my personal notes to clarify how it works. Also, it turns out that the names I selected for the relevant methods in the IConstraint interface were not good choices. So I’m going to offer some explanation here. And when I post an update to the code, I may be renaming the method names to something more descriptive of their meaning and function.

So a long explanation follows. Those who are interested can read it. For others, I will post a much shorter explanation when I submit the code fixes and close out this item.

Please feel free to comment since, as always, I think it is important that users help shape the direction of the project.

The Long Explanation:
For the constraint classes, I considered the idea of enabling a constraint instance to serve as the boundary between two regions. For example, think of an application where constraints were based on national borders. France borders Spain and, just for added complexity, Andorra borders both. The problem with that feature was that it meant that a constraint edge would have to carry extra attributes for each bounding entity. Extra attributes would require more memory use. Most likely, that would mean an additional 2 elements, or 2x4=8 bytes, per edge. For each vertex in a Delaunay triangulation of sufficient size, there are approximately 3 edges per vertex. Thus the memory use of Tinfour would increase by 24 bytes per vertex. For the standard implementation this would be an increase of 10 percent (up from 240 bytes per vertex). For the SemiVirtual implementation (120 bytes per vertex), the relationship would be more complicated, but it would amount to a maximum of about 20 percent.

There are things I can do to reduce the extra memory, though it would add complexity to the implementation. If there is a requirement to do so, I can implement derived edge classes to be used only in those cases where edges were derived from constraints. I would also have to add special handling in the edge-pool classes to store the special edges separately from regular edges. And I'd have to make sure that the extra conditional logic required to support this function does not bog down processing. All of this is feasible, but I want to have a user with an identified need before I do so. I also think that there is a fair chance that anyone who wants to use this kind of feature may be better served by more direct computational geometry routines (or mainstream GIS applications)… But I would be glad to be persuaded otherwise.

Anyway, back when I was writing the original code, there was a feature that I was able to add which would operate within the existing memory footprint. Although a constraint edge could not define the boundary between two regions, it could be used to indicate the boundaries of the general domain of a data set (the term "domain" being used as it is in mathematics). For example, in my CDT Logo demo, the constraints partition the plane into two separate domains: The “inside domain” and the “outside domain”. You could also read these as the “domain” of the data set and the “non-domain” of the data set.

This partitioning scheme also allows Tinfour to perform an action that resembles the idea of a “flood fill” routine used in old-school computer graphics. The CDT Logo demo uses that to mark all the edges inside and outside the letter domains as belonging to distinct sets. Then when rendering the feature, it can suppress the lines that are outside the data domain.

So that's how the existing feature works. It also explains some of the special behaviors embedded into the implementation. But, I did make a mistake in naming the methods in the IConstraint interface as “definesDataArea” and “setDataArea”. The term “area” is vague and simply doesn’t mean the same thing as “domain”. So in the update, I will probably be renaming these methods to “definesDataDomain” and “setDataDomain” or perhaps something similar.

from tinfour.

Thank you for "partial fix to missing constraints"

from tinfour.

from tinfour.

from tinfour.

Changes are mostly complete and I am current performing final testing. I expect to upload code this weekend. The changes improve internal behaviors and add some much needed usage explanation into the javadoc.

The changes will involve renaming the "constraint area" method calls to the "constrained region" variation I described in my earlier post. In practice, I think that relatively few applications will be affected by this change (certainly that's what I hope). Most of the renamed methods are used by Tinfour internals but are unlikely to be used by external application code.

The three renamed methods that are most like to be used by application code will be:

• IConstraint.setDefinesDataArea() becomes setDefinesConstrainedRegion()

• IQuadEdge.isConstrainedAreaEdge() becomes isConstrainedRegionEdge()

• IQuadEdge.isConstrainedAreaMember() becomes isConstrainedRegionMember()

from tinfour.

Thank you. I'm looking forward to use it.

from tinfour.

I am still performing testing, but the initial results have been sufficiently successful that I am now submitting changes to address this issue,

The API for the IConstraint interface changed to reflect a better use of math terminology and a more correct use of concepts from plane geometry. Some methods were removed and others renamed. Existing applications that used constraint features will be affected by the following changes:

• The setDefinesDataArea() method no longer exists. The setDefinesConstrainedRegion method was also abandoned. Instead, all Polygon Contraints define constrained regions all the time
• IQuadEdge.isConstrainedAreaEdge() becomes isConstrainedRegionEdge()
• IQuadEdge.isConstrainedAreaMember() becomes isConstrainedRegionMember()

I am still working on performance improvements for the semi-virtual incremental tin class when adding polygon constraints.

from tinfour.

The problems with incorrectly assigning constraint status to interior edges is now resolved. Therefore I am closing this issue.

Thank you for identifying this problem. Resolving it led to a significant improvement in the constraint management logic and related API design.

As a parting note, I am including a picture that was created using a TIN built from polygon constraints. The constraints were taken from the public-domain Natural Earth Data. This test provided an excellent test case for the new constraint logic.

Although the rendering logic used to create the image is not part of the Tinfour project, the ability to read Shapefiles is supported.

from tinfour.