Author Topic: Delaunator, Delaunay triangulation, tin  (Read 513 times)

0 Members and 1 Guest are viewing this topic.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Delaunator, Delaunay triangulation, tin
« on: October 26, 2021, 09:38:51 PM »
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  :crazy2:

here's the source
« Last Edit: November 25, 2021, 07:44:06 PM by It's Alive! »
Retired

MickD

  • King Gator
  • Posts: 3513
  • (x-in)->[process]->(y-out)
Re: Delaunator, Delaunay triangulation, tin
« Reply #1 on: October 26, 2021, 11:43:44 PM »
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-
Forth is like the Tao: it is a Way, and is realized when followed.
Its fragility is its strength; its simplicity is its direction - Michael Ham

"First, solve the problem. Then, write the code." ó John Johnson

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #2 on: October 27, 2021, 02:57:37 AM »
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.

Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #3 on: October 29, 2021, 08:41:00 PM »
Found an optimization, last version, i promise  :laugh:


Quote
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
« Last Edit: November 19, 2021, 08:52:37 PM by It's Alive! »
Retired

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9765
Re: Delaunator, Delaunay triangulation, tin
« Reply #4 on: October 29, 2021, 10:13:28 PM »
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.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #5 on: October 30, 2021, 07:49:14 PM »
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
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #6 on: November 16, 2021, 03:44:33 AM »
Added a constrained TIN  :laugh:
the commands are createhull, createtin, createctin  :mrgreen:

« Last Edit: November 19, 2021, 08:52:51 PM by It's Alive! »
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #7 on: November 19, 2021, 08:50:06 PM »
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
« Last Edit: November 19, 2021, 08:53:32 PM by It's Alive! »
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #8 on: November 22, 2021, 03:03:13 AM »
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
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #9 on: November 24, 2021, 05:25:26 AM »
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  :crazy2:

 
Retired

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7158
  • AKA Daniel
Re: Delaunator, Delaunay triangulation, tin
« Reply #10 on: November 24, 2021, 10:37:21 PM »
Found an optimization, cut the runtime (sans drawing the entities) by almost 1/2
total time Num Points = 291876, time = 616ms
Retired