Challenge: How to determine if a point is within a scalene triangle or parallelogram (with a single logical expression)


#1

Hi Hops. I’ve been working on a way to replace the When (self) is Tapped/Pressed in my Rubik’s Cube project with a single conditional Rule (since the native rule is flawed). The project uses triangles to render each face, but astute observers will also recognize that each face is also a parallelogram. I’ll resist the temptation to mention anything more on how I solved the problem as I thought this might make an interesting challenge for mathematically minded forumers (and perhaps a method with a shorter equation will be shown). So here it is:

Part 1

Given:

  • A point (x, y)
  • A triangle with vertices {(x1,y1),(x2,y2),(x3,y3)}

Find:

  • A single logical expression that returns TRUE when the point is inside the triangle

Part 2

Given:

  • A point (x, y)
  • A parallelogram with vertices {(x1,y1),(x2,y2),(x3,y3),(x4,y4)}
  • Vertices 1 & 3 are diagonally across
  • Vertices 2 & 4 are diagonally across

Find:

  • A single logical expression that returns TRUE when the point is inside the parallelogram

Bonus Credit

Make a Hopscotch project(s) to demonstrate your Rule



The solution to these problems can also be used for collision detection if the object doesn’t fit nicely in a square or circle!



[Edit]
I’ll update this if a shorter solution is found. So far the shortest (that is, it has the fewest operations or Hopscotch code blocks) is:

Cross product direction

Cross product can be used to determine the direction of the normal vector.

Consider PA x PB (that’s PA cross PB) for a point P inside the parallelogram:

image

Using your right hand & following the arrow, curl your fingers from A to B. Your thumb will point outward indicating a positive direction to the normal vector

Now consider PA x PB (PA cross PB) for a point P outside the parallelogram:

image

Again, using your right hand & following the arrow, curl your fingers from A to B. Your thumb will point inward indicating a negative direction to the normal vector.

For a parallelogram, if all four cross products are positive then the point P is inside the triangle.

When
(Ax-Px)(By-Py) - (Ay-Py)(Bx-Px) >= 0
and
(Bx-Px)(Cy-Py) - (By-Py)(Cx-Px) >= 0
and
(Cx-Px)(Dy-Py) - (Cy-Py)(Dx-Px) >= 0
and
(Dx-Px)(Ay-Py) - (Dy-Py)(Ax-Px) >= 0

For a triangle, there’s only three cross products to check to determine if the point P is inside the triangle.

When
(Ax-Px)(By-Py) - (Ay-Py)(Bx-Px) >= 0
and
(Bx-Px)(Cy-Py) - (By-Py)(Cx-Px) >= 0
and
(Cx-Px)(Ay-Py) - (Cy-Py)(Ax-Px) >= 0


#2

Do we need to choose our own points for x1, y1, x2, y2, x3, y3, x4, and y4 to make a parallelogram or scalene triangle?


#3

Yep. But the conditional rule should work for any values.


#4

Write some inequalities to find if the point is more than the Lowest X Coordinate and less than the Highest X Coordinate. If either of those statements are false than the point is not inside the parallelogram horizontally. Do the same for the Y coordinates. If all your inequalities prove true than you will find out if the point is inside the parallelogram. Keep in mind this isn’t 100% accurate for a shape that is solely a parallelogram. If it’s a Rectangle or a Square this will work 100% of the time I believe.

Point X (X1,Y1)

Parallelogram Vertices
A(x1,y1) B(x2,y2) C(x3,y3) D(x4,y4)

image

All outputs need to be true for the point to be inside the parallelogram

Conditionals
If Y1>y1 and y4 -> Output True1
If True1 then if Y1<y2 and y3 -> Output True2
If True2 then if X1>x1 -> Output True3
If and only if True3 then if X1>x2 -> Output True 4
If True3 then if X1<x2 -> Output Maybe1
If and only if True4 then if X1<x3 -> Output Maybe2
If True4 then if X1<x4 -> Output True5

If Maybe1 or Maybe 2 then the point might be in the parallelogram
If True5 than the point is in the parallelogram

