CODEWITHSUNDEEP
vectorgeometry2dlinear-algebratrigonometry
Mieko
Mieko

Reputation: 103

Determining if a list of points fit a "formation"?

I have, as input, an arbitrary "formation", which is a list of rectangles, F:

Formation

And as another input, an unordered list of 2D points, P:

Input

In this example, I consider P to match the formation F, because if P were to be rotated 45° counter-clockwise, each rectangle in F will be satisfied by containing a point. It would also be considered a match if there were an extraneous point in P which did not fall into a rectangle.

Neither the formation, nor point inputs, have any particular origin, and the scale between the two are not required to be the same, e.g., the formation could describe an area of a kilometer, and the input points could describe an area of a centimeter. And lastly, I need to know which point ended up in which node in the formation.

I'm trying to develop a general-purpose algorithm that satisfies all of these constraints. It will be executed millions of times per second against a large database of location information, so I'm trying to "fail out" as soon as I can.

I've considered taking the angles between all points in both inputs and comparing them, or calculating and comparing hulls, but every approach seems to fall apart with one of the constraints.

Points in the formation could also easily be represented as circles with an x,y origin and tolerance radius, and that seems to simplify the approaches I've tried so far. I'd appreciate any solid plan-of-attack or A-Ha! insights.

Upvotes: 2

Views: 146

Answers (2)

ryanm
ryanm

Reputation: 3009

I've had another thought - using polar coordinates this time.

The description was getting complex/ambiguous, so here is some code that hopefully illustrates the idea.

The gist is to express the formations and points in terms of polar coordinates, with the origin in the center of the formation/point set. It then becomes a lot easier to find the rotation and scaling factors of the transform between points and formations. The translation component is trivially found by comparing the average of the point set and of the formation zone set.

Note that this approach will treat your formation zones not as squares or circles, but as sections of circle segments. Hopefully this is a fudge that you can live with.

It will also not return the exact scaling and rotation terms of a valid mapping transform. It will give you a mapping between formation zones and points, and a good approximation of the final rotation and scaling factors. This approximation could be very quickly refined into a valid solution via a simple relaxation scheme. It will also quickly disregard invalid point sets.

Upvotes: 2

ryanm
ryanm

Reputation: 3009

One approach would be to express the point sets and formations in relative coordinate systems.

For each point set and formation:

  1. Identify the most mutually-distant pair of points, call them A and B
  2. Identify the point farthest from the line through A and B, call it C. Ensure that C is on the left of the line AB - you may need to swap A and B to make this so.
  3. Express the rest of the points in terms of A, B and C. This is a simple matter of finding the closest point D on the line through AB for each point, and scaling such that all distances are in terms of the distance between A and B. The distance from A to D is your relative x coordinate, and the distance from D to the point is the y.

For example, if you find that A and B are ten units apart, and that C is 5 units distant from the midpoint of AB, then the relative coordinates would be: A: (0,0) B: (1,0) C: (0.5,0.5)

You can then compare the point sets and formations independently of the global coordinate system. Note that the distance tolerances to find a match also have to be scaled in terms of AB.

I can easily imagine problem formations for this approach, where the choices of A, B and C are difficult to make unambiguously, but it's a start.

Upvotes: 1

Related Questions