Simple algorithm for calculating the intercept of two lines?

I have a project where I have two sets of x/y coordinates each describing separate but definitely intersecting lines - e.g., (0,0 to 8,9) and (2,0 to 6,14). Does anyone have a non-math major friendly algorithm for solving for that intersection? Sadly, geometry and trig is a distant memory for all but things I do at least every few years. I have googled for a solution and have found solutions but they seem way too complex for something that perhaps is as simple as I think. Perhaps it does require multiple iterations, etc., just asking for input here. The application specifically is using 3 microphones in a triangular array to locate the X/Y coordinate of a brief, loud sound such as a projectile striking a coplanar piece of, for example, a thin piece of plywood upon which a target is affixed. I have the math and hardware working in successfully obtaining vectors for microphones A-B and B-C sound times of arrival. I also have another pair of microphones spaced a meter apart colinear with projectile path at 2 meters from the gun muzzle. These are for capturing projectile speed with the caveat that it probably only works for supersonic projectiles, the shock wave is shockingly easy to detect and has a very short rise time. Any help would be greatly appreciated. I'm using a Prop 1 and an ESP8266 communicating to a PC app for now but also have the P2 ES board working very nicely (love those fast ADCs!) but I'm waiting for production silicon until progressing further with the P2. Thanks for reading, I wanted to give a relatively complete picture of what I'm doing.

Mike R.
The difference between theory and practice is that, in theory, there is no difference between theory and practice, but in practice, there is.

