Comments (6)
Hello, yes, I'm aware of this limitation.
The triangulation should be created by first inserting vertices followed by edge (constraints) insertion. So when inserting vertices the triangulation is Delaunay.
So as you mentioned inserting vertices in constrained triangulation is not supported. But there is also another reason for that: when inserting vertices edges are flipped to ensure Delaunay property. And the algorithm does not currently handle constraints at this point.
from cdt.
Alright, wasn't sure that your implementation is for offline use only so decided to point out potential issue. I have halfe edge delaunay triangulation implementation that can perform operations in runtime and had to deal with that kind of issues.
from cdt.
Please disregard my previous message.
I double-checked and we use a remembering stochastic walk.
So it should work with arbitrary triangulations.
Here's the code
template <typename T>
TriInd Triangulation<T>::walkTriangles(
const VertInd startVertex,
const V2d<T>& pos) const
{
// begin walk in search of triangle at pos
TriInd currTri = vertices[startVertex].triangles[0];
#ifdef CDT_USE_BOOST
TriIndFlatUSet visited;
#else
TriIndUSet visited;
#endif
bool found = false;
while(!found)
{
const Triangle& t = triangles[currTri];
found = true;
// stochastic offset to randomize which edge we check first
const Index offset(detail::randGen() % 3);
for(Index i_(0); i_ < Index(3); ++i_)
{
const Index i((i_ + offset) % 3);
const V2d<T> vStart = vertices[t.vertices[i]].pos;
const V2d<T> vEnd = vertices[t.vertices[ccw(i)]].pos;
const PtLineLocation::Enum edgeCheck =
locatePointLine(pos, vStart, vEnd);
if(edgeCheck == PtLineLocation::Right &&
t.neighbors[i] != noNeighbor &&
visited.insert(t.neighbors[i]).second)
{
found = false;
currTri = t.neighbors[i];
break;
}
}
}
return currTri;
}
Flipping a fixed edge could still be a problem. How does your implementation handle this?
from cdt.
I track what edges are constrained. Constrained edges are not getting flipped. You can play with Spine. They use CDT to interactively create meshes.
from cdt.
Thanks. If it's just this single check then it should be really easy to add.
from cdt.
#44
Fix for not flipping fixed edges is merged to master
.
from cdt.
Related Issues (20)
- Some inputs that trigger failure HOT 3
- Warnings: `vertices` is shadowing a member declaration HOT 1
- Tiny compilation warning (VS2019) HOT 6
- initializeWithCustomGrid HOT 1
- Infinite Loop in Conform Mode HOT 4
- overlapping edges / flat triangles (solved) HOT 5
- Csharp support? HOT 1
- Are there better ways to find all triangles containing a certain edge? HOT 2
- Generate some degenerate triangles HOT 2
- How to update triangulations efficiently? HOT 10
- How to obtain the vertices inside the boundary composed with some edges? HOT 3
- A case that failed in triangulation HOT 20
- Question about m_vertTris HOT 1
- Wrong super-triangle calculated for tiny bounding box
- Failure in eraseOuterTriangles HOT 3
- Callbacks HOT 6
- Unexpected new vertices created; potential issues (or misuse of the API?) HOT 5
- Name clash HOT 4
- Are these intersecting edges being handled correctly? HOT 2
- Resume CDT::Triangulation HOT 4
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 cdt.