im not sure if this is even the right forum to ask this, but im sure you math guys know the answer anyway i''m trying to figure out how to subdivide a polygon, or moreover- how to know WHEN to subdivide a polygon. here''s what i''ve come up with so far- say i have an stl vector of type "Vert" (im using a vector because i want to be able to increase and decrease verts dynamicaly)

struct Vert
{
   double x;
   double y;
}

int polygon_count = 1;
int vertice_count = 4;

vector  vertex(vertice_count);

/*** This draws a polygon like so ***/

v1                         v2
 +-------------------------+
 |                         |
 |                         |
 +-------------------------+
v4                         v3

 

lets say i kept adding vertices to the middle portion of my polygon until it were visibly ''divided'' how do i know when i''ve got a second polygon? is there a magical mathmatic equation i can use? -eldee ;another space monkey; [ Forced Evolution Studios ]

ok, best thing i can think of is that i''ve got to check if the
new vertice crosses any other line segment.. if it does that,
then i subdivide the line segment and ajust my numbers accordingly..
i guess i need to look into this a bit more...

You mean, if you draw a line in your polygon, how do you know if it has split the polygon in two? In that case, intersecting the line should work alright. You could also do a floodfill (if you''re working at the pixel level) and see if it covers the entire area, although that''s far from efficient.

Cédric

intersecting the line is what i was getting at, yah...
i''ve done a few ''on paper'' tests and that seems to
be the most accurate way to do it.. only snag i ran into
is when a segment intersected at a corner (i decided that
in said circumstance i''d just test both intersecting line segments).

now i just need a really fast algorithm for testing line intersections and returning intersection coordinates..
anybody know of one?

-eldee
;another space monkey;
[ Forced Evolution Studios ]

now i just need a really fast algorithm for testing line intersections and returning intersection coordinates..
anybody know of one?

Well, you could solve for y in both equations and set the equations equal to each other, then solve for X and those will be the x points where the lines intersect. Just substitute back in to the original for y.

er..

y = m1x + b1
y = m2x + b2

m1x - m2x = b2 - b1
x = (b2 - b1)/(m1 - m2)

where m is the slope, and b is the y-intersept (point slope formula)