Comments

  • Wuerfel_21Wuerfel_21 Posts: 351
    edited 2019-05-26 - 20:22:42
    Well, that's basically solving a linear equation.

    You first need to convert the lines into "functions" of the form
    y = (x*slope)+offset
    which can be calculated as such (i think. sanity check before using):
    slope = (y2-y1) /(x2-x1)
    Note that lines parallel to Y can't be expressed, so there needs to be a special case. You might be able to get away with just using a very high slope.
    offset = y1 - (x1*slope)

    Now we can solve for the intersection:
    (x*slope1)+offset1 = (x*slope2)+offset2
    (x*slope1)+offset1-offset2 = x*slope2
    offset1-offset2 = (x*slope2) - (x*slope1)
    offset1-offset2 = x*(slope2-slope1)
    (offset1-offset2) / (slope2-slope1) = x

    x = (offset1-offset2) / (slope2-slope1)
    y = (x*slope1)+offset1
  • @Wuerfel_21 , thank you! That reawakened long dormant neurons. Sadly that's high school level stuff. The things I think I've forgotten...

    Mike R.
    The difference between theory and practice is that, in theory, there is no difference between theory and practice, but in practice, there is.
  • Tracy AllenTracy Allen Posts: 6,386
    edited 2019-05-29 - 19:01:04
    The Wiki for intersection of lines has a formula for Py and Px (the intersection point) in terms of the four x,y coordinates of the two points, without going to slope/intercept form. Lots of terms, but many of the terms appear twice in the formula.
    The terms can be computed first and then combined...
    a = x1 - x2
    b = y1 - y2
    c = x3 - x4
    d = y3 - y4
    e = x1*y2 - y1*x2
    f = x3*y4 - y3*x4
    g = a * d - b * c
    Then
    Px = (e * c - a * f) / g
    Py = (e * d - b * f) / g

    Watch out for points that are close together. Subtractions in the denominator, the term "g", make the equation "stiff". Small errors in the representation of the numbers can make the result blow up if the points are close together. Need to maintain sufficient precision.



  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 22,440
    edited 2019-05-29 - 22:25:35
    Watch out for points that are close together. ...
    ... or if the lines are nearly parallel.

    -Phil

    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Indeed, that term in the denominator approaches zero when the lines are parallel. The intersection point zooms to a far horizon. The denominator is the cross terms of the differences between the x and y coordinates. g = (x2-x1) * (y4-y3) - (y2 - y1) * (x4 - x3)
    Screen%20Shot%202019-05-30%20at%2011.49.41%20AM.png
  • It’s so easy now to visualise this with computers. Back at school when i did this those pics would have been great. It was all theory then. Most computers were valve based!
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Cluso99 wrote:
    It’s so easy now to visualise this with computers. Back at school when i did this those pics would have been great. It was all theory then. Most computers were valve based!
    You were lucky. The ones I used were bamboo-based: two slabs, separated by another one that slid between them.

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Cluso99 wrote:
    It’s so easy now to visualise this with computers. Back at school when i did this those pics would have been great. It was all theory then. Most computers were valve based!
    You were lucky. The ones I used were bamboo-based: two slabs, separated by another one that slid between them.

    -Phil

    LOL, ditto.
    In science there is no authority. There is only experiment.
    Life is unpredictable. Eat dessert first.
  • Cluso99Cluso99 Posts: 15,398
    edited 2019-05-31 - 01:53:46
    OT
    Cluso99 wrote:
    It’s so easy now to visualise this with computers. Back at school when i did this those pics would have been great. It was all theory then. Most computers were valve based!
    You were lucky. The ones I used were bamboo-based: two slabs, separated by another one that slid between them.

    -Phil
    Seems I may not have expressed myself properly :( Then again, maybe you were born with the dinosaurs ;)

    When I was in high school (60's), we used blackboard and chalk. No computers.

    Most computers in the world were valve based, although transistor based computer were starting to take over. Terminals were TTY.

    Would have been nice to see a pair of lines like that on a PC (or tablet) in color. You could zoom in and out to see the intersection, etc. Those nice parabola's that we had to draw could be on a screen, together with the area under a curve. Would have made my day to see those things when learning maths. We had no idea what i*i=-1 (i squared equals -1) was used for - that would come the following year as j*j=-1 with electronics. Wish i'd known what it was used for two years earlier as it would have made more sense, not that I didn't grasp it - maths was my best and favorite.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Technical high school in early '70s, BB, chalk, and in the electronics program I had a Picket 1010ES analog computer. Even came with its own ESD safe leather belt mounted carrying case.
    Ordnung ist das halbe Leben
    I gave up on that half long ago.........
  • Technical high school in early '70s, BB, chalk, and in the electronics program I had a Picket 1010ES analog computer. Even came with its own ESD safe leather belt mounted carrying case.

    lol, carried the analog computer myself, but had to go to the lab to use the Friedan rotary calculator to do statistics!
    Jim
  • RS_Jim wrote: »
    Technical high school in early '70s, BB, chalk, and in the electronics program I had a Picket 1010ES analog computer. Even came with its own ESD safe leather belt mounted carrying case.

    lol, carried the analog computer myself, but had to go to the lab to use the Friedan rotary calculator to do statistics!
    Jim

    Ah, Friden. My mate in NZ has a few old Friden calculators that he has fixed and now run.

    I cut my teeth on the Friden System Ten computer (later Singer and then ICL) System Ten). It was a mini, but that mini was the length of my garage. I need to find those old photos.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • I love hearing about the experiences of you guys! It’s so interesting to hear of early computers!
    Windows 10 Home:
    Propeller Tool 1.3.2, BASIC Stamp Editor 2.5.4, Javelin Stamp IDE x.x.x, Arduino IDE, PST
    Hardware:
    BASIC Stamp Board of Education, Propeller Board of Education, Propeller Project Board, Propeller Mini

    Me, a programmer in English class, asking for grammar help: “What is the syntax for this statement?”
  • Thank you you to all who answered my initial question. Your responses led me down a road of research and successfully comprehending your answers, including the geometry and trig behind those answers. I'm also very happy that further discussion involving several people's past experiences from decades ago has ensued. It's extremely interesting! My first computer was a Sinclair ZX-80 that got me hooked and has progressed from there. CP/M on a Franklin 2+ with a Z80 card and a $600US 5MB harddrive the size of a shoebox was my first experience with a traditional OS after Apple DOS and ProDOS. Using Dbase II and WordStar REALLY opened my eyes! Just sharing my story from a while back...
    The difference between theory and practice is that, in theory, there is no difference between theory and practice, but in practice, there is.
  • Followup: with input received I now have a working prototype that is able to detect and calculate the point of impact of a projectile on a target using four electret microphones with comparators whose outputs are fed to a P1 to capture the times of arrival. The TOAs are sent to an ESP8266 which then wifis the TOAs to a remote PC program which does the post processing on that data. The project uses an additional two mikes a couple of meters from the firearm muzzle and uses the differential of TOAs of the shock wave from the passing bullet to calculate velocity. I'm very grateful to allof you; thank you!

    Mike R.
    The difference between theory and practice is that, in theory, there is no difference between theory and practice, but in practice, there is.
Sign In or Register to comment.