How to triangulate between two closed curves?

Need help, or want to share a macro? Post here!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Post Reply
stefankorisnik3
Posts: 101
Joined: Sun Jul 24, 2022 12:49 pm

How to triangulate between two closed curves?

Post by stefankorisnik3 »

Maybe this is an off topic for this thread.
How can i triangulate between two closed wires in 2D/3D?
For the start case how can i triangulate between two convex closed wires in 2D?

I have tried following:

If we have two convex closed wires in 2D
we can for each convex curve find the diagonal that connects two most far vertices. Then we can split that curve in the lower and upper part.
Now we can separate algorithm in two parts: upper and lower part.

Let's take the upper parts from the both curves.
We can make projection on the x-axis like following:

first curve: `{x_1, 0}, {x_2, 0}, ...., {x_n, 0}`

second curve: `{x_1', 2}, {x_2', 2}, ...., {x_m', 2}`

Notice the fixed y-axis. We place fixed y-axis for both projection and we will return the regular y-coordinate after applying triangulation.

Now we can apply some triangulation algorithm let's say delaunay. After that as said above we can return the regular y-coordinate from map that we generate before projection.

The main flaw in this algorithm i think is the boundaries vertices. On the next picture can be seen the problem. We can see that the boundaries vertex have a lot of connection: [the link to the image 1][1]

How can i solve this flaw and also is there the better way to triangulate between two curves for start case in the 2D convex closed curves?

The second thinking is to densify the numbers of points on both curves and to make the numbers same. Then to start from arbitary vertex from the first curve and connect to the closest vertex on the second curve (step 1.). Then to go vertex by vertex and make triangles like on the following image: [the link to the image 2][2]

Is this okay way?


[1]: https://i.stack.imgur.com/MKe3u.png
[2]: https://i.stack.imgur.com/pEB1B.png
jbi
Posts: 117
Joined: Sun Apr 24, 2016 3:28 pm

Re: How to triangulate between two closed curves?

Post by jbi »

why not discretize the wires with a equal number of points beforehand?

Code: Select all

wire.discretize(Number=nb)
find the closest distance from points in one curve to points in the other curve, start with that pair and work trough points from there.
stefankorisnik3
Posts: 101
Joined: Sun Jul 24, 2022 12:49 pm

Re: How to triangulate between two closed curves?

Post by stefankorisnik3 »

Thanks. I'll try right now.
Can you let me know how this

Code: Select all

discretize
works?
I didn't know that this method exists so i implement the function to add more points on the closed curve.
The algorithm follows. Let's say we need to add 10 points. We have 10 iteration and in every iteration we find the longest one edge in the wire and then half the edge.
jbi
Posts: 117
Joined: Sun Apr 24, 2016 3:28 pm

Re: How to triangulate between two closed curves?

Post by jbi »

no need to tell from my side. Just create a wire object in the console. when you type wire.discretize the help window should show.
wire.discretize(Number=10) will give you 10 equidistant point (acc. documention)
I guess you could get much better targeted help here if you explain what you want to achieve in the end.
stefankorisnik3
Posts: 101
Joined: Sun Jul 24, 2022 12:49 pm

Re: How to triangulate between two closed curves?

Post by stefankorisnik3 »

Ok. Thanks for your input.

This is what i got.
If we choose for every vertex from one curve the closest vertex from the other curve we can get a lot of "spaces"
This is an example where we get a polygon with 5 edges: https://imgur.com/zniDrvM
stefankorisnik3
Posts: 101
Joined: Sun Jul 24, 2022 12:49 pm

Re: How to triangulate between two closed curves?

Post by stefankorisnik3 »

and following part
If we have polygon of five edges like on the picture in previous post
and we have v1 and v2 from one curve and t1,t2,t3 from the other curve
we can connect v1 - t2 and v2 - t2

more generally we can go up down up like
v1 - t2 - v2
and finish the triangulation if we have odd polygon
stefankorisnik3
Posts: 101
Joined: Sun Jul 24, 2022 12:49 pm

Re: How to triangulate between two closed curves?

Post by stefankorisnik3 »

Actually i think it is better to do the next thing.
We can align all points from the curves above and below in two lines like show in the picture:
https://imgur.com/B6csmqy

Now we can see that there is no intersection and that there is no conection on the same line (bipartite)
Post Reply