Get super triangle/bounding triangle of points

Member
Posts: 24
Joined: 2008.01
Post: #1
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?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
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?
Quote this message in a reply
Member
Posts: 24
Joined: 2008.01
Post: #3
I need to calculate the super triangle to kick off my delaunay triangulation algo.
Quote this message in a reply
Member
Posts: 338
Joined: 2004.07
Post: #4
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.

Justin Ficarrotta
http://www.justinfic.com
"It is better to be The Man than to work for The Man." - Alexander Seropian
Quote this message in a reply
Moderator
Posts: 776
Joined: 2003.04
Post: #5
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 Smile

I found this one, for instance, but the full text is behind a pay wall:
http://www.springerlink.com/content/uggr3e5uj5l11ntp/
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #6
Most Delaunay triangulation algorithms don't begin with a bounding triangle... what's your extra requirement?
Quote this message in a reply
Member
Posts: 24
Joined: 2008.01
Post: #7
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
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #8
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.
Quote this message in a reply
Member
Posts: 24
Joined: 2008.01
Post: #9
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/
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #10
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...
Quote this message in a reply
Member
Posts: 24
Joined: 2008.01
Post: #11
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?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #12
yeah (extra characters to pacify Carlos)
Quote this message in a reply
Member
Posts: 24
Joined: 2008.01
Post: #13
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.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Ray-Triangle Intersection mikey 2 5,797 Aug 15, 2010 05:11 AM
Last Post: mikey
  Triangle Intersection Tests merrill541 1 3,846 Feb 6, 2009 12:13 PM
Last Post: scgames
  Triangle Normal Calculations merrill541 2 4,219 Feb 1, 2009 07:06 PM
Last Post: merrill541
  Angle between two points? Graphic Ace 6 7,549 Nov 8, 2008 12:11 PM
Last Post: macnib
  Super Mario Galaxy Physics SethWillits 0 3,319 Mar 27, 2008 11:38 AM
Last Post: SethWillits