Remove edges from concave triangulation

12 views (last 30 days)
Ouatehaouks
Ouatehaouks on 10 Dec 2021
Edited: Ouatehaouks on 15 Dec 2021
Hello,
Let say I have a curve that is both concave and convex on which I run a delaunayTriangulation with a constraint matrix that is the domain. How do I get rid of edges that go outside of the domain in the concave region ? It looks like the isInterior works on points and not on edges so it does not detect these edges outside the domain. I could code myself the edges location and check whether in domain, but somehow I think there is a cleaner way. Moreover, when the edges to remove are detected, is it possible to create another delaunayTriangulation without those edges ?
A quick and dirty Matlab code example to show the issue:
% circle
x=cos(theta*pi/180);
y=sin(theta*pi/180);
% create a concave region
I1=theta>270 & theta<360;
I2=theta>90 & theta<180;
xx=x(I2)+1;
yy=y(I2)-1;
x(I1)=xx(end:-1:1);
y(I1)=yy(end:-1:1);
% constraint
Constraint=[1:length(x)-1 ; 2:length(x)]';
% run triangulation
DT=delaunayTriangulation(x',y',Constraint);
% plot
triplot(DT)
% isInterior only gives 1 as all points belong to the domain...
find(isInterior(DT)==0)
ans =
Empty matrix: 0-by-1
  1 Comment
Ouatehaouks
Ouatehaouks on 15 Dec 2021
Please help ! :) I have an ugly way to detect the segments in the concave region which is basically to see if the middle of the segment is inside my boundary but this method is prone failing with coarse resolution...

Sign in to comment.

Answers (1)

Bjorn Gustavsson
Bjorn Gustavsson on 15 Dec 2021
You problem is dificult in principle. How are the unwanted triangles supposed to be determined? In a general enough case that you can use it, and not only in this specific case.
Perhaps you can somehow identify convex region(s) in your perimeter and find triangles with only points from the same convex set of points? That would be my (current) first approach to this problem. How does that generalize to more complex perimeters or general sets of points I cannot tell, but that might get you somewhere.
  1 Comment
Ouatehaouks
Ouatehaouks on 15 Dec 2021
Edited: Ouatehaouks on 15 Dec 2021
Thank you for your answer. I think a proper definition would be to remove all edges 1. lying outside of the boundary and 2. which do not connect neighbouring points. The point 2 is important because the edge connecting two consecutive points on the boundary that I want to keep might end up being outside the continuous (or more refined) boundary. This is what I currently do (well thanks to your question I added point 2:) but it involves a for loop across the entire list of edges to see if points 1 and 2 are valid, and I thought there would be a more matlab-style and efficient way but I can't find it...

Sign in to comment.

Categories

Find more on Triangulation Representation in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!