#### Archived

This topic is now archived and is closed to further replies.

# two dimensional polygon division

This topic is 5736 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 ]

##### Share on other sites
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...

##### Share on other sites
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

##### Share on other sites
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 ]

##### Share on other sites
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.

##### Share on other sites
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)

• 9
• 23
• 10
• 19