Comments (12)
This is not a defect!! Just a request for implementation
Original comment by [email protected]
on 22 Nov 2010 at 10:45
from poly2tri.
Actually I have implemented support for most of these cases in the Java code.
If you are using floating point data these cases should be really rare.
So what are you doing? This should never be an issue when triangulating
polygons since the edges of the polygon is the constraints. If you have this
problem with polygons then the polygon would not be simple but self
intersecting.
If you got an example I could test, please just dump some point and constraints
in the form:
x,y,z
x,y,z
.
.
Original comment by [email protected]
on 22 Nov 2010 at 11:26
from poly2tri.
Hi,
Ok I am using the C# port, where there are commented TODO's where these
exceptions are thrown.
I did notice that I had some points very close by, and when I filtered these
the issue went away.
Is it just close almost coincidential points that can cause this? If so I
can pre-filter to make sure.
Original comment by [email protected]
on 22 Nov 2010 at 12:22
from poly2tri.
If you have a set of points then you just pick two points at random to create a
constrained edge. There is always a tiny chance that this edge might pass thru
another point in this set.
The chance that this edge will pass thru another point is pretty low when
dealing with float coordinates but if you point data is somewhat structured. eg
several points have the exact same x or y coordinates the likely hood that this
might happen gets bigger. In the java version I have implemented a way to split
the constraint edge in to several edges when these intersections happen.
If you have two points really close (almost coincidental) I guess that a
constraint edge from one of these point might consider the other point as
intersecting the constrained edge. So filtering almost coincidental points will
probably solve most of you problems. But as described above there are other
ways the edges can intersect points.
Original comment by [email protected]
on 22 Nov 2010 at 1:58
from poly2tri.
Here is a set of points that does cause a failure.
It is a large polygon (the boundary of South Africa) that is being rendered as
a filled polygon in my application.
Please let me know the results
Original comment by [email protected]
on 24 Nov 2010 at 12:58
Attachments:
from poly2tri.
Any results from the test set above?
Original comment by [email protected]
on 30 Nov 2010 at 2:39
from poly2tri.
Sorry have been busy with another project :).
I ran the dataset on the current Java release and the Triangulation in itself
works fine. This is 10 times more polygon edges than I have every tried to
triangulate before so the recursive meshClean will result in a stack overflow
:X.
This is the triagulation output without removing "external" triangles:
http://img530.imageshack.us/img530/2923/capture1291208037953.png
I use the DataLoader in the java example base to load the polygon this will
also translate and rescale the polygon points around 0,0. Also had to change
the loader to support Double instead of Float due to the precision in your
dataset.
Original comment by [email protected]
on 1 Dec 2010 at 1:09
from poly2tri.
I totally understand!!!
Thanks.
Yes I did a quick non recursive version of the meshclean to avoid the stack
overflow!
The output looks perfect. So I think the Java version is totally fine, but we
need to get the C# version to be in step with it. I have actually 'Genericized'
the C# version so I can get back my original points when triangulating surfaces
in 3D. I have a great interest in getting the C# version working as the Java
one does.
Will there be an update to the C# version? I am willingto help in any way I can
if that helps!, since I really like this library. It has good performance in
the managed environmnent.
Original comment by [email protected]
on 1 Dec 2010 at 1:34
from poly2tri.
Ah.
Would you like to share the your meshClean, could use one non recursive version
:).
First just try to normalize the coordinates to be within the range +-10 could
improve the precision during computations a little bit. But your coordinates
seems to use the whole range pretty good already.
There is also a EPSILON=1e-12 in the triangulation util. You could try to set
it to EPSILON=1e-13 or even smaller.
Since this started as more of a hobby project there is no floating point
precision analysis done on the algorithm so I just picked a reasonably EPSILON
that would give a wide margin of robustness. Since your coordinates are of such
high precision lowering the epsilon might help.
Original comment by [email protected]
on 1 Dec 2010 at 2:02
from poly2tri.
Here is a nonrecursive version of MeshClean:
public void MeshClean( DelaunayTriangle<Tag> triangle ) {
MeshCleanReqNoStack(triangle);
}
/// <summary>
/// Clean mesh without chewing the stack.
/// Derek Diamond 25 Nov 2010
/// </summary>
/// <param name="triangle"></param>
private void MeshCleanReqNoStack( DelaunayTriangle<Tag> triangle ) {
var stack = new System.Collections.Generic.Stack<DelaunayTriangle<Tag>>();
stack.Push(triangle);
while (stack.Count > 0)
{
var t = stack.Pop();
if (t != null && !t.IsInterior)
{
t.IsInterior = true;
Triangulatable.AddTriangle(t);
for (int i = 0; i < 3; i++)
{
if (!t.EdgeIsConstrained[i])
{
stack.Push(t.Neighbors[i]);
}
}
}
}
}
Original comment by [email protected]
on 1 Dec 2010 at 2:29
from poly2tri.
Thnx :).
Wierd that it didn't occur to me to replace the recursive function and the call
stack with an ordinary stack, so simple!
Original comment by [email protected]
on 1 Dec 2010 at 6:05
from poly2tri.
If there is any direct issues with the C# version you might try
https://github.com/MaulingMonkey/poly2tri-cs/issues
I'm closing this now since there is nothing to fix in the java codebase which
is the base of all other versions.
Original comment by [email protected]
on 15 Dec 2010 at 9:01
- Changed state: Done
from poly2tri.
Related Issues (20)
- Java source unbuildable in 1.7+
- Build failed when compliling with -we4715
- Java findbugs - nullcheck of value previously dereferenced HOT 1
- [java] Tessellation with hole error HOT 4
- Polygon with hole HOT 10
- [java] Missing triangle in non-constrained delaunay HOT 3
- Problem building library
- the EPSILON value is not exported in the python/cython version HOT 1
- Compilation fails with MSVC
- CMake build script
- Inconsistent behavior with holes that share a point HOT 17
- add typedef for "double"
- add typedef for std::vector<Point*>, std::vector<Triangle*> and other containers
- Triangulate crashes in sweep.cc:703 HOT 3
- java version compile error HOT 3
- Polygon.getHoles() missing HOT 5
- poly2tri crashes on a very simple geometry HOT 1
- crash with attached polygon HOT 2
- Crash when triangulating a polygon HOT 1
- crash with square polygon HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from poly2tri.