Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-02-20 05:37:23

webwolve
Member
Registered: 2006-02-20
Posts: 2

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!

Offline

#2 2006-02-20 08:10:02

mikau
Member
Registered: 2005-08-22
Posts: 1,504

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.

Offline

#3 2006-02-20 09:00:42

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,582

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 (2006-02-20 09:02:36)


igloo myrtilles fourmis

Offline

#4 2006-02-20 09:57:19

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

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

Online

#5 2006-02-20 10:07:40

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Polygon Division

thats essentially what I meant. :-)

Last edited by mikau (2006-02-20 10:07:52)


A logarithm is just a misspelled algorithm.

Offline

#6 2006-02-20 10:36:33

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,582

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

Offline

#7 2006-02-20 10:50:12

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,582

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)/(By-Ay)

Cy = Ay + HeightToDivideLine


igloo myrtilles fourmis

Offline

#8 2006-02-21 03:52:25

webwolve
Member
Registered: 2006-02-20
Posts: 2

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!

Offline

#9 2006-02-21 03:57:57

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,582

Re: Polygon Division

Hey, we spoke understandably.  Glad we all helped!


igloo myrtilles fourmis

Offline

Board footer

Powered by FluxBB