The Maybe parameters are just so this system can’t technicslly get it wrong, but a point can be in between point A and B horizontally and get through the system otherwise.

Also this could all be wrong


#5

Ah, I like what you’re thinking. A simplification to find if the point is within the internal square/rectangle. That might very well be good enough for some applications.

But there also might be variations that result in a relatively small “true area”, like this:


(Please forgive the horribly crude sketch)

Also, what if the AD & BC are not horizontal? What if the parallelogram is rotated or mirrored?


#6

Yeah…O didn’t think it through all the way…


#7

This was super fun to solve. My equation didn’t end up being so nice, but I feel like there’s some method behind the madness that justifies it. I won’t post my solution because I want other people to experience the same exploration that I did, but if you want a hint:

If your point is inside the parallelogram, think about “splitting” the area of the parallelogram around the point. What happens once the point moves outside?

Probably not the best solution either, and I’m sure there are tons. But I like mine :slight_smile:


#8

@BuildASnowman Based on your hint, I’m fairly certain I know what your solution is. And it is a different solution than I used. I do like the elegance of your method and I’ll have to consider which is more computationally efficient. (The biggest reason for caring in the context of Hopscotch is that equations get translated into an exceptionally large amount of json data. The equation I used is so long, the app has become very unresponsive due to the latency of saving the project data as changes are being made)

I think you’ll like the method I used as well, as I found it to be very unusual and intellectually stimulating.

I suppose a hint for my solution would be:

What if the vertices had mass (i.e., gravity) that correlated to the point’s location. How would those mass parameters be different if the point were outside the triangle?


I suggest we give it a few days and then explain our solutions


#9

I wish that I could get the option to learn more advanced math in school so that I also could think about these kinds of interesting mathematical problems, and also help people.


#10

@William04GamerA
Advanced (which is of course a relative term) math isn’t necessarily required. Let’s consider the method BAS hinted at. Clever recognition of geometric properties would lead, at least, to a conceptual solution. Perhaps some pictures would help.

Consider these:

image

verses

image

With the red dot being the point we want to test.


@BuildASnowman, I don’t think I’m giving too much away… (and correct me if I’m mistaken regarding the method you used)


#11

I don’t know if this is what you are hinting at (and to be honest this is probably a super inaccurate way of doing this) but could you possibly create an equation that measures the distance of the lines and then finds out if the point is inside the parallelogram or not? I don’t know what it would be but it would be interesting, just a lot of conditionals.


#12

I understand what you mean. What I’m missing is the way to look at mathematical problems in that way.


#13

@HopscotchRemixer
Interesting thought. I was going a different direction(s), but that doesn’t mean you’re wrong. What might the logic be, using the lengths of the lines, to determine if the point is inside or outside?


#14

Maybe if the distance of the lines are less than a certain distance for all of them then that means the point is inside the shape…however Icdont know specifically what the distance would be in proportion to the size of the shape.


#15

Ok, it’s been a couple days so I’ll comment on the solutions I’ve found. @HopscotchRemixer @William04GamerA

Area comparison

When the point P is inside the parallelogram, the sum of the areas of the 4 subdivided triangles = the area of the parallelogram

One of the subdivided triangles APD is shown here:
image

When the point P is outside the parallelogram, the sum of the area of the 4 subdivided triangles is > the area of the parallelogram.

For comparison triangle APD is again shown here:
image

Sum of angles (dot product)

Consider the interior angles created by dividing the parallelogram. Shown is ∠APB:

image

When the point P is inside the parallelogram, the sum of the subdivided interior angles = 360

∠APB is shown again with point P outside the parallelogram:

image

Now the sum of the 4 interior angles of the subdivided triangles < 360

The angles can be calculated using the algebraic and geometric definitions of dot product

Cross product direction

Cross product can be used to determine the direction of the normal vector.

Consider PA x PB (that’s PA cross PB) for a point P inside the parallelogram:

image

Using your right hand & following the arrow, curl your fingers from A to B. Your thumb will point outward indicating a positive direction to the normal vector

