Numerical analysis of contact function - most efficient and easiest way to represent shapes

user_14047249 0
Viewed 67

I'm doing a little assignment, as title suggest it's about numerical analysis of contact function, more specifically i'm looking for the closest distance between two points that are inside two different shapes so that those shapes are making contact (they're tangent).

A little picture for better understanding of the problem. I know its not 100% accurate.

I'm wondering how i can represent different shapes in the best, most uniform way for this algorithm to work at all. Shapes being mostly convex and concave polygons and/or different kinds of curves.

My main idea was to use some kind of spline: B-spline, or NURB, then i could interpolate it and create a polygon.

Then there's a problem with collision detection, for convex sets i'm using Separating Axis Theorem, but what to do with concave polygons and curves, i have no idea.

I'm writing this with C++17 and SFML2, no other third-party libs (for now, if there are any that will help me please link them in your comment).

numeric linear-algebra geometry python c++
1 Answers

Polygon storage: You do what you think is best. Personally, I've seen a lot of collision libraries that include polygon objects for the end-user to mess with, and they're mostly stored as an array of counter-clockwise points: {{x1,y1},{x2,y2}} or {x1,y1,x2,y2}. The collision system is responsible for calculating normal vectors.

I personally like to store them as ccw edges: {{x1,y1,dx1,dy1}, {x2,y2,dx2,dy2}} where x1+dx1 = x2 and y1+dy1 = y2. The normal is just calculated as {-dy, dx}.

For concave polygons and SAT, the solution opted for is to decompose them into a set of convex polygons. There are lots of algo's for this, but polygon triangulation is your best bet, I think. It leaves the simplest shapes and there are several tried-and-true algorithms to accomplish it.

For curves, here's a good answer. Pixel-perfect collisions with a few simple polygons would be performant enough (if your comfortable with it), but decomposing into vertices with a tight resolution isn't a bad option (and it works with SAT!)

Hope I helped :)

user_121358040
Related