Assume you have a 2d plane (ok… a canvas)… and on that canvas you have two shapes at random coordinates (measured at the CENTER)
Each shape has 4 nodes, of which you know the X/Y coordinates of each, and it is a fact that each of the 4 nodes is at increments of 90 degrees, but the DISTANCE from the center is not the same (but it is know via the coordinates)
Recap. Shape has 5 points. 1 center point, and 4 nodes surrounding that center point at 90 deg incrments (0,90,180,270)
Now, given one of those nodes on EACH of the two shapes draw a line (in segments) to connect the two… each segment of this line must be horizontal or vertical (ie. they two must only be in 90deg increments)
Problem. given the X/Y coordinates of two points, calculate the collection of line segments required to connect them
examples
[
basically I see these combo
0deg to 0deg
0deg to 90deg
0deg to 180deg
0deg to 270deg
90deg to 90deg
90deg to 180deg
90deg to 270deg
180deg to 180deg
180deg to 270deg
270deg to 270deg
the DIRECTION the line is drawn is not overly important, as I can calculate that from other events, so for simplicty sake, the above list is going from lowest angle to highest angle … that is drawing from the 90deg node on shape 1 to the 0deg node on shape 2 results in the same line as going from 0 deg on Shape 2 to 90deg on Shape 1
Avoiding other shapes would be great… but not a compelling requirement…
Once the basic set of segments is calculated, the user will be able to manually drag them around
But there is an object array of classes that defines each shape, where various properties include (but not limited to)
X,Y - center of shape
Rectangle (X1,Y1,X2,Y2) of minimum bounding area
Width (x2-x1)
Height (y2-y1)
I’d start simple with the 4 basic cases
This assume origin is top left 0,0
Two objects - obj1 and obj2
deltaX = obj2.x-obj1.x
deltaY = obj2.y-obj1.y
they are positioned aligned vertically if abs(deltaX) = 0
they are positioned aligned horizontally if abs(deltaY) = 0
and the degenerate case of one on top of another if both deltas are = 0
-if delta X > delta Y then they are misaligned more vertically than horizontally so you going to
if deltaX > 0 then draw right from the center of object1 to 1/2 deltaX
if deltaX < 0 then draw left from the center of object1 to 1/2 deltaX
if deltaY > 0 then draw down the deltaY
else draw up the deltaY
draw to the center of object2
else
if deltaY > 0 then draw down from the center of object1 to 1/2 deltaY
if deltaY < 0 then draw left from the center of object1 to 1/2 deltaY
if deltaX > 0 then draw right the deltaX
else draw left the deltaX
draw to the center of object2
eventually insert code to
approximate other angles by using more segments
not draw over / under other objects
An exercise for the reader is how thy used to phrase it
Ok… I think I have a viable approach to this puzzle… just not sure yet how to work out the final pieces.
Given the data mentioned above…
a) determine an appropriate bounding rectangle that would enclose the points along any path
b) calculate a matrix (am going with 5 x 5 for now) and remove any point that is INSIDE another shape
c) using remaining points find the shortest path (this is where I’m stuck right now)
I know there has to be a published method to do “C”
here is two examples… joining the same two points on two shapes… but the second one has extra shapes that negate the use of some of the points. Light Green is “legal path”, Dark Green is “Best Path”, Red is don’t wanna go there. Notice is the second pic, that it has to backtrack to get to the destination.
THESE WERE DRAWN BY HAND but illustrate examples of the desired results
[quote=15974:@Dave S]Assume you have a 2d plane (ok… a canvas)… and on that canvas you have two shapes at random coordinates (measured at the CENTER)
Each shape has 4 nodes, of which you know the X/Y coordinates of each, and it is a fact that each of the 4 nodes is at increments of 90 degrees, but the DISTANCE from the center is not the same (but it is know via the coordinates)
Recap. Shape has 5 points. 1 center point, and 4 nodes surrounding that center point at 90 deg incrments (0,90,180,270)
Now, given one of those nodes on EACH of the two shapes draw a line (in segments) to connect the two… each segment of this line must be horizontal or vertical (ie. they two must only be in 90deg increments)
Problem. given the X/Y coordinates of two points, calculate the collection of line segments required to connect them
[/quote]
Looks like the Traveling Salesman problem to me. The approach is:
Pick one of the possible paths
If there is no other connection
then declare a succes
else declare nothing
This type of problem is called polynomial and its class is probably ‘nondeterministic polynomial problem’ or in short NP. Main issue with this type of problem is that the amount of time needed to calculate a solution grows exponential and most of the time grows out of control.
It is a special part of theoretical Computer Science.
And for those of you interested here is the code to do it yourself…
This is I believe a version of the “A*” alogritthm… or at least that is what the “C” version of the code said
It does a 5x5 matrix in like 0.00004 seconds (not including the drawing etc)
Note : the code for the GUI was rough… I just threw something together to test the alogrithm which is contained in its own module and class.
