Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Triangle and Point Intersection
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Raknarg




PostPosted: 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
Sponsor
sponsor
DemonWasp




PostPosted: 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




PostPosted: 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




PostPosted: 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




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

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




PostPosted: 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 Sad 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Raknarg




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

It's ok, I don't need recognition



</3
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 7 Posts ]
Jump to:   


Style:  
Search: