Topic: Delaunator, Delaunay triangulation, tin

[It's Alive!]

Worthy of its own thread as its very impressive performance

Source is https://github.com/delfrrr/delaunator-cpp
Note the original source is 2D, but the input point set is const, so the indexing seems to work on any array. See my notes in the code. It could have been faster, but the authors used their own point class, so there’s memory duplication.

GenTin Num Points = 1000004, time = 645.811500
total time Num Points = 1000004, time = 11666.346100

BricsCAD - GenTin Num Points = 1000004, time = 640.873300
BricsCAD - total time Num Points = 1000004, time = 47141.696700

Adding the faces could be optimized by using a transaction, instead of opening and closing the database a million times 

here's the source

[MickD]

Have you looked into ECS for this type of work? It's well suited to this sort of thing with big lists of data

https://www.gamedeveloper.com/design/the-entity-component-system---an-awesome-game-design-pattern-in-c-part-1-

[It's Alive!]

I’ve found the civil and point cloud space fascinating, at least in how they crunch big data.
I think some of these engines are using the graphics cards to do crunching. CAD or DWG is definitely not the best platform.

[It's Alive!]

Found an optimization, last version, i promise 

Ac =GenTin Num Points = 41769, time = 12.167100
Ac =total time Num Points = 41769, time = 297.333700

Ac =GenTin Num Points = 1000004, time = 459.705100
Ac =total time Num Points = 1000004, time = 16602.357400


Bc =GenTin Num Points = 41769, time = 12.675900
Bc =total time Num Points = 41769, time = 1187.718800

Bc =GenTin Num Points = 1000004, time = 476.299300
Bc =total time Num Points = 1000004, time = 29203.530100

[JohnK]

You have had me reading on this stuff for the last few days. Still have very little understanding (so many rabbit holes traveled) but it's fun to think about some of this stuff.

[It's Alive!]

I have very little understanding too lol. Just goofing around this week.
Since I’m retired, I was thinking about joining some open source project, just to keep my chops up, but most of this stuff is really hard

[It's Alive!]

Added a constrained TIN 
the commands are createhull, createtin, createctin 

[It's Alive!]

new version doubles performance with createctin
from, in milliseconds

total time Num Points = 36976, time = 512
to
total time Num Points = 36976, time = 204

edit, attached the latest to the first post

[It's Alive!]

I found a really fast way to get the concave hull using the existing TIN algorithm. Computing radius of triangle circumcircle and check with a user input
Caveats, it has islands, the boundary is individual line segments collected from the edge triangles.  The edges can be flipped, so it’s hard to create a polyline edge.
Createhull2

[It's Alive!]

Renamed command Createhull2 to Createctin2.

I found I was able to build a proper polyline,  by using the triangle to reset the edge direction.
For each edge triangle, orient the outside edge clockwise.  It’s really fast at around 1s for 300,000 points.
But this is for calculating the boundary and the TIN. I probably could have improved performance a bit,
but I ran out of sunflower seeds and black licorice 

 

[It's Alive!]

Found an optimization, cut the runtime (sans drawing the entities) by almost 1/2
total time Num Points = 291876, time = 616ms

[frtfff]

确实厉害。crazy job. Good job.

[frtfff]

Mr,D:
 glad to see you again,crazy job. By the way, I can't get the inner concave,Why I am failed? 
 Command :createhull2 enter enter enter.
I can get the outer concave ,but failed in inner concave.
with many thanks.

[It's Alive!]

Because I removed it. In https://www.theswamp.org/index.php?topic=57122.msg607183#msg607183

From line 511 to 551 constructs the outside polyline by detecting outside edges. It was too hard (slow) to construct multiple closed polylines (islands).
You can easily draw them (out of order) with line segments though.

I actually don’t know if real pointsets actually have islands.  I would think that a good pointset would look like the first picture.

[frtfff]

oo, you can leave a switch to select to control island. Maybe useful if that is a lake.