Now consider PA x PB (PA cross PB) for a point P outside the parallelogram:

image

Again, using your right hand & following the arrow, curl your fingers from A to B. Your thumb will point inward indicating a negative direction to the normal vector.

For a parallelogram, if all four cross products are positive then the point P is inside the triangle.

When
(Ax-Px)(By-Py) - (Ay-Py)(Bx-Px) >= 0
and
(Bx-Px)(Cy-Py) - (By-Py)(Cx-Px) >= 0
and
(Cx-Px)(Dy-Py) - (Cy-Py)(Dx-Px) >= 0
and
(Dx-Px)(Ay-Py) - (Dy-Py)(Ax-Px) >= 0

For a triangle, there’s only three cross products to check to determine if the point P is inside the triangle.

When
(Ax-Px)(By-Py) - (Ay-Py)(Bx-Px) >= 0
and
(Bx-Px)(Cy-Py) - (By-Py)(Cx-Px) >= 0
and
(Cx-Px)(Ay-Py) - (Cy-Py)(Ax-Px) >= 0
Barycentric coordinates

This method is really interesting but is probably the most difficult to understand.

Barycentric coordinates can describe the location of a point relative to a triangle’s vertices by treating the vertices as unequal masses (i.e., unequal gravitational forces)

For a triangle, the point P is inside when
λ1 >= 0
λ2 >= 0
λ1 + λ2 <= 1

I first used this method, but it is not the most computationally efficient

Number of vertices when 'wrapped'

You can also “wrap” the parallelogram and point P, then count the number of vertices required to do so.

Here the green polygon (with 5 vertices) wraps the parallelogram and external point P:

image

Now if point P is internal to the parallelogram, the wrapped green polygon will only have 4 vertices:

image

This method is described here

The area comparison method is probably the easiest to understand, while the cross product method is the most computationally efficient (with the number of required math, logical, and boolean Hopscotch blocks as the criteria) of the methods listed.

I don’t have my notes with me at the moment but I believe the cross product method requires 36 operations. I’ll post again tomorrow with the specific formula.

@BuildASnowman Did I cover the method you had used? Are you able to find a more “efficient” solution than using cross product?


#16

Interesting! Can you somehow apply this in Hopscotch? If you made a project (because it’s your method), it would be awesome!


#17

The application in Hopscotch is replacing When Tapped/Pressed or replacing When Bumps for collision detection (for triangular or parallelogram shaped areas) with higher performance code.

I will be using this in an update to my Rubik’s Cube project & I have made a project to demonstrate the calculation of the Barycentric method, but I haven’t published it yet. Though I think I’ll change it to demonstrate the cross product method instead as the equation is shorter. I’m hoping BAS will be able to chime in again and confirm if there’s a even shorter method or not.


#18

You indeed got the method I used, and covered most everything I else I thought of and more. I’m currently at a conference so I don’t really have any time to sit down and do some calculations but I definitely will when I have the time! This is such a fun problem.

Off the top of my head, taking and xMin, xMax and yMin and yMax and creating a “bounding box” to first rule out points should be super fast and rule out most cases, such that most of the time you don’t even need to run one of these algorithms.

Apologies for the short response, once I have the time I’ll expand on it!


#19

P.S. I have an inkling there is a faster method, assuming a vertex of your parallelogram is at the origin (which you can just do by applying a transformation to your parallelogram/point), then all points in the polygon are of the form p=xa+yb where a and b are the two other vertices connected to the one at the origin and 0 < x,y < 1, so we can set up an equation for x and y based on a and b and just check if x and y are both less than 1.

Again, sorry if you’ve already hashed through this method - I’m only here because I’m trying to distract myself about to stand up and present, so I haven’t read through everything thoroughly yet :stuck_out_tongue:

EDIT: And speaking of “more general contexts”, this method, if I haven’t made some mistake, should also generalize to higher dimensions through Gaussian Elimination.


#20

Agreed, in more general contexts. Though keep in mind that, for use in Hopscotch, the desire is to have a single logical expression to put in a “When” rule, rather than an algorithm.