Segment intersection formula explained

[@cesarmoltoni]

Amazing tutorial Dr Radu, I have made a little change breaking "getIntersection" into two functions and interchanging arguments: function getIntersection(A, B, C, D) { const t = calculateOffsets(A, B, C, D) const u = calculateOffsets(C, D, A, B) if (t && u) { return { x: lerp(A.x, B.x, t), y: lerp(A.y, B.y, t), offset: t } } return null } function calculateOffsets(A, B, C, D) { const top = (D.y - C.y) * (A.x - C.x) - (D.x - C.x) * (A.y - C.y) const bottom = (D.x - C.x) * (B.y - A.y) - (D.y - C.y) * (B.x - A.x) if (bottom != 0.0) { const offset = top / bottom if (offset >= 0 && offset

[@Radu]

Hey! That's really nice :-) Pinning your comment for others to see!

[@quentinquadrat9389]

I found a bad case: AB = ((0.0f, 0.0f), (10.0f, 0.0f)) and CD = ((10.0f, 0.0f), (20.0f, 0.0f)) bottom will be 0 so it will find no solution while the intersection is 10.

[@Radu]

You're right! Bottom is also zero when points of the segments are collinear... I wonder what we can do about it? 🤔

[@quentinquadrat9389]

​@@Radu better to keep talking on the ticket that I reopened on your virtual-world project. Tonight I'm busy. Yes collinearity is painful and shall be managed separately: if segment are superposed, you have plenty of intersections (but let say the 2 corners of the smaller segment), else 0 intersection when they are parallel, else 1 intersection. On other point in your road generation, you discard the case where segments are connected by a single vertex :)

[@Radu]

I will have to check those tickets at some point. Have had many things keeping me busy, recently :-\

[@yandra_dev]

I simply can't explain how much I love this guy, one of the best teachers I ever had.

[@Radu]

Good that you are learning :-)

[@ЛюдмилаБаїк-ъ9ь]

Radu is pure gold )

[@crypticmeow]

One of the best tutor for learning maths and coding.

[@Radu]

Thank you :-)

[@eugeniogonzato]

You opened my mind in a way that nobody did before, thanks.

[@Radu]

Happy to hear that :-)

[@williamikennanwosu]

You lay things out clearly, explain things well and code at a pace that is easy to follow along. Top notch teaching Radu 💯!

[@Radu]

Thank you :-)

[@williamikennanwosu]

@@Radu You are very welcome Radu 😁!

[@Eternam]

a master class, thank you very much Radu, waiting for the next one.

[@Radu]

Thanks Eternam :-) glad to hear you're excited!

[@awekeningbro1207]

i really love this sort of coding, which involves maths! It makes the problem so much more engaging and challenging!

[@Radu]

I like it too... It also makes the math easier to understand when visualized like that. Thanks for watching!

[@redundantqwail9088]

After trying a number of methods, I'd determined line segment collision detection to be an integral part of an effective way to determine A) if a sprites projected path is going to be intersecting a block B) which side of the block and therefore how to respond to it. I've looked at a number of resources that give similar equations with little explanation of beyond what the components are. I hate using math I don't understand in my projects, so the in depth explanation given here was a godsend. Keep producing awesome content!

[@Radu]

I'm happy to hear you found good uses for it :-) Thanks for watching!

[@amitlavian]

Great stuff :) I really like the approach of visualizing things to make the explanations clearer

[@Radu]

Thanks! I'll make try to make more things like this.

[@hri7566]

literally the only explanation i can find for the hardest part of raycasting

[@Radu]

Really? There must be others as well :-) it's a popular topic!

[@lukasaudir8]

Radu is a super teacher!! Teaching the intuition and logic behind more complex topics, by simply breaking down the complex into smaller simple pieces is a brilliant way to teach, and surely the lesson will stick with the student forever, I'm glad that people like you exist and are willing to share that knowledge, Thank you Radu!!

[@Radu]

Glad to be of help :-)

[@nurbekss2729]

Dude ,you have to become a prof.You are such genious of explaining the complex things in the easiest way.Thank you sir.

[@Radu]

I got my PhD in 2017. Does it count? :-)

[@nurbekss2729]

@@Radu Actually,I saw your PhD defending .I have to admit you did a great work! I just wanted to tell you about your pure talent of explanation. Always thought that I am dumb in math and will never get it.But after some "switches" to good written work or people who helped me to understand more clearly the subject ,I feel myself more confident in math right now . You know about people psychology/attitude .If you dont get once you will never return to it again ,saying it's not for me or it's too hard.So the world needs a good teachers and it doesn't matter if you are a prof in univ or youtube maker. Anyway love your content,wish you the best. P.s :Can't imagine my self studying CS w/o Stackoverflow or youtubers lol.

[@Radu]

Thanks for the nice comment :-) [PS: KZbin just enabled a feature that I can easily find these replies... wasn't possible until now]

[@josephsam2145]

Thank you very much for your tutorials.

[@Radu]

Glad you like them! :-)

[@LBCreateSpace]

I love Radu. Great teacher.

[@Radu]

Thanks :-)

[@daiyaanmuhammad]

Wow! Didn't even realize I actually watched a half hour content without skipping anything. Awesome explainations man. You've earned a sub.

[@Radu]

Glad to hear :-) hope you'll find it useful!

[@bloppai9462]

Brilliant explanation, thank you so much!

[@Radu]

Glad it was helpful!

[@ScriptRaccoon]

This is a really good and pictorial explanation! As a mathematician I would have explained it quite differently, but probably you are right that this scares people away :D

[@Radu]

I'm glad to see a mathematician agreeing with me :-) I was actually waiting for the opposite :-D what I did here is not really standard... and not a formal proof, but I feel these things are needed as well. Visualizing things like that helped me a lot during my research: not only to verify new ideas, but also to see if there are bugs in the code.

[@abdulnafay72]

Hey mathematician please teach me.

[@antonioguilherme1844]

thank you teacher. I'm Brazilian, I was looking for some content about collision between line segments, but I couldn't find it, you saved me.

[@Radu]

Glad you found it useful. Another, more mathematical approach is linked in my video description.

[@henrmota]

Underrated channel.

[@Radu]

Thanks for watching :-)

[@Radu]

Can you think of a way to use segment intersection in your project? :-)

[@basiccoder2166]

I've tried to use intersection in roundabout and confused the hell out of myself (⊙_⊙;)

[@basiccoder2166]

other way i was thinking about intersection is sorting that happens in production factory where 2 similar or different product either intersect or separate out

[@Radu]

@@basiccoder2166 Oh, wow. Did you di intersection between line and circle then? :-)

[@Radu]

@@basiccoder2166 Yeah, that's the (intersection) concept from set theory :-)

[@basiccoder2166]

@@Radu yes tried to😂

[@eitanbegayev9290]

please explain me how to get the uTop, mt calculation desn't work

[@___d3p1]

Great linear interpolation related video! I hope my English level could be good enough to be able to express gratitude for your videos. The creative way in which you explain, the program you develop to exemplify what is being explained in an entertaining way, the editing... all the time spent in front of the camera and off it, has great value to me. All your students should be proud to have such a great teacher!

[@Radu]

Thanks for the nice words, and thanks for watching :-)

[@AtticusColdfield]

Okay. Well, THAT was INCREDIBLE!

[@Radu]

Haha, glad to hear :-)

[@ЛюдмилаБаїк-ъ9ь]

Watched, it is just all about algebra, solving system of equations, at last I found the practical use of those countless school exercises )

[@Radu]

Yeah, one hope I have with these videos is to make people see that the things they learn in school are not 'useless'.

[@unknown-bx8my]

Very useful! Right now, i know how to use this function in all cases as i need after understanding it. Thank you.

[@Radu]

You're welcome!

[@bawbak8800]

Thank you sir, I really appreciate that you explained it in a programming way and not in the math way. 🙏 You have no idea how many videos I've watched to understand this topic, but because all of them explained it with the math language, I couldn't comprehend it at all and it just frustrated me

[@Radu]

I'm happy to hear :-) it's the reason I made it.

[@serveshchaturvedi2034]

Thank you, professor Gem! 💎❤

[@Radu]

:-)

[@andresgardiol8111]

Great video! I learn a lot with your tutorials!

[@Radu]

Thanks :-) Happy to hear that!

[@eitanbegayev9290]

please explain how to find the uTop, u cant calculate it, i always get (B - A) there instead of (A - B), please help

[@coachtroop]

As all of your videos have been so far - very entertaining and enlightening. I am excited to see the rest of this series 😀 Thank you for putting the effort into these.

[@Radu]

Great to hear that :-) Thanks for watching!

[@DanielJoseAutodesk]

I liked.😁👍 Simple and direct. Very good teaching. Demonstrating mastery over what you want to explain 👏👏👏👏. So you've gained another subscriber. 👍😁

[@Radu]

Thank you :-)

[@pand0ras]

interesting approach, i just used the 2point vector form, and shuffled them around to get the intersection point. It's maybe a little bit easier. like (y2-y1)/(x2-x1) * (x-x1) *y1. Shorter, less to calculate.

[@Radu]

Nice work :-)

[@vasylp.4007]

Hello. Can I get the code source of this video?

[@Radu]

Sorry, haven't saved this one since it doesn't really do anything...

[@od1367]

Thank you for this explination. This is pobably the best vidoes i have seen on youtube relating to CS!!!!!!!!!!!!!!!!❤

[@Radu]

Glad to hear that. I tried to handle the concept well.

[@engtari]

Beautiful stuff

[@Radu]

Thanks!

[@calebcadainoo]

I really love your tutorials 👏👏 How do I detect a shape click on the canvas? Example if I have a circle or rectangle on the canvas at any point and I click on any of them how will I know if the user clicked a section of the rectangle or circle?

[@Radu]

You may want to look into the 'isPointInPath' method of the canvas context.

[@abdulnafay72]

May be you can check if your mouseX and MouseY is same as PointX PointY

[@calebcadainoo]

@@Radu oh okay 🔥🔥

[@igor2703]

English is not my native language, but I can perfectly understand everything you say. You are amazing, I love your channel and I wish I knew sooner!

[@Radu]

Hi, and welcome to the channel :-)

[@JeanDAVID]

is there a github to get the source files ? thanks

[@Radu]

You can get the code for getIntersection from the self driving car repository: github.com/gniziemazity/Self-driving-car But the code of this whole demonstration is not online.

[@mattoattacko]

your intro is great :D

[@Radu]

Haha, thanks! There's an extended version on my channel :-)

[@mattoattacko]

@@Radu I showed it to my gf, and now we will just randomly sing "coding with Radu.🎶Coding with Radu🎶"

[@Radu]

@@mattoattacko Probably a one hit wonder :-))

[@mattoattacko]

@@Radu Would win Eurovision IMO😁

[@Radu]

@@mattoattacko Hahaha :-)) next year maybe!

[@Alex_Aly]

Slove the system ecuation composed of both linear equations d1:ax+by+c=0 and d2:ax+by+c=0, and you get the intersection point , but first test the slope for paralel lines. at least that is what I've tried.

[@Radu]

You can do that. Have to also consider vertical lines (slope is undefined then).

[@imnotchinese6235]

i love your intro

[@Radu]

Thank you :-) there's also an extended version if curious kzbin.info/www/bejne/aWS8qH6Zi7ZkrNk

[@moussadotco]

Cyprien fait des maths. Love it.

[@Radu]

Who is Cyprien? :-)

[@moussadotco]

@@Radu kzbin.info/www/bejne/mGa0Yn5tn9-NhJY

[@Radu]

:-))

[@experimentnameuntitled22]

for the calculation of uTop, why is there a A.x - B.x instead of B.x - A.x? I followed the same steps as the steps for getting t and can't seem to get this result

[@Radu]

A.x - B.x is same as - (B.x - A.x). Could it be that you have another minus (-) sign somewhere that cancels this one out?

[@experimentnameuntitled22]

@@Radu Thanks for the reply. Yeah I figured it out. I checked and the subtraction in the divisor of my u equation is actually reversed. So I had to multiply both side by -1 and got the same answer.

[@Radu]

Great!

[@abhishekgourav6144]

Need to follow him...

[@Radu]

:-)

[@ap666-o8h]

Amazing video, as always. One question: is the drawing of the car need to be done by us, or did I miss something? waiting for the next video

[@fleckenfurz77]

You mean looking for a little picture of a car, and then simply replace.. ctx.rect(....) with.. ctx.drawImage(img, sx,sy,sw,sh, dx,dy,dw,dh) ??? i believe in you! you can do it! ;-)

[@ap666-o8h]

@@fleckenfurz77 ok, thank you. i'll try.

[@Radu]

Thanks! About the car, I did post one challenge on my community tab where the goal was to make a car, but I will eventually show you how to draw it and how to make them have random colors (it will be the final lecture).

[@ap666-o8h]

@@Radu Thank you! I'll wait for that lesson. Meanwhile, I'm really curoius about the ML part, I'm wainting for it!.

[@Radu]

@@ap666-o8h Glad to hear. I've put the most effort into the Neural Network lecture. Should be out on 15th of April (on my birthday :-D) if all goes according to plan.

[@basiccoder2166]

out of curiosity is the function lerp is same as y = mx+t ?

[@Radu]

