Find if a point is within a triangle: Difference between revisions
Content added Content deleted
Line 58: | Line 58: | ||
</lang>{{out}} |
</lang>{{out}} |
||
<pre> |
<pre> |
||
Point |
Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2)) |
||
</pre> |
</pre> |
Revision as of 22:38, 11 November 2020
Find if a point is within a triangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Find if a point is within a triangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Find if a point is within a triangle.
- Task
- Assume points are on a plane defined by (x, y) ewal number coordinates.
- Given a point P(x, y) and a triangle formed by points A, B, and C, determine if P is within triangle ABC.
- You may use any algorithm.
- Bonus: explain why the algorithm you chose works.
- Related tasks
- Also see
Python
<lang python> """ find if point is in a triangle """
from sympy.geometry import Point, Triangle
def sign(pt1, pt2, pt3):
""" which side of plane cut by line (pt2, pt3) is pt1 on? """ return (pt1.x - pt3.x) * (pt2.y - pt3.y) - (pt2.x - pt3.x) * (pt1.y - pt3.y)
def iswithin(point, pt1, pt2, pt3):
""" Determine if point is within triangle formed by points p1, p2, p3. If so, the point will be on the same side of each of the half planes defined by vectors p1p2, p2p3, and p3p1. zval is positive if outside, negative if inside such a plane. All should be positive or all negative if point is within the triangle. """ zval1 = sign(point, pt1, pt2) zval2 = sign(point, pt2, pt3) zval3 = sign(point, pt3, pt1) notanyneg = zval1 >= 0 and zval2 >= 0 and zval3 >= 0 notanypos = zval1 <= 0 and zval2 <= 0 and zval3 <= 0 return notanyneg or notanypos
if __name__ == "__main__":
POINTS = [Point(0, 0)] TRI = Triangle(Point(1.5, 2.4), Point(5.1, -3.1), Point(-3.8, 0.5)) for pnt in POINTS: a, b, c = TRI.vertices isornot = "is" if iswithin(pnt, a, b, c) else "is not" print("Point", pnt, isornot, "within the triangle", TRI)
</lang>
- Output:
Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2))