News for hackers. Stuff that matters.
Re:Faster than earcut: triangulating 3.7M map polygons in 48... by airbreather on Thursday October 22, 2026 @08:00AM (#50194160)
Why the obsession with triangles?

If you just want areas, or to know if a point is inside or outside the shape there is a better way.

Given a simple closed curve, points (ax, ay) (bx, by) (cx, cy) (dx, dy) as a trivial example.

Line them up a,b,c,d,a vertically and take the "determinant" as we were taught.

Axby - aybx + bxcy - bycx etc etc.

Divide the result by -2 and you have the are, positive is clockwise, negative is anticlockwise.

Put an anticlockwise shape inside a clockwise shape and you have a donut.

There is more, have to go to dinner.

Re:Faster than earcut: triangulating 3.7M map polygons in 48... by jcattle on Thursday October 22, 2026 @08:02AM (#50194172)
Obsession with triangles so the GPU can show millions of polygons on a webmap.
Re:Faster than earcut: triangulating 3.7M map polygons in 48... by Sharlin on Thursday October 22, 2026 @08:13AM (#50194262)
There’s this thing called rendering, pretty important for maps.
Re:Faster than earcut: triangulating 3.7M map polygons in 48... by ethin on Thursday October 22, 2026 @09:27AM (#50195026)
Also important for physical modelling and geometric acoustics -- you need a geometric mesh (made of triangles) to work with. Which parts of could be sent to the GPU for processing as well.
Re:Faster than earcut: triangulating 3.7M map polygons in 48... by adrian_b on Thursday October 22, 2026 @08:33AM (#50194452)
The obsession with triangles comes from Microsoft, who around 1995 chose to support only triangles in DirectX.

As a consequence of that, the GPU vendors designed then GPUs supporting only triangles in hardware, abandoning earlier attempts to also support other figures.

That has been inherited until today, so any program that wants to use not only the general-purpose computing features of a GPU, but also the dedicated graphics hardware from it, must convert any other kinds of graphics primitives into triangles, before rendering on the GPU.

Re:Faster than earcut: triangulating 3.7M map polygons in 48... by entrope on Thursday October 22, 2026 @11:25PM (#50204154)
I don't think that is quite right. I had a book about computer graphics using OpenGL from before then, and I remember it saying (something like) that various polygons were supported at the API layer, but the GL implementation would decompose them into triangles at some point, and this could have surprising results for texture mapping, so it was typically a good idea to triangulate shapes explicitly.

One major technical reason that triangles are nice is that every triangle determines a plane, and rendering points onto a bitmap is easier if you know the surface is planar.

Re:Faster than earcut: triangulating 3.7M map polygons in 48... by jplusequalt on Thursday October 22, 2026 @11:44AM (#50196993)
Hardware/software rasterizers are already doing the "inside or outside" check millions/billions of times a second using the same determinant trick.
Re:Faster than earcut: triangulating 3.7M map polygons in 48... by anon291 on Thursday October 22, 2026 @08:06PM (#50202823)
Triangles are the simplest 2-d polytope?