Analytic Geometry.

[KeepingRealBusy]

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.

[dedndave]

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

[KeepingRealBusy]

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.

[dedndave]

http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

[dedndave]

this will help you get from 2 points to standard form

http://en.wikipedia.org/wiki/Linear_equation

[FORTRANS]

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.

[KeepingRealBusy]

Steve,

Thank you for the link.

Dave.

[Farabi]

Here is for a present

Code Select Expand


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


[Gunther]

Hi KeepingRealBusy,

you could find every information you'll need here. Have fun.

Gunther

[KeepingRealBusy]

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.

[Gunther]

Hi Dave,

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. If not, you should think about a kind of fixed point arithmetic. Octave could be a good starting point for that. There are probably other solutions available, too. That's what I would do. Good luck.

Gunther

[KeepingRealBusy]

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.

[dedndave]

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

[dedndave]

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

[KeepingRealBusy]

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:

this will help you get from 2 points to standard form

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.