Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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.

DemonWasp

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

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

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 7 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: