mads

genius among idiots

  • she/her

Trans CS college student

Will talk about minecraft and celeste at any possible moment.



hthrflwrs
@hthrflwrs

learning about polygon triangulation. much to think about...


hthrflwrs
@hthrflwrs

methods of polygon triangulation:

  • turn it into trapezoids :) and then do math on them :)
  • [terrifying incomprehensible bullshit that somehow hits O(n)]
  • CUT OFF ITS FUCKING EARS DO IT YOU COWARD DO IT DO IT DO IT

Inumo
@Inumo

I looked up the terrifying incomprehensible bullshit that somehow hits O(n) and

what

(Note: this is the "simpler randomized algorithm"; its input is the output of an earlier optimized trapezoidation algorithm)


hthrflwrs
@hthrflwrs

well, it's simple, you see: it's a conformal of K, T(K) with an input of a set of chains K and the trapezoidation T(K) of its edges, which outputs a conformal decomposition T'(K) and its adjacency graph! And that gives you triangles :)


You must log in to comment.

in reply to @hthrflwrs's post:

i have no idea of the specifics of the method, tbh -- all that wikipedia says is "Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex. A simpler randomized algorithm with linear expected time is also known." i couldn't get access to the paper that describes the algorithm, unfortunately