Direct link for mobile devices.

I was walking a few miles in the nice weather this evening when two possible solutions popped into my head for the DisplayGroup drag problem I had in the simulation app (where the pointer arrow from the edge of the DisplayGroup object to the edge of the DisplayItem object does not get drawn if the intersection tests generate false negatives). As long as the idea was fresh I figured I’d go ahead and check it out. It turned out that I already do one of things that occurred to me so that quickly proved to be a dead end. The other idea appears to solve the problem for all the cases I’ve tested.

The problem I found with the method I originally implemented solved for the intersection of two lines using the slope and y-intercept formula. The problem with that is that some values for the y-intercept can be quite high which can lead to rounding errors at the intersection point. If I write formulas for the lines in terms of one of the endpoints of each line then the formulas get slightly more complex but the accuracy of calculating the intersection point should increase.

The point-slope formula for a line is:

y_{p} = y_{1} + m_{12} * (x_{p} – x_{1})

where:

x_{p}, y_{p} = location of arbitrary point on line

m_{12} = slope of line, (y_{2} – y_{1}) / (x_{2} – x_{1})

x_{1}, y_{1} = location of line endpoint 1

x_{2}, y_{2} = location of line endpoint 2

Substituting for the y_{p} we look to solve for x_{p} for the intersection of lines 12 and 34

y_{1} + m_{12} * (x_{p} – x_{1}) = y_{3} + m_{34} * (x_{p} – x_{3})

y_{1} + m_{12} * x_{p} – m_{12} * x_{1} = y_{3} + m_{34} * x_{p} – m_{34} * x_{3}

m_{12} * x_{p} – m_{34} * x_{p} = y_{3} – y_{1} + m_{12} * x_{1} – m_{34} * x_{3}

x_{p} * (m_{12} – m_{34}) = y_{3} – y_{1} + m_{12} * x_{1} – m_{34} * x_{3}

x_{p} = (y_{3} – y_{1} + m_{12} * x_{1} – m_{34} * x_{3}) / (m_{12} – m_{34})

Once you have the x-coordinate then you get the y-coordinate by reinvoking the first formula. The code has to do some testing for special cases involving vertical and horizontal lines as shown in the new `intersection`

function here:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
function intersection(x1,y1,x2,y2,x3,y3,x4,y4) { //see if line12 crosses line34 between the endpoints of both lines var m12; var b1; var m34; var b2; var ix; var iy; if (x1 != x2) { //first line not vertical m12 = (y2 - y1) / (x2 - x1); if (x3 != x4) { //second line not vertical m34 = (y4 - y3) / (x4 - x3); if (m12 != m34) { if (y3 != y4) { //edge not horizontal ix = (y3 - y4 + m12 * x1 - m34 * x3) / (m12 - m34); iy = y1 + (ix - x1) * m12; } else if (y1 != y2) { iy = y3; //ix = (iy - y1 + x1 * m12) / m12; //save some clocks by rewriting as next line ix = (iy - y1) / m12 + x1; } else { //both lines horizontal therefore parallel return false; } } else { //should not need to explicitly test for overlapping parallel lines for convex shapes return false; } } else { //second line is vertical ix = x3; iy = y1 + (ix - x1) * m12; } } else { //first line vertical if (x3 != x4) { //second line is not vertical m34 = (y4 - y3) / (x4 - x3); ix = x1; iy = y3 + (ix - x3) * m34; } else { //if this happens then no intersection return false; } } if (!(((ix >= x1) && (ix <= x2)) || ((ix >= x2) && (ix <= x1)))) { return false; } if (!(((iy >= y1) && (iy <= y2)) || ((iy >= y2) && (iy <= y1)))) { return false; } if (!(((ix >= x3) && (ix <= x4)) || ((ix >= x4) && (ix <= x3)))) { return false; } if (!(((iy >= y3) && (iy <= y4)) || ((iy >= y4) && (iy <= y3)))) { return false; } //if we haven't failed to this point then return values return {x: ix, y: iy}; } |

Click or tap on any of the non-path objects to make the associated DisplayGroup object visible, then drag that object around the screen with the mouse or by touch. The pointer appears to render smoothly in all cases.