-----------------------------------

Raknarg

Mon Jun 17, 2013 1:57 pm


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:


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.


-----------------------------------

DemonWasp

Mon Jun 17, 2013 4:29 pm


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 . 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

Mon Jun 17, 2013 7:24 pm


RE:Triangle and Point Intersection

-----------------------------------

Already figured it out thanks, just added an extra if:

if s + t < 1 then ...


-----------------------------------

silvestersloon

Mon Dec 09, 2013 6:39 am


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

Mon Dec 09, 2013 10:46 am


RE:Triangle and Point Intersection

-----------------------------------

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


-----------------------------------

Tony

Mon Dec 09, 2013 2:38 pm


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.


-----------------------------------

Raknarg

Mon Dec 09, 2013 2:44 pm


RE:Triangle and Point Intersection

-----------------------------------

It's ok, I don't need recognition