What you're writing here is the line equation. And lerp, as the name says: 'linear' interpolation is also a line, yes. But in lerp m is defined as a difference between two end values, say: t and w (with your naming convention). So y=(w-t)x+t. That's because lerp is supposed to give you values for y within the interval [t,w] with values for x in [0,1]. You can also use x outside of the [0,1] range and then it's called extrapolation.

[@basiccoder2166]

@@Radu Thanks

[@Radu]

@@basiccoder2166 No problem!

[@paulbaxter7002]

Excellent. The only thing I would suggest is adding a link to the code.

[@Radu]

Yeah, unfortunately it got deleted somehow 🤣

[@jubrazkhan255]

How to select rectangle and resize rectangle please help me. I made drawing app

[@Radu]

Can you share some sample code you're working with? I'm not sure I understand your problem...

[@adilsonbuset738]

Valeu!

[@Radu]

E de bine? :-D

[@adilsonbuset738]

Yes, Master, this class was awesome!@@Radu

[@Radu]

Merci :-)

[@fereshtekasra5038]

You are an angle ,,,🎉❤😊

[@Radu]

:-)

[@eitanbegayev9290]

pleaseeee help me understand how to get th uTop. i cant do it. i get the wrong answer all the time idkw

[@Radu]

Hard to help in the comments... just keep in mind that the result you get can be different as long as it is equivalent. Like -(B-A) is the same as (A-B), but a minus (-) must be there.

[@eitanbegayev9290]

@@Radu yes, that waz the problem, thank you radu. I'm so happy i found your channel😇

[@Radu]

@@eitanbegayev9290 thanks for watching!

[@soussousalahiddine5933]

you are awesome

[@Radu]

Thanks :-) and thanks for watching!

[@georgetheprogrammer]

Rock lee reference. 🔥🔥🔥🔥🔥🔥🔥🔥

[@Radu]

:-) yeah, one of my favorite scenes in the whole series.

[@boonga585]

28:00

[@canimeup]

love it!

[@Radu]

Cool! Thanks :-)

[@boonga585]

19:55

[@Radu]

What about it?

[@osamaabozahra]

Thanks for the wonderful content, very much appreciated. I just have a question which is killing me, you didn't initialize the variable myCanvas and somehow it is working with you, hooow?😃

[@Radu]

All IDs defined using HTML are by default global variables. I don't do this very often because its easy to overwrite those if not careful... I don't recommend that practice, but for something like this, where we're not really building anything real, it's ok. Good question! I think not many people know this!

[@osamaabozahra]

@@Radu wow this is new to me, I have an experience for like 4 years now and this is the first time to know this. Thanks again for the explanation and for the content.

[@Radu]

@@osamaabozahra Maybe better that way :-) it's not a good practice, I think. And, I'm sure that after 4 years you know many other things I don't! Keep it up and thanks for watching!

[@_gunnnu_]

is the dropping of hand weights in your intro supposed to be a resemblance to Rock Lee from Naruto?

[@Radu]

:-))) yes...

[@rmsv]

If the two segments overlap, there are parallel but collision occurs.

[@Radu]

True, would you implement this differently?

[@rmsv]

@@Radu If the segments overlap, I would return a point of intersection anywhere in the region of overlap, maybe using both segments current direction of movement to set a collision point that's "happening first". What's your take on this? Was it intentional to not trigger a collision with overlapping segments?

[@Radu]

@@rmsv Well, if they overlap there is no collision 'point' but a collision 'segment'... so proper way would be to return that. Now, I couldn't possibly return all (infinitely many) points that form that segment :-) so maybe returning it as a kind of interval that represents all points within the range. I don't know :-| another possible way would be to return nothing... if intersection would mean that one segment must have one endpoint on one side and another on the other (which overlapping segments do not have). I think this is actually the case in this video. Would have to check the code again to verify and I'm not at the office, so I'll probably forget :-D

[@Aaackermann]

