Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 14:34, 17 September 2021
, 2 years agoAdded Common Lisp
m (→{{header|REXX}}: re-instated required parenthesis.) |
(Added Common Lisp) |
||
Line 254:
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)]
Point (5.41429, 14.3492) is within triangle? true</pre>
=={{header|Common Lisp}}==
<lang Lisp>
; There are different algorithms to solve this problem, such as adding areas, adding angles, etc... but these
; solutions are sensitive to rounding errors intrinsic to float operations. We want to avoid these issues, therefore we
; use the following algorithm which only uses multiplication and subtraction: we consider one side of the triangle
; and see on which side of it is the point P located. We can give +1 if it is on the right hand side, -1 for the
; left side, or 0 if it is on the line. If the point is located on the same side relative to all three sides of the triangle
; then the point is inside of it. This has an added advantage that it can be scaled up to other more complicated figures
; (even concave ones, with some minor modifications).
(defun point-inside-triangle (P A B C)
"Is the point P inside the triangle formed by ABC?"
(= (side-of-line P A B)
(side-of-line P B C)
(side-of-line P C A) ))
; This is the version to include those points which are on one of the sides
(defun point-inside-or-on-triangle (P A B C)
"Is the point P inside the triangle formed by ABC or on one of the sides?"
(apply #'= (remove '0 (list (side-of-line P A B) (side-of-line P B C) (side-of-line P C A)))) )
(defun side-of-line (P A B)
"Return +1 if it is on the right side, -1 for the left side, or 0 if it is on the line"
; We use the sign of the determinant of vectors (AB,AM), where M(X,Y) is the query point:
; position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
(sign (- (* (- (car B) (car A))
(- (cdr P) (cdr A)) )
(* (- (cdr B) (cdr A))
(- (car P) (car A)) ))))
(defun sign (x)
(if (plusp x)
1
(if (minusp x)
-1
0 )))
</lang>
{{out}}
<pre>
(point-inside-triangle '(0 . 0) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2))
T
(point-inside-triangle '(0 . 1) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2))
T
(point-inside-triangle '(3 . 1) '(1.5 . 2.4) '(5.1 . -3.1) '(-3.8 . 1.2))
NIL
(point-inside-triangle '(5.414286 . 14.349206) '(0.1 . 0.111111) '(12.5 . 33.333333) '(25.0 . 11.111111))
T
(point-inside-triangle '(5.414286 . 14.349206) '(0.1 . 0.111111) '(12.5 . 33.333333) '(-12.5 . 16.666667))
NIL
</pre>
=={{header|D}}==
| |||