5 ms·

As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. Can you implement thi

• defen 16y ago
  Has that algorithm ever been implemented?
• palish 16y ago
  Skimming over the paper, the goal appears to be "convert an arbitrary closed concave polygon into a set of triangles in linear time". Disregarding the "linear time" part, there is a standard way to accomplish this goal: - the polygon can be thought of as the "outline". - transform the outline into a set of XYZ positions (verts). This is accomplished simply by starting at any point on the outline, then stepping along the outline by a fixed interval until you wind up back at your start pos. - then: triangles = [] while len( verts ) >= 3: for i from 0 to len( verts ) - 2: A = verts[i] B = verts[i+1] C = verts[i+2] # verify the triangle has not been flipped inside-out, and is not degenerate. det = Determinant2x2( A - B, C - B ) # if the triangle is degenerate, then remove the middle vertex. if det == 0: verts.remove( B ) break; # if the triangle is inside-out, skip it. if det < 0: continue; # if the triangle does not intersect the polygon and is not inside-out, then it is a valid triangle, so add it to the result. if not TriangleIntersectsPolygon( poly, A, B, C ): triangles.append( [A, B, C] ) verts.remove( B ) break; This is known as 'ear clipping'. Now, it is not linear time, but there is no reason to optimize this algorithm unless it turns out to be necessary, which I've never yet seen to be the case in an actual real-world scenario. That's the thing about scientific papers --- they are very useful, but only if your problem domain precisely matches theirs. For example if you don't care about "linear time", then all of that paper's complexity simply fades away.
  • codexon 16y ago
    Um, what? This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary. Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.
    • palish 16y ago
      Yes, yes. But the original challenge is invalid. I asserted that I could implement 99% of algorithms I came across for practical real-world problems, not 99% of all algorithms. I gave a solution that solves the problem. The problem is, convert an arbitrary concave closed polygon into a set of triangles. I maintain that it is completely valid for me to present that solution --- there are plenty of tricks you can do to optimize it in C/C++. And not just runtime optimization either... For example why not triangulate the polygon, then save the results to disk? That way O(N log N) vs O(N) becomes completely irrelevant... you only have to do it once, ever. I suppose what I am saying is this: I can solve 99% of real-world problems I am likely to encounter in my career as a software engineer. The challenge "implement THIS scientific paper!" is completely invalid because it's a solution to a problem which very likely will never exist. My solution is valid as long as it does not greatly impact the performance of the app. Which is "always", once you throw in a layer of caching. P.S. The paper has the restriction "for every polygon vertex XY, no two vertices may have the same Y coordinate", which means it's likely to not be applicable to any real-world problem.
      • codexon 16y ago
        Why is it invalid? Your original comment made no mention of "practical real-world problems". Who gets to decide that? Is implementing a video codec not a "real-world" problem since only a handful of people have experience with this? What about symbolic algebra software? A handful of find those useful compared to the masses that require mundane enterprise crud. Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort. My point is that in any field, "99% of real-world problems" are easy enough for the average college graduate to comprehend. Think about the kind of math that is useful for "real-world" problems. When you start bragging that you can learn any CS topic/algorithm in less than a day, you just didn't look hard enough. P.S. You missed the sentence right after where it says "we can easily get around this assumption by applying the symbolic perturbation techniques of [10] and [31]"