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


#21

Do you think that this could be used for sensing line of sight?


#22

I have a feeling I didn’t explain my method very well, so I’ll expand on it once I get back my room. But, once you’ve done your transformation, and have a vertex at (0,0), if your other two defining vertices are (x1,y1) and (x2,y2) and your point is (p1,p2), then the numbers you have to check as less than 1 would be:

image

This should edge out the cross product in terms of operations. But I could just be making a huge mistake xD


#23

No mistake & a very elegant solution! I love that the communicative nature of vectors makes the solution so simple.

So… our rule is:

When u>=0 and u<=1 and v>=0 and v<=1

Or to be more efficient, because u & v have to be “spelled out” each time, we could use:

When Abs(u-0.5)<=0.5 and Abs(v-0.5)<=0.5

So, remembering that we also can’t transform the coordinate system prior to the When rule calculation, each variable in u & v is of the form (a-b). Therefore u & v each require 15 operations. And the total for the second When rule is 37 operations.

Now the When rule using cross product (expressed with point P at the origin) is:

When
x1y2 - y1x2 >= 0
and
x2y3 - y2x3 >= 0
and
x3y4 - y3x4 >= 0
and
x4y1 - y4x1 >= 0

So the total operations (also considering each variable is of the form a-b) for the cross product method is 35. And so barely edges out “vector addition”!

Just to note, after I used Wolfram Alpha to simplify the equation for me, the “area comparison” method also was 37 operations. So we have 3 methods that are all of very similar complexity.

This was very interesting. Thank you for your input BAS!


#24

It depends on what exactly you have in mind. Let’s say you have a light source & an obstruction and want to test if a point is “in the shadow” of the obstruction… having only thought briefly about it, I’d say “Yes”.

Using similar triangles, you could test if the point is within the larger triangle AND is not within the smaller triangle…


#25

You could find the area that the triangle (assuming this is a flashlight we are talking about) would be taking up, and then apply it to when you have barriers.

Another crazy idea I had was if you had a text object running back and forth a certain distance at different angles (which would make the triangle) and every time it hit a barrier it would reverse direction until it hit the desired Y Coordinate, change the direction it is facing and repeat.


#26

An idea I just had is that you take the coordinates of the points of the parallelogram and use that to make a slope function for all 4 sides then you would do something like this
_______ side 2
Side 1_______\ side 3
Side 4
If (y=MX+b)<slope
Then
Out of shape
And so on


#27

Ok ignore that^^^^^
Use this
So the normal slope function is y=MX+b
You would take the coordinates of your point and put x as your x of the point, then the m as the slope of the bottom line and b as the y intercept. If the y of your point is less then the answer, it is in. Repeat with the top line with greater then.
Then you would use the equation (y-b)/m=x with the y of your point as y, then greater then and less then accordingly


#28

That’s a really good idea once or if you know the orientation of the parallelogram.

Can you write a single expression to return true/false without using IF statements (that works for any orientation)?


#29

What do you mean by singular? Like one line?


#30

A single expression would be one that you can put here:


#31

Maybe try including something like a hyperbola’s formula in saying point is less than the absolute value of distance from vertex…

(idk might help)


Something like it has to be less than that distance from the vertex


#32

Ah ok let me try that.


#33

Oh I know: If (inside_triangle = 1)
ok I’m sorry don’t flag me

Parallelogram just find the rate of change on the diagonal and do something like:
if (TouchY>Y-(0.5*height)) and (TouchY<Y+(0.5*height)) and (TouchX>X-(8/9*width*(TouchY-Y))) and (TouchX<X+(8/9*width*(TouchY-Y)))


#34

So, my stated solution using cross products was incomplete:

Rather, all the cross products have to all be positive (which is what’s expressed above) or they have to all be negative. In other words, they have to be the same sign.

I can’t think of way to compare the signs without repeating the expressions. If we were only comparing 2 results then, result1 * result2 >= 0 could be used (as two negatives or two positives would result in a positive). But that doesn’t work when we have 3 or 4 results to compare.

That makes the cross product method more “expensive” (has more blocks, which causes Editor lag for long equations) than I originally thought…


[edit]
Just to prove to my myself if was possible to determine if 3 or more results were all the same sign without repeating the result calculation I derived this (for 3 values):

Abs([Round((R1/999999)+0.5) + Round((R2/999999)+0.5) + Round((R3/999999)+0.5)] - 1.5) = 1.5

where R1, R2, R3 are the 3 results (which could be substituted with the cross product calculations) & assuming the result value is less than abs(999999)

But that’s uuuugly.


#35

Don’t knock it if it works! In the programming language I’m making I just implemented regex pattern matching and I use a regular expression to check whether the passed regex is valid regex. The code is a nightmare but I get an overwhelming sense of dread whenever I open that file so I’ve decided to leave it be.

Jokes aside, I know you found a method - but if you’re looking for elegance, a vector a is all the same sign iff it’s equal to |a| or -|a|, so you could find the angle between a and |a| and check if it’s equal to Pi or 0 (Angle(Pi-Angle)=0).

But I think the fact that my solution requires calculating arccos is very telling that I am a math person more than an engineering person xD


#36

Hi BAS, I’m not following your suggestion.

a vector a is all the same sign iff it’s equal to |a| or -|a|

How can a vector equal a scalar? Why would a vector equal it’s magnitude?

find the angle between a and |a|

How can there be an angle between a vector and a scalar?


#37

Ah! Sorry, late night notation. I meant | | in the sense of abs value, not magnitude (I always denote magnitude with || ||), so if a=(x,y,z), |a|=(|x|,|y|,|z|). Sorry about that!


#38

I was helping my friend with his Algebra homework and have seemed to have stumbled on this


Idk maybe I’ll look into it deeper


#39

a =(x,y,z), |a|=(|x|,|y|,|z|)

Ah, now the suggestion makes sense!

find the angle between a and |a| and check if it’s equal to Pi or 0 (Angle(Pi-Angle)=0)

For simplicity couldn’t we also use

If a x |a| = 0

,where x is cross product


#40

I decided to use the “Vector Addition” method as it is conceptually elegant and I now believe requires the fewest operators (therefore causes least editor lag)

Here is a demonstration project:


(@William04GamerA, tagging since you asked about a Hopscotch project)


For reference, here’s When rule used

u = (Py-Ay)(Cx-Bx) + (Px-Ax)(Cy-By) / (Cx-Bx)(By-Ay) - (Bx-Ax)(Cy-By)

v = (Px-Ax)(By-Ay) + (Py-Ay)(Bx-Ax) / (Cx-Bx)(By-Ay) - (Bx-Ax)(Cy-By)

The point P is within the parallelogram ABCD

When u>=0 and u<=1 and v>=0 and v<=1

Or to be more efficient, because u & v would have to be “spelled out” each time, we can use

When Abs(u-0.5)<=0.5 and Abs(v-0.5)<=0.5

And finally the full rule is:

When Abs([(Py-Ay)(Cx-Bx) + (Px-Ax)(Cy-By) / (Cx-Bx)(By-Ay) - (Bx-Ax)(Cy-By)]-0.5)<=0.5 and Abs([(Px-Ax)(By-Ay) + (Py-Ay)(Bx-Ax) / (Cx-Bx)(By-Ay) - (Bx-Ax)(Cy-By)]-0.5)<=0.5