
Polygon Division
My issue is this. I'm developing a C++ Engineering application in which I need a function that takes a simple polygon (a piece of cut wood) consisting of 4 to 6 bounding points and is split perfectly down the middle (horizontally) to create 2 new polygons. I need to graphically represent the bottom half differently than the top half, so I need both polygons.
Points of Polygon could be (0,0), (0,25), (100,100), (400,100), (500, 25), (500, 0).
I want a method that would split this right in half at the y=50 line, and give me 2 new polygons in return.
The polygon will always have top and bottom parallel lines which can be used to determine the intersection line...aka a horizontal piece of 2x4 wood.
Any help would be appreciated.
Thanks!
 mikau
 Super Member
Re: Polygon Division
Its difficult to understand exactly you mean by splitting it down the center. But if you know where you want it to be split, you could in theory draw mathematical lines to connect each corner of the polygon together. Then write the equation of the line that cuts it in half. Then use simple math to determine where the intersections of the lines are. There would be the cut points.
Of course thats a lot easier said then done. The math part is easy but the rest can be tricky. But if your a good programmer you can probably figure that out.
A logarithm is just a misspelled algorithm.
Re: Polygon Division
What if the piece is shaped like two mountains beside one another connected at the bottom, and then if you cut in up too high, you end up with THREE pieces?? When you said simple polygon, do you mean, this could not occur?
Oh, I think you said there are upper and lower parallel lines, can you explain this a little more. What would you do with a stair case with many parallel lines, how do you tell which is the top and bottom, check every one?
Last edited by John E. Franklin (20060221 08:02:36)
igloo myrtilles fourmis
 MathsIsFun
 Administrator
Re: Polygon Division
webwolve wrote:I want a method that would split this right in half at the y=50 line, and give me 2 new polygons in return.
It may not be exactly in half, of course, if you are choosing a fixed cut line, but that doesn't matter, right?
I think a possible solution would be to loop through each line and try to find an intersection point with y=50.
Example: (0,0), (0,25), (100,100), (400,100), (500, 25), (500, 0)
Line (0,0)=>(0,25) (flat, no intersection)
Line (0,25)=>(100,100) Slope= 0.75, y_intercept=25, so y = 0.75x+25 Solve: 50 = 0.75x + 25 → 25 = 0.75x → so x = 33.333 when y=50 Intersection point = (33.33,50)
Line (100,100)=>(400,100) etc ...
You should end up with two intersection points after looping through all of the polygons lines, and that is your "cut line"
If you also keep track of which lines get cut, you can then assemble two new "line lists" (bottom half and top half) and plot them as you wish.
(Note: Equation of a Straight Line)
Is that getting close?
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman
 mikau
 Super Member
Re: Polygon Division
thats essentially what I meant. :)
Last edited by mikau (20060221 09:07:52)
A logarithm is just a misspelled algorithm.
Re: Polygon Division
That sounds pretty nice and methodical, M.IsFun! One tiny thing though, (0,0) to (0,25) is vertical, not flat, but luckily, no intersection in the example.
igloo myrtilles fourmis
Re: Polygon Division
Once you find a segment that crosses over the y value of interest, you can do this: Call the bottom point A and the top point B. Call the dividing horizontal point C.
Cx = Ax + HeightToDivideLine*(Bx  Ax)/(ByAy)
Cy = Ay + HeightToDivideLine
igloo myrtilles fourmis
Re: Polygon Division
Thanks for your replies and your site.
Imagine if you will a piece of lumber, a 2x4, laying horizontally on your desk in front of you. It is 3 1/2 inches thick when lying on its edge. The ends of the 2x4 can be angled at any degree. There can also be a vertical segment before the angle begins as well.
So, in essence I am looking at this for example, a piece that always is horizontal on top and bottom with different end cuts:
(The dots are just placeholders to help represent the general shape I am trying to describe.)
... _________ .. /..................\ ../.................... ...................... .____________
This is my starting polygon. At exactly the midpoint, 1.75 inches for a 2x4 on edge, I want to intersect this polygon with a line at y = 1.75 inches, giving me 2 new distinct polygons which share the intersection line.
I don't share an interest for the area. I just need the coordinates of the new polygons so I can graphically represent them.
I think your ideas above will help me develop a routine to give me what I need.
Thanks for the help!
Re: Polygon Division
Hey, we spoke understandably. Glad we all helped!
igloo myrtilles fourmis
