I have a function that takes a point, and given its velocity, and acceleration, calculates the time(s) for the point to collide with the line:

def ParabolaLineCollision(pos, vel, acc, line):
    """A pure function that returns all intersections."""

I have another function that wants to calculate the smallest intersection time between two entities, where an entity has a velocity/acceleration, and a list of vertices.

The algorithm of entity_intersection creates lines for each objects' list of vertices, and then calls ParabolaLineCollision on each point of each object, with each line of the other object. My current algorithm runs slowly, and thus I would like to be able to parallelize the algorithm.

My problem is that entity_intersections is a bit hard to read, and I think that there may be some code duplication, which might possibly be eliminated. Here's the algorithm, and

class Entity
    # ...

    def lines(self):
        Get a list of lines that connect self.points.

        If self.enclosed, then the last point will connect the first point.
        # type(self.enclosed) == bool

        # # I included this, as this may be where there is logic duplication with entity_intersections.
        # # It's also not very readable.

        return [(self.points[i-1], self.points[i]) for i in range((1-int(self.enclosed)), len(self.points))]

    # ...

def entity_intersections(entity, other):
    Find all intersection times between two entities.

    type(entity) == type(other) == Entity
    # Find relative velocity/acceleration
    a12 = entity.acceleration - other.acceleration
    a21 = other.acceleration - entity.acceleration
    v12 = entity.velocity - other.velocity
    v21 = other.velocity - entity.velocity

    entity_points, other_points = entity.points, other.points
    entity_lines, other_lines = entity.lines, other.lines

    results = []

    # Get all intersections between each object's point and the other object's line
    for point in entity_points:
        for line in other_lines:
            results.append((point, v12, a12, line))
    for point in other_points:
        for line in entity_lines:
            results.append((point, v21, a21, line))

    # Return results of ParabolaLineCollision with each list of arguments in results
    # Pseudo-code to achieve this (I haven't done the parallizing yet):
    # return min(map(ParabolaLineCollision, results))
  • \$\begingroup\$ How does your entity behave? Instead of calling "ParabolaLineCollision on each point of each object" which is very expensive, couldn't you just track the two mass center trajectory and check for an overlapping of the shapes of the two entities? \$\endgroup\$
    – Rik Poggi
    Apr 6, 2012 at 10:58
  • \$\begingroup\$ This is how I check the overlapping shapes, as this is the shapes of the two entities. I don't have a mass center trajectory. In addition, this is A Priori collision, and this is only done whenever an object's trajectory changes. \$\endgroup\$ Apr 6, 2012 at 16:56
  • \$\begingroup\$ There's a particular reason for not having one? It should really speed things up. I don't understand what it has to do if the computation is a priori or not, it's still a computation. \$\endgroup\$
    – Rik Poggi
    Apr 6, 2012 at 17:16
  • \$\begingroup\$ I'm not sure what you're indicating as a way of doing collision. I don't have one because I don't need one. I say it's A priori to indicate that this doesn't happen every frame. I need to know when the shapes are going to hit each other, so that I can resolve the collision as it occurs (instead of after). I define my objects' shapes as a set of consecutive points. At the time that two consecutive points of an object become collinear with any other objects' point, there is a collision. \$\endgroup\$ Apr 6, 2012 at 17:44
  • \$\begingroup\$ I'm indicating a way of just let those entity be, I'd build some kind of (repulsive) interaction between them to trigger when they'll get near enough. To keep the picture in sync with the physics underneath use different refresh rate. You wouldn't need to pre-compute anything and just let the physics flow. This way you should save you a "very CPU-intensive function" :) \$\endgroup\$
    – Rik Poggi
    Apr 6, 2012 at 18:39

1 Answer 1


Not a lot of changes, but maybe a bit more legible.

a12 = entity.acceleration - other.acceleration
a21 = -a12
v12 = entity.velocity - other.velocity
v21 = -v12

result  = [ (p, v12, a12, l) for l in other.lines for p in entity.points ] +
          [ (p, v21, a21, l) for l in entity.lines for p in other.points ]

Obviously you could inline the v21 and a21 variables, but it's actually somewhat descriptive of what they represent to use those names.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.