Ok, everyone. I have forgotten how to calculate the intersection of two lines, given that each of the two lines are described by two (x,y) points. Can anyone give me a beautiful Christmas present and tell me how to do this?
Dave.
you can convert the 2 points into a standard form linear equation
Y = mX + b
m = slope
b = y intercept
so - if you have 2 linear equations for the 2 lines,
do a simultaneous solution where the 2 points are the same
Dave,
Thank you.
I have been digging in Wiki. Seems that I have lost some of my school books in one of our moves.
Dave.
http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection (http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection)
(http://upload.wikimedia.org/math/f/3/f/f3f00114cd81250f4f90308b6f96db64.png)
this will help you get from 2 points to standard form
http://en.wikipedia.org/wiki/Linear_equation (http://en.wikipedia.org/wiki/Linear_equation)
Hi,
Here is a link that I used to find interesting.
Frequently Asked Questions for comp.graphics.algorithms
http://www.faqs.org/faqs/graphics/algorithms-faq/
1.03: How do I find intersections of 2 2D line segments?
Cheers,
Steve N.
Steve,
Thank you for the link.
Dave.
Here is for a present
f2DLineCollisionDetect proc uses esi edi lpLine:dword,lpLine2:dword,lpPointResult:Dword
LOCAL dX1,dX2,dY1,dY2:dword
LOCAL C1,C2,M1,M2:real4
LOCAL tmpM,tmpC,tmp:real4
; m=dY/dX
; C=y-(m*x1)
; x=(C2-C1)/m1-m2 y=(m1*x)+c1
mov esi,lpLine
mov edi,lpLine2
mov ecx,[esi].Line.X2.x
mov eax,[esi].Line.X1.x
sub ecx,eax
mov dX1,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[esi].Line.X2.y
mov eax,[esi].Line.X1.y
sub ecx,eax
mov dY1,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[edi].Line.X2.x
mov eax,[edi].Line.X1.x
sub ecx,eax
mov dX2,ecx
mov esi,lpLine
mov edi,lpLine2
mov ecx,[edi].Line.X2.y
mov eax,[edi].Line.X1.y
sub ecx,eax
mov dY2,ecx
;M1
;m=dY/dX
fild dY1
fidiv dX1
fstp M1
;M2
fild dY2
fidiv dX2
fstp M2
;C1
;C=y1-(m*x1)
fld M1
fimul [esi].Line.X1.x
fstp tmp
fild [esi].Line.X1.y
fsub tmp
fstp C1
;C2
fld M2
fimul [edi].Line.X1.x
fstp tmp
fild [edi].Line.X1.y
fsub tmp
fstp C2
mov edx,lpPointResult
;x=(C2-C1)/m1-m2
fld C2
fsub C1
fstp tmpC
fld M1
fsub M2
fstp tmpM
fld tmpC
fdiv tmpM
fistp [edx].POINT.x
;y=(m1*x)+c1
fld M1
fimul [edx].POINT.x
fadd C1
fistp [edx].POINT.y
ret
f2DLineCollisionDetect endp
Hi KeepingRealBusy,
you could find every information you'll need here (https://en.wikipedia.org/wiki/Intersection_%28Euclidean_geometry%29). Have fun.
Gunther
Thank you all for the information and links. What I need to work out is how to do this efficiently with huge numbers (500 to 1000 decimal digits).
Dave.
Hi Dave,
Quote from: KeepingRealBusy on December 30, 2014, 02:02:10 AM
Thank you all for the information and links. What I need to work out is how to do this efficiently with huge numbers (500 to 1000 decimal digits).
do you have large integers? If so, you can collect up some ideas and information here (http://www.codeproject.com/Articles/2728/C-BigInteger-Class). If not, you should think about a kind of fixed point arithmetic. Octave (http://octave.sourceforge.net/packages.php) could be a good starting point for that. There are probably other solutions available, too. That's what I would do. Good luck.
Gunther
Gunther,
I looked at the list of functions and saw nothing that looked like it handles bignums. I haven't downloaded any code to see if it could be adapted to windows (I don't do linux (or C++ /C# for that matter so I don't use the MS bigInteger? C++ class).
Do you have any clue which Octave package (if any) may support bignumbs?
I looked at the function list in Geometry, but without downloading the code, I do not know if the functions support bignumbs.
Dave.
you are talking about integers that may have as many as 416 bytes (may result in as many as 1002 decimal digits)
i would start with add, subtract, multiply, divide routines
add and subtract are fairly simple
multiply is a little harder - and divide is a little harder, still
once you have those, you can write a routine to find the intersection
most bignum libraries support either 256-bit or 512-bit integers - not going to help you
i do have routines that will convert large integers to decimal strings for you :P
there's even one to do integer exponentials...
http://masm32.com/board/index.php?topic=222.0 (http://masm32.com/board/index.php?topic=222.0)
Dave,
I have implemented a bignum library, but it should really be called BigPosInt since it does not support negative numbers or floating point. It currently is limited to binary numbers with up to 64K bits, 8K bytes, or 2K dwords. It supports Add, Sub, And, Or, Xor, PowOf2, Mul, Div, Sqrt, Display (in decimal), and Input (numbers in bases from 1 to 64 where 1 is for passing in a binary image to be moved to a number structure). I am currently trying to speed it up (aligning loops, reducing pipeline stalls) and conditionally removing validation checks from internal helper functions. The main functions are formally declared as Public and deal with the numbers as objects, only dealing with the numbers as an index to the real numbers. The Public functions validate and convert the index to a pointer to the number structure and then call a helper function declared as Private to do the actual work. There are also Public functions that use pointers to the numbers but still have validation. For absolute speed, just use the Private functions.
Public/Private are a formality, all of the functions are together in a single assembly with Public/Private data declarations and Public/Private Include files prototypes and definitions.
In trying to calculate the intersections of the two lines in TwoPoint form, the numbers end up with a complicated form that can eventually be reduced to an X/Y form so an integer divide can be done. See your prior post:
Quote from: dedndave on December 25, 2014, 10:19:15 AM
(http://upload.wikimedia.org/math/f/3/f/f3f00114cd81250f4f90308b6f96db64.png)
this will help you get from 2 points to standard form
http://en.wikipedia.org/wiki/Linear_equation (http://en.wikipedia.org/wiki/Linear_equation)
Some of these values may end up as negative values which would eventually cancel out (since the intersection is in the first quadrant), but it messes up the arithmetic. I may have to implement negative number support.
Dave.
Dave,
Quote from: KeepingRealBusy on December 30, 2014, 05:04:05 AM
Do you have any clue which Octave package (if any) may support bignumbs?
I looked at the function list in Geometry, but without downloading the code, I do not know if the functions support bignumbs.
Dave.
Octave is available for Windows (https://www.gnu.org/software/octave/download.html), too. An explanation how to install and use it can be found here (http://wiki.octave.org/Main_Page). The sources are available and should give an idea to solve the problem. But it's probably better to follow Dedndave's proposal, because to use the Octave sources needs some knowledge in C/C++ and the installation of GCC (MinGW) under Windows.
Gunther
you will find that support of signed values is essential :t
and - for long integers, it slows things down to convert a negative to positive to work on it
so, the routines should natively support signed values by design whenever possible
if you look at my signed ling long kai fang routines, you will get an example of how to handle negatives as positives
i create a DWORD flag that is either 0 or 0FFFFFFFFh (0 if it's positive)
when processing the working value, that flag is XOR'ed onto each DWORD (in register)
at the end, when i process the last DWORD, the flag is also subtracted from the low-order DWORD (also in register)
(X - (-1)) = X + 1
so, you XOR the entire negative value with 0FFFFFFFFh, then add one
this is faster than doing that to the entire value in memory before processing
Dave,
Thank you for the hint, I'll look into it.
Dave.