Get super triangle/bounding triangle of points
Hi guys  got a problem that I need some advice on.
I have a set of 2D points and need to calculate a triangle that encompasses every point in that set; kinda like a bounding box. Should be simple but I haven't been able to come up with something that works in all cases.
I tried calculating a simple extents box, and splitting it into two triangles, but for this algorithm I'm working on, I need just one 'super triangle'.
I know how to find if a triangle contains a point, and how to calculate the triangle's circumscribed area.
And ideas?
I have a set of 2D points and need to calculate a triangle that encompasses every point in that set; kinda like a bounding box. Should be simple but I haven't been able to come up with something that works in all cases.
I tried calculating a simple extents box, and splitting it into two triangles, but for this algorithm I'm working on, I need just one 'super triangle'.
I know how to find if a triangle contains a point, and how to calculate the triangle's circumscribed area.
And ideas?
Minimal bounding triangle sounds really hard, harder than minimal bounding circle ( which is already nontrivial  http://www.personal.kent.edu/~rmuhamma/C...tercli.htm ).
What are you trying to do?
What are you trying to do?
I need to calculate the super triangle to kick off my delaunay triangulation algo.
Does it need to be the smallest enclosing triangle? Because you could always take the bounding circle from OSC's link and superscribe an equilateral triangle around it. It will be huge but you're guaranteed to enclose all points.
From there, you could pare that down with some sort of sweeping algorithm. So you start at one vertex of the triangle A, and take the segment from A to another vertex B. Sweep the second vertex from B towards C until the segment hits one of the points. Cut out what you've swept through, and you're left with a smaller triangle that still encompasses all points. After that, start at B, and sweep from C to A. Keep going around the circle until you can't cut anything more out.
I'm sure that's not the best way to do it, since I just pulled that out of my butt in the last 15 minutes, but it's a good start and it gives you a fairly optimized* triangle that encompasses all points.
*EDIT: I mean optimized for area of the triangle, not complexity. I'm sure the time required is atrocious.
From there, you could pare that down with some sort of sweeping algorithm. So you start at one vertex of the triangle A, and take the segment from A to another vertex B. Sweep the second vertex from B towards C until the segment hits one of the points. Cut out what you've swept through, and you're left with a smaller triangle that still encompasses all points. After that, start at B, and sweep from C to A. Keep going around the circle until you can't cut anything more out.
I'm sure that's not the best way to do it, since I just pulled that out of my butt in the last 15 minutes, but it's a good start and it gives you a fairly optimized* triangle that encompasses all points.
*EDIT: I mean optimized for area of the triangle, not complexity. I'm sure the time required is atrocious.
Justin Ficarrotta
http://www.justinfic.com
"It is better to be The Man than to work for The Man."  Alexander Seropian
Well, you can always make a convex polygon using the border points (there are several alghoritms for that) and then... try googling the problem of finding a triangle that contains a convex polygon
I found this one, for instance, but the full text is behind a pay wall:
http://www.springerlink.com/content/uggr3e5uj5l11ntp/
I found this one, for instance, but the full text is behind a pay wall:
http://www.springerlink.com/content/uggr3e5uj5l11ntp/
Most Delaunay triangulation algorithms don't begin with a bounding triangle... what's your extra requirement?
OneSadCookie Wrote:Most Delaunay triangulation algorithms don't being with a bounding triangle... what's your extra requirement?
Really? Surely you need an initial triangle to start off the process? At least that's what I've read
Well, I haven't ever implemented it, but I've never seen anything to suggest that's the case... Wikipedia suggests one way is to add vertices one by one and retriangulate each time, which suggests you start with three vertices; and another way involves recursive subdivision and merging pairs of triangulations, which suggests your base case for the recursion is three vertices. I don't see why either requires a bounding triangle, nor do I see how a bounding triangle could ever be helpful regardless of the algorithm used.
OneSadCookie Wrote:Well, I haven't ever implemented it, but I've never seen anything to suggest that's the case... Wikipedia suggests one way is to add vertices one by one and retriangulate each time, which suggests you start with three vertices; and another way involves recursive subdivision and merging pairs of triangulations, which suggests your base case for the recursion is three vertices. I don't see why either requires a bounding triangle, nor do I see how a bounding triangle could ever be helpful regardless of the algorithm used.
I the algorithm works by determining if a point is inside the circumscribed area of a triangle or triangles. It then isolates those triangles, gets their commen edges, and then builds new triangles from those vertices and the point.
Hence, the point must be within a triangle's circle to be included in the process and thus the need for a 'super triangle' to kick things off. I don't see how else you could do it.
Link: http://www.codeguru.com/cpp/data/mfc_dat...php/c8901/
Well, from that link, it looks like the size of the supertriangle isn't at all relevant, it doesn't have to be in any sense minimal, so just find the AABR of the points and build a right triangle around it or something...
OneSadCookie Wrote:Well, from that link, it looks like the size of the supertriangle isn't at all relevant, it doesn't have to be in any sense minimal, so just find the AABR of the points and build a right triangle around it or something...
AABR = Axis Aligned Bounding Rect?
yeah (extra characters to pacify Carlos)
OneSadCookie Wrote:yeah (extra characters to pacify Carlos)
Ok so what you're suggesting is I create this box and use the gradient to generate an inclosing triangle?
I think I'll just try my previous idea first  split the box into two triangles and take it from there.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
RayTriangle Intersection  mikey  2  6,197 
Aug 15, 2010 05:11 AM Last Post: mikey 

Triangle Intersection Tests  merrill541  1  4,104 
Feb 6, 2009 12:13 PM Last Post: scgames 

Triangle Normal Calculations  merrill541  2  4,522 
Feb 1, 2009 07:06 PM Last Post: merrill541 

Angle between two points?  Graphic Ace  6  8,253 
Nov 8, 2008 12:11 PM Last Post: macnib 

Super Mario Galaxy Physics  SethWillits  0  3,539 
Mar 27, 2008 11:38 AM Last Post: SethWillits 