Triangle and Point Intersection
Author 
Message 
Raknarg

Posted: Mon Jun 17, 2013 1:57 pm Post subject: Triangle and Point Intersection 


Trying to make a function that tells you if a point is within a triangle. I created a parametric equation here:
p = s * a + t * b
where p is a point, a and b are vectors, s and t are variables that tell you how many of each vector. From this, I created two equations:
s := (py * bx px * by) / (ay * bx  ax * by)
t := (py * ax px * ay/ (by * ax  bx * ay)
It almost works. I'm working in turing atm, so I have a function as such:
Turing: 
fcn intersects (px, py, x1, y1, x2, y2 : int) : boolean
var s, t : real
s := (py * x2  px * y2) / (y1 * x2  x1 * y2)
t := (py * x1  px * y1) / (y2 * x1  x2 * y1)
if s > 0 and s < 1 and t > 0 and t < 1 then
result true
else
result false
end if
end intersects

However it intersects as if the two vectors made a parallelogram instead of a triangle... Any ideas?
I should clarify I understand why they do this, I'm just not sure how to change it. 





Sponsor Sponsor



DemonWasp

Posted: Mon Jun 17, 2013 4:29 pm Post subject: RE:Triangle and Point Intersection 


The answer is centered on vector addition.
Currently, you can tell whether the point satisfies ( p = s * a + t * b ), with s and t in [0,1]. That corresponds to a parallelogram, because if s = t = 1, then p is at the "far end" of the parallelogram.
Consider the "diagonal" between s = 1, t = 0 (that is, p = a) and s = 0, t = 1 (p = b). If you have a p somewhere on that line, what do you know about the values of s and t?
Once you know that, can you determine how to test s and t to decide whether p is inside the triangle defined by a, b, and that diagonal? 





Raknarg

Posted: Mon Jun 17, 2013 7:24 pm Post subject: RE:Triangle and Point Intersection 


Already figured it out thanks, just added an extra if:
if s + t < 1 then ... 





silvestersloon

Posted: Mon Dec 09, 2013 6:39 am Post subject: RE:Triangle and Point Intersection 


I admire what you have done here. I like the part where you say you are doing this to give back but I would assume by all the comments that this is working for you as well. 





Raknarg

Posted: Mon Dec 09, 2013 10:46 am Post subject: RE:Triangle and Point Intersection 


Thanks I never mind giving back, I just didnt know this was a point of interest. I worked this out a while ago. 





Tony

Posted: Mon Dec 09, 2013 2:38 pm Post subject: RE:Triangle and Point Intersection 


Raknarg, I'm sorry to inform you that silvestersloon was a spam account I think the idea is to build up a user account with many posts first, and edit in the spam links at a later point in time. 
Tony's programming blog. DWITE  a programming contest. 




Raknarg

Posted: Mon Dec 09, 2013 2:44 pm Post subject: RE:Triangle and Point Intersection 


It's ok, I don't need recognition
</3 






