Computer Science Canada

Triangle and Point Intersection
Author:  Raknarg [ 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.
Author:  DemonWasp [ 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?
Author:  Raknarg [ 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 ...
Author:  silvestersloon [ 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.
Author:  Raknarg [ 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.
Author:  Tony [ 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.
Author:  Raknarg [ Mon Dec 09, 2013 2:44 pm ]
Post subject:  RE:Triangle and Point Intersection
It's ok, I don't need recognition



</3

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy