Algorithm for collision - any library in Python or other languages - or will someone do it?

Question

Hi,

I read about an algorithm that checkes a collision between lets say two triangles a and b.
The idea looks easy on the first glance:

add every point of a to every point if b

so if
a = (1,2),(3,3),(3,0) and
b = (0,0),(1,1),(2,2)

we have points (1,2),(3,3),(3,0),(2,3),(4,4),(4,0),(3,4),(5,5),(5,0)

now create convex hull of this 9 points and check if (0,0) is in it.
Although there is an algorithm as pseudo code

https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

I still have the last point to solve.

Dont we have libraries for that?

Answer 1

You can find whether a given point lies inside the convex hull by checking whether it lies at the same side of each segment that forms the convex hull.
If you have the hull in counterclockwise order, the O[0,0] point should be in counterclockwise direction from each segment AB on the hull, that is, the vector product
AO x AB
should be negative for all segments AB
If it is in clockwise order, it should be always positive
Is this what you are asking for?

Answer 2

to be honest:
Its an assignment for runaways.😇😇😇😇
so if you like... write a collisiin detector.

Answer 3

@michal thats true.. i remember wrong.. it was similiar. not add but substract?

Answer 4

I think the first part is incorrect. Suppose that both triangles are in the first quadrant (both coordinates positive). Then all nine points have positive coordinate and their convex hull doesn't contain 0,0

Answer 5

The simplest algorithm to check collision seems to be:
for each pair of edges, one edge from the first triangle, second frpm the other, find if they intersect. If any pair intersects, there is a collision.
Otherwise not, but it still can be the case that one triangle is whole within the other.

Answer 6

michal I think she is asking whether there are libraries for all this work or not. Not asking the way how it can be solved🤔

Answer 7

One thing I can't understand:
Check if (0,0) is in (1,2,),(3,3),…,(5,0) .
Why need for two triangle a and b? How there collision is related to finding (0,0) thing? (I haven't opened wiki link yet)
Initially I thought I am so much beginner for this(still am). So, I didn't thought to solve this one. But then I think I could have solved it hypothetically though I may not be able to implement code and I got to "collision between two triangles" not any convex hull stuff. Then I surfed 5-6 stack overflow questions and found great answers and codes.
Main thing to cheer for me, my idea was probably the fastest way to check😎

Edit: now I opened wiki links. I think I missed the word 'lets say'😁
so, this is well beyond my range.

Answer 8

I have not really read any of the other answers, but here's mine :
I highly recommend using tkinter to make graphical programs on python. There is a special keyword object.x/y which can be used to detect collision.