search

noinia / hgeometry

HGeometry is a library for computing with geometric objects in Haskell. It defines basic geometric types and primitives, and it implements some geometric data structures and algorithms.
122 stars 40 forks source link

Collision detection #12

Open egormalyutin opened 6 years ago

egormalyutin commented 6 years ago

Can you add some collision detection algorithms (something like https://github.com/vrld/HC)?

noinia commented 6 years ago

Do you just want to test if, say two polygons, intersect? Or do you want something along the lines of "given two polygons and two movement vectors, find the time at which they intersect"? The former should be easy enough using Algorithms.Geometry.LineSegmentIntersection, the latter is more complicated.

egormalyutin commented 6 years ago 
just want to test if, say two polygons, intersect

Something like https://hackage.haskell.org/package/gjk.

BebeSparkelSparkel commented 5 years ago

I'm interested in this as well. It seems like the only reliable way to do this is to triangulate the polygon and then check for triangle intersections.

noinia commented 5 years ago

It is unnecessary to split the polygons into triangles. Using the algorithms currently in the package it should be fairly easy to test if two arbitrary polygons intersect in O(n log n) time. (where n is the max size of the polygons). The idea is: Two polygons R and B intersect if and only if

The first condition is easy to check: just pick a vertex from r, test if it occurs in B with pointInPolygon and vice versa. Otherwise the boundary intersects. We can use Algorithms.LineSegmentIntersection.BentleyOtmann for that. (I think the current implementation also reports the vertices of the polygons as intersections, so maybe one should check if the points outputted are vertices).

Of course if the input polygons are convex it is actually possible to test if they intersect in O(log n) time. But that is a bit more complicated. I would like to implement that at some point, but I won't make any promisses ;).

The gjk method suggested seems to also support testing intersections of higher dimensional convex polyhedra. That is kind of nice. Maybe I'll look at that some time. I'm certainly not against adding it to the package, so if anyone feels like implementing that algorithm I'm certainly open to adding it.