Cutting a rectangle with straight lines

[mariano_donat]

Hi to everyone.

I'm developing a puzzle game which involves some concepts of geometry.
Suppose you have a rectangle formed by points A, B, C and D. Now, I add points X1 (lies on line AB), X2 (inside the rectangle) and X3 (lies on line AC).
I'd like the output to be the two rectangles resulting from these added points.

I don't know how to do it nor how to ask it properly. Any guidance will be very helpful.

Thanks in advance.

 

[gsal]

Yes, you need to describe your problem much better...

do points a, b, c, d go around the rectangle in clockwise direction? counter-clockwise? do they go from upper-left to upper-right to lower-left, lower-right corners? where exactly are the two additional points and what are the two rectangles you envision as output?

maybe it would be best if you draw everything on grid paper and put the coordinates here.

 

[mariano_donat]

I'm actually envisioning two polygons, not rectangles, I apologize.

Note that Xs points are arbitrary. The user can draw these points however he/she wants.
So, the output for this example would be two polygons:

P1 = {X1, X2, X3, X4, X5, C, D, A}
P2 = {X1, B, X5, X4, X3, X2}

I'm just trying to get the big picture. This is an small problem from what I really want to achieve. Hopefully, solving this will help me to solve the bigger problem.

 

[gsal]

I see.

I am not sure how fool proof and intelligent you want your puzzle game to be...you could probably take baby steps and start with a not so smart game and be really careful as you input points, and work your way to a really smart game that validates your input as it goes...for example, once you start a sequence of new Xn points, it could assume that every point after the first one is the last one of the sequence and keep offering the resulting two polygon as it goes until the user indicates the end of sequence, somehow...also, you need to make sure that once it is known which polygon is going to be divided, that every subsequent new point actually falls inside the polygon...this may not be easy if your polygon can have "concave" and "convex" corners, you know, like a star or something.

If you limit your puzzle pieces to be made of only vertical and horizontal lines, like you show in your image file, things are a lot easier, of course...I would provide my commentary assuming this ...then you can get more complicated.

So, I am not sure if you are asking help with the logic part, with the analytic geometry part or what. So, I am going to share just a few things that occurred to me when I see your puzzle.

I can see that you want to define a polygon as a sequence of points, this sequence has a few properties:

• First, it is a set,i.e., every point exists only once;
• second, it is an ordered set
• and can be think of as a circular list, really

in other words,
polygon { a , b , c , d } is the same as
polygon { b, c, d, a } and the same as
polygon { c, d, a, b }

So, as soon as the user indicates the start of a new sequence of Xn points and provides the first point, you need to find out in between which two pre-existing points it lies...I think this is easy...just take every two adjacent points, and out of the two X's and Y's coord. of the point, get Xmin,Ymin and Xmax, Ymax if the new point X,Y falls inside this (Xmin<X<Xmax) and (Ymin,Y,Ymax), then your point is between those two adjacent points.

Then, I think you need to wait for the second point to find out which polygon is being split..you need figure that one out...maybe read some literature out there about gaming, 2D graphics...

Once you have the first and second point, the adjacent pre-existing points X1 is in between of and know which polygon you are dealing with...

re-order your polygon so that one of the adjacent points is at the beginning and the other at the end of the set...for example, let's say you have a polygon { a, b, c, d, e} and the new (first) point falls between b and c...the first thing I would do is redefined my set as { c, d, e, a, b }

then, collect all intermediate points and when the user indicates the end of the sequence, get the last point and find out in between which two adjacent points if falls in...the same as before, except this time, you do no need to worry about all polygons and all possible adjacent points, you just need to inspect two adjacent points of the polygon with are working with.

Once you know between which two points the last new X point fall in, you split your polygon there...and attach the Xn sequence to the end of one and the beginning of the other one...for example, if the last Xn falls between d and e, then, the two resulting polygons would be:

{ c, d, x1, x2, x3} and { x1, x2, x3, a, b}

Well...that's it...sorry to leave unfinished business but got to get back to work...

...the solution above is not entirely correct, you need to figure out in which order you need to add the sequence { x1, x2, x3 } to the pre-existing sets {c, d} and { a, b } in other words, you need to figure out whether it is going to be

{ c, d, x1, x2, x3} or { c, d, x3, x2, x1}

if you get it wron, your polygon is going to be "twisted" in the topological sense.

hope this helps

 

[mariano_donat]

I apologize, I couldn't get back any sooner to write the reply to your post as I wanted.
Thank you very much for your response, I followed a different approach, but it was very inspiring!

The two most important points are x1 and x5. Fortunately my game required to keep track of adjacent nodes, so I use that to build up a chain. Also, I can easily figured out which line from the rectangle x1 and x5 were slicing. So, I take the final cut point, in this case is x5 (it works with x1 too). I know what line it cuts, i.e. I know its adjacent vertexes, let's call them p1 and p2. Now, one polygon will be formed by x5 -> p1 -> ... -> x1 -> rest of xn sequence and the other one is x5 -> p1 -> ... -> x1 -> rest of xn sequence. I can easily build up this chain, so that's how I got it.

Thank you very much for your reply.

 

[mariano_donat]

Your post was so inspiring for me, thank you very much! I just wanted to thank once more time and show you where I had to apply this

Thank you very much, again.

 

[gsal]

I see.

That's cool.

Thanks for sharing.