I don't know what you tested to get that the sum of angles would be wrong. Can you post a tiny program showing the problem? I am afraid you are plugging in the coordinates of the vertices instead of vectors. If you were using different types for vectors and points, the compiler could have told you there was a problem.
Also, what is v2 in the last piece of code you posted? You don't seem to use it... And why are you passing non-const references to a function that doesn't modify its arguments?
Skinny Triangles
Interesting topic, tackled some of this stuff myself not so long ago.
I found that the slowest part of ear clipping is the point-inside-triangle test, obviously a well known problem. I wrote an optimisation that put all of the points into a quad tree, this meant the triangulation was massively faster for complex shapes. Still not fast enough for real-time font tessellation though.
I found that the slowest part of ear clipping is the point-inside-triangle test, obviously a well known problem. I wrote an optimisation that put all of the points into a quad tree, this meant the triangulation was massively faster for complex shapes. Still not fast enough for real-time font tessellation though.
Here's some code showing how the sum of the angles in a triangle is 180 degrees:
#include <iostream>#include <cmath>struct Vector { double x, y; Vector(double x, double y) : x(x), y(y) { } double length_squared() const;};double dot(Vector const &v1, Vector const &v2) { return v1.x*v2.x + v1.y*v2.y;}double Vector::length_squared() const { return dot(*this, *this);}struct Point { double x, y; Point(double x, double y) : x(x), y(y) { }};Vector operator-(Point const &v1, Point const &v2) { return Vector(v1.x-v2.x, v1.y-v2.y);}double angle(Vector const &v1, Vector const &v2) { return std::acos(dot(v1,v2) / sqrt(v1.length_squared()*v2.length_squared()));}double sum_of_triangle_angles(Point const &A, Point const &B, Point const &C) { return angle(B-A, C-A) + angle(C-B, A-B) + angle(A-C, B-C);}double radians_to_degrees(double x) { static const double C = 45.0/std::atan(1.0); return C*x;}int main() { Point A(1,2), B(2,4), C(0,10); std::cout << radians_to_degrees(sum_of_triangle_angles(A,B,C)) << '\n';}
Author
Sorry for the strange things present in my functions it's just I've been reusing that function for all sorts of things. To perform changes on those three vertices for one purpose or another(Accomplishing little though ):). I won't do something like that again.
On the side though I found my mistake. I was getting the length of the vectors from the world origin not the edges. Idiot ignorant me. Now it works.
How do you think a delaunay triangulation algorithm could be made to work like an ear clipping one? What I mean is, how can a delaunay triangulation produce polygons only inside a contour of vertices? I am new to this sort of thing so I am still trying to figure out how to implement some of the things mentioned like ear flipping. I didnt develope the triangulation algorithm I am using, so that too I am still trying to figure out.
On the side though I found my mistake. I was getting the length of the vectors from the world origin not the edges. Idiot ignorant me. Now it works.
bool PlayState::FixAngles(b2Vec2 v0, b2Vec2 v1, b2Vec2 v2){ b2Vec2 n1 = v1 - v0; b2Vec2 n2 = v2 - v0; n1.Normalize(); n2.Normalize(); float dotProduct = b2Dot(n1,n2); float lengtha = n1.Length(); float lengthb = n2.Length(); float angle = RadtoDeg(acos(dotProduct/(lengtha*lengthb))); if(angle < 5 || angle > 150){ return false; } return true;}How do you think a delaunay triangulation algorithm could be made to work like an ear clipping one? What I mean is, how can a delaunay triangulation produce polygons only inside a contour of vertices? I am new to this sort of thing so I am still trying to figure out how to implement some of the things mentioned like ear flipping. I didnt develope the triangulation algorithm I am using, so that too I am still trying to figure out.
Quote:Original post by Antonym
On the side though I found my mistake. I was getting the length of the vectors from the world origin not the edges. Idiot ignorant me. Now it works.
Well, I told you what your problem was ("I am afraid you are plugging in the coordinates of the vertices instead of vectors"). As I said, if you were using different types for points and for vectors (like in the code I posted), the compiler would have told you that you were doing something wrong.
If I replace sum_of_triangle_angles by this code
double sum_of_triangle_angles(Point const &A, Point const &B, Point const &C) { return angle(A, B) + angle(B, C) + angle(C, A);}..., the compiler says this (emphasis mine):
kk.cpp: In function 'double sum_of_triangle_angles(const Point&, const Point&, const Point&)':kk.cpp:48: error: invalid initialization of reference of type 'const Vector&' from expression of type 'const Point'kk.cpp:33: error: in passing argument 1 of 'double angle(const Vector&, const Vector&)'kk.cpp:49: error: invalid initialization of reference of type 'const Vector&' from expression of type 'const Point'kk.cpp:33: error: in passing argument 1 of 'double angle(const Vector&, const Vector&)'kk.cpp:50: error: invalid initialization of reference of type 'const Vector&' from expression of type 'const Point'kk.cpp:33: error: in passing argument 1 of 'double angle(const Vector&, const Vector&)'Quote:How do you think a delaunay triangulation algorithm could be made to work like an ear clipping one? What I mean is, how can a delaunay triangulation produce polygons only inside a contour of vertices?
In constrained Delaunay, you can require that the edges of your polygon be part of the triangulation. The resulting triangulation will have triangles outside of the polygon, but you can filter those out as a post process.
[Edited by - alvaro on May 25, 2009 7:00:12 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