Here I transcribed the code: (But I made some minor changes to fit my needs, but It works and you might find this helpfull) let canvas = document.getElementById("canvas") let ctx = canvas.getContext("2d") let angle=0; const A={x:200, y:150}; const B={x:150, y:250}; const C={x:50, y:100}; const D={x:250, y:200}; const mouse={x:0,y:0}; document.onmousemove=(event)=>{ mouse.x=event.x; mouse.y=event.y; } function lerp(A,B,s) { return A+(B-A)*s } let t=-1; let u = -1; function drawDot(point,label,isOutside) { ctx.beginPath() ctx.fillStyle=isOutside?"red":"white"; ctx.arc(point.x,point.y,10,0,Math.PI*2); ctx.fill() ctx.stroke(); ctx.fillStyle="black"; ctx.textBaseline="middle"; ctx.font="bold 14px Arial" ctx.textAlign="center" ctx.fillText(label,point.x,point.y); } function animate() { const radius=50; A.x=mouse.x+Math.cos(angle)*radius; A.y=mouse.y-Math.sin(angle)*radius; B.x=mouse.x-Math.cos(angle)*radius; B.y=mouse.y+Math.sin(angle)*radius; angle+=0.02; ctx.clearRect(0,0,canvas.width,canvas.height); ctx.beginPath(); ctx.moveTo(A.x, A.y); ctx.lineTo(B.x, B.y) ctx.moveTo(C.x, C.y); ctx.lineTo(D.x, D.y) ctx.stroke(); drawDot(A,"A",false); drawDot(B,"B",false); drawDot(C,"C",false); drawDot(D,"D",false); let M={ x:lerp(A.x,B.x,t), y:lerp(A.y,B.y,t) } let N={ x:lerp(C.x,D.x,u), y:lerp(C.y,D.y,u) } const I=getIntersection(A,B,C,D); if (I) {drawDot(I,"I",false)} //ctx.beginPath(); //ctx.rect(canvas.width/2,0,I.bottom/100,10); //ctx.fill(); drawDot(N,"N",u1); u+=0.005; drawDot(M,"M",t1); t+=0.005; requestAnimationFrame(animate); } function getIntersection(A,B,C,D){ const vTop=(D.x-C.x)*(A.y-C.y)-(D.y-C.y)*(A.x-C.x); const uTop=(C.y-A.y)*(A.x-B.x)-(C.x-A.x)*(A.y-B.y); const bottom=(D.y-C.y)*(B.x-A.x)-(D.x-C.x)*(B.y-A.y); if(bottom!=0){ const v=vTop/bottom; const u=uTop/bottom; if(v>=0 && v=0 && u

[@Radu]

Thanks!

[@mazlumkoyuncu5549]

now i realize i was always using lerp to generate random number between min and max value😅

[@Radu]

Cool :-) you probably know lerp very well in that case... probably just didn't know it has a name.

[@RajVenkatVijayakumar]

bro has 654 missed calls from microsoft

[@Radu]

I hope not :-/ I worked for them a while back and missed calls might mean I did something bad :-D

[@Xoundz]

*How did you do that !???* 😯😲😳🤯

[@Radu]

Do what exactly? :-)

[@Xoundz]

@@Radu I really love and admire your thinking and explaining capabilities. You are JUST amazing ! I am continuously watching your videos from last 3 days and feel JS is easy and fun. Understanding mathematical expressions taking some time, though. 🤭

[@Radu]

@@Xoundz Thank you :-) happy to hear you're learning!

[@MikkelGissel]

How is it possible to select the canvas on the id without a query selector? What is this sorcery! And thanks for great videoes - don't hold the math =)

[@Radu]

They are globals, by default, but I don't recommend doing this. They can easily get overwritten.

[@abdulnafay72]

Holy Shit 😂. Can you teach me mathematics?

[@Radu]

Probably, since you watched this video, I already did :-D

[@__________________________6910]

Coding with radu la la la

[@Radu]

Haha :-) here is the extended intro, if curious: kzbin.info/www/bejne/aWS8qH6Zi7ZkrNk

[@__________________________6910]

@@Radu noice : )

[@__________________________6910]

@@Radu love this intro

[@Radu]

:-))

[@zVOLT220z]

My head is gonna explode

[@Radu]

You find it difficult? Which part is causing you trouble?

[@zVOLT220z]

@@Radu The part of getting back to math, even tho it's basic math I'm not used to think at all, I did the uTop alone and got the same as you (glad for that). I do got questions for this project on C#, as I'm stuck in this part specificaly, whenever I try to create my lines, I put them in a Canvas but for some reason they all get messed up, the orientations isn't good and half of the lines get hidden for some unknown reason to me. It does work with Rectangles, except I don't know how to get their coordinates inside the Canvas. Thanks for the lessons, I watched everything twice now. I'm doing an Automation bachelor degree and A.I. is something I want to get to know, in it's raw state.

[@Radu]

@@zVOLT220z Glad to hear you find this useful. If you're having trouble with doing it in C# you could try sharing the code (like maybe on my Discord) and I'll have a look.

[@exploring.the.world2023]

Fain

[@Radu]

Merci :-)