I have tried to take some of your comments to heart. My aim was not to provide a 'free programming service', but to illustrate an idea, as best I could.

The mod, as much of my code, was written for brevity. I have removed it and replaced it with an if. It could be optimised more for speed, but I don't think it would help the simplicity.

I posted the first working solution to the problem, based on your first code, and only calculating the difference. I received no comments on it at all. I still don't understand why. I ifdeffed in some code to calculate both areas, in case that was the problem. I'm sorry if you found this confusing, but I hoped it would be simple enough for people to "preprocess" the code themselves and remove the unused code, if necessary.

In any case, I've removed the ifdefs and improved the code I added. I've expanded it a bit, added more comments, and made it clear why there are no divisions by zero. I've left the 'difference' version pretty much as it is.

Neither piece of code physically splits the polygon. I think this is a step that overcomplicates the procedure.

You have made some fantastic contributions to this thread, in ideas and code, and have produced multiple, very well written, working solutions, but if both algorithms are fully understood and well optimised, I think my solution will work better.

Code: Select all

`screen 13`

''input data (anticlockwise: positive area, clockwise: negative area)

const as integer n = 11

dim as double x(0 to n - 1), y(0 to n - 1)

x( 0) = 7: y( 0) = 11

x( 1) = 2: y( 1) = 9

x( 2) = 2: y( 2) = 8

x( 3) = 3: y( 3) = 5

x( 4) = 8: y( 4) = 5

x( 5) = 5: y( 5) = 2

x( 6) = 10: y( 6) = 2

x( 7) = 9: y( 7) = 9

x( 8) = 14: y( 8) = 4

x( 9) = 18: y( 9) = 6

x(10) = 16: y(10) = 10

''dividing line points

dim as double lx1 = 0, ly1 = 9

dim as double lx2 = 19, ly2 = 5

dim as double ldx_, ldy_, ldx, ldy

ldx_ = lx2 - lx1 ''calculate direction vector of line

ldy_ = ly2 - ly1

ldx = ldx_ / sqr(ldx_ ^ 2 + ldy_ ^ 2) ''make it a unit vector

ldy = ldy_ / sqr(ldx_ ^ 2 + ldy_ ^ 2)

''draw dividing line (pointing in light gray direction)

''all coordinates ares caled by 10.

''y coords are reversed, so y=0 is at bottom of screen.

dim as double lx1_5 = (lx1 + lx2) / 2, ly1_5 = (ly1 + ly2) / 2

line (10 * lx1, 199 - 10 * ly1 )- _

(10 * lx1_5, 199 - 10 * ly1_5), 8

line (10 * lx1_5, 199 - 10 * ly1_5)- _

(10 * lx2, 199 - 10 * ly2 ), 7

''useful vars for following loop

dim as double AreaDiff = 0 ''total difference between two areas

dim as double Area0, Area1 ''left (0) and right (1) areas

dim as double Area(0 to 1) = {0, 0} ''totals of left and right areas

dim as double x1_, y1_, x2_, y2_ ''the line points from the array

dim as double x1, y1, x2, y2 ''line points, after rotation

dim as double dx, dy ''displacement of x2 from x1; y2 from y1

dim as double iy ''point at interception of x axis

dim as double mx ''average width of trapezoid

''here is the main loop that gets the edges, draws them and finds the areas:

for i as integer = 0 to n - 1

''this loop will find the area contained between each edge and the dividing line

''the points are rotated so the dividing line becomes the line x = 0

'get the points for edge n

x1_ = x(i)

y1_ = y(i)

if i + 1 = n then

x2_ = x(0)

y2_ = y(0)

else

x2_ = x(i + 1)

y2_ = y(i + 1)

end if

line (10 * x1_, 199 - 10 * y1_)- _ ''draw edge (in red-violet order)

(10 * x2_, 199 - 10 * y2_), _

56 + int(24 * i / n)

''rotate all the points

x1 = ( ldy * x1_ - ldx * y1_) - (ldy * lx1 - ldx * ly1)

x2 = ( ldy * x2_ - ldx * y2_) - (ldy * lx1 - ldx * ly1)

y1 = ( ldx * x1_ + ldy * y1_)

y2 = ( ldx * x2_ + ldy * y2_)

''if the edge intersects the dividing line, there will be two triangles made by it

'' |-/

'' |/

'' /|

'' /-|

''/--|

''otherwise, there will be a tapezoid

'' |----/

'' |---/

'' |--/

''dy will be the height of the trapezoid, or the height of the two triangles

''when dy is positive, the areas on the right of the line will be positive

''and areas on the left will be negative.

''things will be the other way round when dy is negative.

dy = y2 - y1

''find the total of both areas - one will be subtracted from the other at the end

''if you want to skip this bit, comment out or remove the whole of the following IF block:

if x1 >= 0 and x2 >= 0 then ''both points are to the right of the line

mx = (x1 + x2) / 2 ''average width of trapezoid (positive)

Area1 = mx * dy ''area of trapezoid

Area(1) += Area1 ''add area of trapezoid to right hand area

elseif x1 <= 0 and x2 <= 0 then ''both points are to the left of the line

mx = (x1 + x2) / 2 ''average width of trapezoid (negative)

Area0 = mx * dy ''area of trapezoid

Area(0) += Area0 ''add area of trapezoid to left hand area

else

''points are opposite sides of the line: two triangles

dx = x2 - x1 ''displacement of x2 from x1

''(never zero because points are opposite sides of the line)

iy = y1 - x1 * dy / dx ''point where edge intercepts x axis

if x1 > 0 then ''point 1 on right (so point 2 on left)

Area1 = x1 * (iy - y1) / 2 ''right hand area is first triangle

Area0 = x2 * (y2 - iy) / 2 ''left hand area is second triangle

Area(0) += Area0

Area(1) += Area1

else ''point 1 on left (so point 2 on right)

Area0 = x1 * (iy - y1) / 2 ''left hand area is first triangle

Area1 = x2 * (y2 - iy) / 2 ''right hand area is second triangle

Area(0) += Area0

Area(1) += Area1

end if

end if

''find just the difference in areas and keep track of the total

''the math is basically the same, but it is simplified a lot. If you

''understand the previous section, you should be able to derive this on your own

if (x1 >= 0 and x2 >= 0) or (x1 <= 0 and x2 <= 0) then ''points are same side of line: trapezoid

mx = abs(x1 + x2) / 2

AreaDiff += mx * dy

else ''points are opposite sides of line: two triangles

dx = abs(x2 - x1)

mx = (x1^2 + x2^2) / (2 * dx)

AreaDiff += mx * dy

end if

next i

''Report results:

print "Area to the right = " & csng(Area(1))

print "Area to the left = " & csng(Area(0))

print "Difference (method 1) = " & csng(Area(1) - Area(0))

print "Difference (method 2) = " & csng(AreaDiff)

if AreaDiff > 0 then print "Right area heavier" else print "Left area heavier"

sleep