BSP Trees, Polygon Complexity (?)

netshade

Hey all -


I've been working on segmenting a polygon to some arbitrary complexity. When I first encountered this problem, I took in an array of Vector2[]'s, computed the centroid, and walked the outside, generating a list of polygons to draw triangle lines from the centroid to. ( I walked the outside with Bresenham's Line Algorithm )

However, this isn't really going to solve the problem for me - it generates a set of triangle faces that have no coordinate points between the centroid and the exterior of the polygon. I've been trying to solve the problem, and I came across documents discussing BSP trees and how they're generated.

While most of the articles I found discussed BSP trees for rendering sets of polygons that may or may not span the plane that intersects the subject of the algorithm, it seems like it would be reasonable ( maybe ) to use a BSP tree algorithm to split a polygon into a more complex mesh of constituent polygons that still combine to form the original general shape.


Any folks out there that can help me Am I on

waruwaru

Maybe I am misunderstanding the problem. Is it a simple polygon, and all the corners of the polygon, on a flat plane If so, can't you just use something like

http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/introduction.html

to break the polygon down to triangles

netshade

Yeah, I could, but it doesn't seem like that generates any interior vertices to the triangles. Cool link though - thank you.


And yes, it's a simple, 2d polygon.

waruwaru

Sorry, what are "interior vertices" Would any point in the triangle do

netshade

Sorry, I know I'm probably making people cringe with poor math terminology usage:

By interior vertices, I mean that the triangles that make up the polygon would have at least one point (of its three major coordinate points) that would not exist on the edge of the polygon. I would like to have some triangles generated in this method that have no points on the edge of the polygon as well, but I don't know how I would generate that...

I've also been getting some help over at the shack:

http://www.shacknews.com/ja.zz comments=45702&13833553

Just to add some context. ( I don't wanna retype everything :-) )

setrio

Maybe this helps:

http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html

look for Triangulation by ear clipping.

waruwaru

wikipedia actually has a page on this:

http://en.wikipedia.org/wiki/Polygon_triangulation

When you hit an interior vertex, just split the polygon and recursively process the "ears". :)