Comments (17)
The thing is that two holes that share a point actually form a weak polygon. I
can understand the problem, clipper does make all polygons strictly simple but
when you add two of these as holes you are actually creating a weak polygon out
of two simple one's.
Anyways poly2tri should be able to support these cases if when you create the
points you make sure that shared points are one unique object.
Does hole 1 and hole 2 share the same point object for the shared point?
One dirty solution would be to shrink the holes a tiny amount that isn't
visible to the naked eye. A simple way would be to loop thru the vertexes of
each hole and move it them tiny bit:
For a 3 vertex hole the unrolled loop would look like:
p0 = p0 + 2e-12*normalize(p1 - p0);
p1 = p1 + 2e-12*normalize(p2 - p1);
p2 = p2 + 2e-12*normalize(p0 - p2);
By moving the p0 closer to p1 along the edge they form you do a form of shrink
that ensures that no new intersection between the holes will form when you
"wiggle" each hole vertex.
The factor has to be atleast twice the size of the epsilon used given that all
points is in the range [-1,1].
Original comment by [email protected]
on 20 Dec 2013 at 11:14
from poly2tri.
Hi,
I'm not sure I fully understand the problem... but you are saying that if I can
guarantee weakly-simple polygons (one unique object) for holes that share a
vertex, then poly2tri should handle them?
I'd like to avoid shrinking as it'll add more computation requirements to an
already expensive process (which is why we chose poly2tri to begin with - it is
fast!). Also, with our use case, there's no guarantee that shrinking won't
create the exact same situation since we have to feed very dirty data into
clipper.
I'll have to study clipper a bit more to see what it can do in this respect.
Original comment by buckyballreaction
on 20 Dec 2013 at 4:22
from poly2tri.
Check if the holes polygons created by clipper use same object instance for
shared points or if clipper creates a new point for every hole.
The problem if you have two different point instances with same coordinate is
that the graph of connected points poly2tri uses during triangulation will not
be correct and the triangulation can fail due to this.
Think of the triangulation as this.
You have a list of unique points to triangulate.
You can add some constraints that some triangle edges must exist between some
points.
This is all poly2tri cares about.
When you add holes what you actually do is add more points to the list of
unique points. Then enforce some edges between points in this list.
What makes poly2tri a polygon triangulator is the knowledge that we have a
closed loop of constraints forming an outer hull. With this knowledge we can
pick a triangle inside and loop thru all triangles and just save those inside
this hull.
Original comment by [email protected]
on 20 Dec 2013 at 5:44
from poly2tri.
The easiest way would be if you could make clipper return a list of all points
and the polygons would just be list of indexes to this list of points.
Original comment by [email protected]
on 20 Dec 2013 at 5:46
from poly2tri.
Ah OK, that makes sense (I also read up a bit more on the sweep-line
algorithm). Although I'm still a little curious as to why both of my examples
above don't fail - could it be because of the resolution or accuracy of the
sweep-line?
Clipper does not use the same object instance for each Point, there is almost
no pointer usage, everything is on the stack.
Also, here is the documentation it gives on its output with respect to
weakly/strictly simple polygons:
http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes
/Clipper/Properties/StrictlySimple.htm
It looks like output polygons are guaranteed to be simple in some form, or
guaranteed to be strictly simple if you set the flag. No guarantee or option
of weakly-only, however. In my code we use the StrictlySimple(true) flag
because it reduced the crashing cases significantly; just the one in my opening
post remains so far.
Also, when I manually adjust the two holes, in the crashing case, into one hole
to form a weakly simple polygon by clipper's definition, it still crashes:
hole:
393000, 205000
419000, 177000
420000, 139000
539000, 138000
419000, 177000
449000, 291000
Original comment by buckyballreaction
on 20 Dec 2013 at 6:19
from poly2tri.
Adding the same point twice as different instances will make poly2tri behave in
an undefined manner. Sometime it will work and sometimes not, it all depends on
how the two identical points end up in the advancing front and how the
constraints are directed. The connected graph will be flawed but under some
circumstances the triangulation will work anyways.
This is why poly2tri only supports simple polygons.
Given you can enforce that holes just share unique common points, poly2tri can
triangulate these polygons.
Original comment by [email protected]
on 20 Dec 2013 at 6:45
from poly2tri.
Perhaps I'm not thinking out-of-the-norm enough to understand (please forgive
me).
Are you saying that the hole that crashes above can still be triangulated if
fed properly into poly2tri? If so, what would the geometry look like? Can
just simple list of (in this case, 5) points suffice for input?
Original comment by buckyballreaction
on 20 Dec 2013 at 10:48
from poly2tri.
You would have to build you hole like this to support shared points
pseudo code:
list = { new Point( 393000, 205000 ),
new Point( 419000, 177000 ),
new Point( 420000, 139000 ),
new Point( 539000, 138000 ),
new Point( 449000, 291000 ) };
hole1 = { list[4], list[0], list[1] };
hole2 = { list[3], list[1], list[2] };
Most likely you will have to spend more time remapping points than it would
take to just shrink the holes like I wrote above. Which is a pretty straight
forward and fast fix. You could probably skip normalization of the vector if
you know your line segments isn't to short or long.
Since I really don't know what you are doing before and after triangulation I
can't give any better suggestions than this.
Original comment by [email protected]
on 20 Dec 2013 at 11:47
from poly2tri.
What you would have after the shrink operation is this overly exaggerated.
Original comment by [email protected]
on 21 Dec 2013 at 12:15
Attachments:
from poly2tri.
Very interesting... now I understand what you meant by "shared points are one
unique object".
I will implement the shrinking and see how everything goes. I will also
continue the discussion about unique Point objects as an output of clipper.
Thanks again!
Original comment by buckyballreaction
on 21 Dec 2013 at 7:13
from poly2tri.
Using the clipper OffsetPolygon class to shrink the polygons slightly added
about 50% processing time overhead, but did resolve the issues. This was a
little too much overhead for my tastes.
I did, however, adapt your 'wiggle-shrink' algorithm to our situation. Since
we upscale our points into clipper by 1000, all I needed to do was shrink the
output back along the line by 1. I can do it in-place with the clipper output
like so:
// Shrink large polygons by reducing each coordinate by 1 in the
// general direction of the last point as we wind around
static void edgeShrink(Path &path) {
unsigned int prev = path.size() - 1;
for(unsigned int i = 0; i < path.size(); i++) {
// Adjust coordinate by 1 depending on the direction
path[i].X - path[prev].X > 0 ? path[i].X-- : path[i].X++;
path[i].Y - path[prev].Y > 0 ? path[i].Y-- : path[i].Y++;
prev = i;
}
}
This simple method didn't add measurable difference to the computation time and
the crashing case is also solved.
Good idea!
Original comment by buckyballreaction
on 21 Dec 2013 at 10:42
from poly2tri.
Great! :)
Original comment by [email protected]
on 21 Dec 2013 at 11:37
- Changed state: WontFix
from poly2tri.
buckyballreaction, why didn't you choose to remap points instead?
Using std::map and std::pair that should have been quite fast, and it looks
like it's more robust than messing with coordinates. What do you think?
Original comment by [email protected]
on 30 Apr 2014 at 4:02
from poly2tri.
I'm not sure I understand what you mean by 're-map' points.
The original issue was due to a conflict between having duplicate points in the
input but poly2tri requiring only one instance of each point.
My solution was a quick way to guarantee no duplicate points with the output
from Clipper.
Original comment by buckyballreaction
on 30 Apr 2014 at 4:28
from poly2tri.
I mean that the solution proposed by thahlen in comment #8 sounds not too
inefficient. I would build such a map:
std::map<std::pair<long,long>, Point*> unique_points;
and then loop through Clipper's output to populate it or reuse existing Point
pointers if the coordinate pair was already seen.
Since I would like to go this way, I was wondering why you thought that
manipulating coordinates to perform shrinking was more robust. I would be
afraid of the existence of another point at the new, shifted, coordinates...
From what I understood from thahlen's words, poly2tri is not afraid of polygons
or holes sharing a point, it's just afraid of duplicate allocated point
structures with same coordinates - which is very good news and a lot less
strict than I thought since an easy workaround can be applied!
Original comment by [email protected]
on 30 Apr 2014 at 6:34
from poly2tri.
Ah OK. I understand now. That may definitely be a more exact solution.
In my case, however, speed is paramount. I'm doing large-scale triangulation
during the level loading for my game. Before my above code I had already
up-scaled floating point values by 1000 and converted them to integers (for
input to Clipper). My solution is not quite exact, but close enough at our
level. It also has only 2 branches and arithmetic operations without new
object allocation (I think).
I do not know how much slower your implementation would be, but I'd expect it
to be so. I'd be interested in timings between the two if you happen to run
them.
Original comment by buckyballreaction
on 30 Apr 2014 at 7:05
from poly2tri.
Okay, thanks for feedback. I understand your performance needs. In my case I
prefer robustness over speed. Not sure I'll do comparisons, but will definitely
share my code if I'm going this way.
Original comment by [email protected]
on 30 Apr 2014 at 8:15
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
- 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.