• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# help computing positions of points

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

12 replies to this topic

### #1kidman171  Members

Posted 10 February 2014 - 07:14 PM

I've been trying to figure out a solution for this math problem. It might be simple, it might be impossible. I don't know because I am still very inexperienced in this domain.

I will be referring to this drawing:

The Problem:
This drawing depicts two rectangles lying on the x-z plane. Think of it like you are looking at them top-down (down the -y axis). The black points (H, I, and J) are given as input. The width of the rectangle is always 4. I need to compute the positions of each green point (A through G).

My Partial Solution:
Computing points D through G is easy:
vec3 forward = normalize(I-J); // direction from J to I
vec3 right = cross(forward, vec3(0,1,0)); // direction from F to G
G = J + (right * 2); // 2 = width/2
F = J - (right * 2);

I can use the same formula to compute D and E.

Where I Need Help:

I don't know how to compute A, B or C!
Any help or advice is greatly appreciated!

### #2ferrous  Members

Posted 10 February 2014 - 07:23 PM

Unless you know the rotation of the rectangle containing the point H, I don't think you can solve it.  Or if you had the point opposite of H, the midpoint between D & C, you could solve it, because you could then figure out the rotation from there.

### #3kidman171  Members

Posted 10 February 2014 - 08:25 PM

Unless you know the rotation of the rectangle containing the point H, I don't think you can solve it.  Or if you had the point opposite of H, the midpoint between D & C, you could solve it, because you could then figure out the rotation from there.

I thought it might not be possible but I needed another set of eyes to confirm. Thanks for taking the time to respond.

### #4SeanMiddleditch  Members

Posted 10 February 2014 - 08:57 PM

Consider the point K that is the midpoint of DC. HK is a line parallel to BD and AC and perpendicular to DC.

Think of D as being the center of a circle with radius 2. K lies on this circle and is such that HK is a tangent to the circle. Also, lies on the line DC. There's lots of information online about finding tangent lines that pass through a circle and an external point. Pick the tangent line that also intersects the midpoint of DC.

One you find that tangent line, you can trivially find the normal of it along DC. Normalize and scale by 4. That's the location of C. Use this same normal scaled by 2 and -2 relative to H to find A and B.

Game Developer, C++ Geek, Dragon Slayer - http://seanmiddleditch.com

C++ SG14 "Games & Low Latency" - Co-chair - public forums

Wargaming Seattle - Lead Server Engineer - We're hiring!

### #5ferrous  Members

Posted 10 February 2014 - 09:11 PM

Consider the point K that is the midpoint of DC. HK is a line parallel to BD and AC and perpendicular to DC.

Think of D as being the center of a circle with radius 2. K lies on this circle and is such that HK is a tangent to the circle. Also, lies on the line DC. There's lots of information online about finding tangent lines that pass through a circle and an external point. Pick the tangent line that also intersects the midpoint of DC.

One you find that tangent line, you can trivially find the normal of it along DC. Normalize and scale by 4. That's the location of C. Use this same normal scaled by 2 and -2 relative to H to find A and B.

I'm not sure I follow, it sounds like you're using DC (which is undefined, as he doesn't have C) to find C.  Am I misinterpreting?

### #6Nypyren  Members

Posted 10 February 2014 - 09:27 PM

One alternative I can think of:

- Consider D to be a hinge.
- Place a new rect A'B'C'D' and point H' directly adjacent to DEFG and treat this as being a rotated version of ABCD.
- You now know the positions of both H' and H. Calculate the angle formed between them using D as the common vertex.
- Use that angle to rotate points A' through C' about D, back to their expected positions.

You could probably do this entirely with matrices and never actually measure an angle (I suspect), but I'm not good enough with linear algebra to verify that.

Edited by Nypyren, 10 February 2014 - 11:19 PM.

### #7kidman171  Members

Posted 10 February 2014 - 10:18 PM

Consider the point K that is the midpoint of DC. HK is a line parallel to BD and AC and perpendicular to DC.

Think of D as being the center of a circle with radius 2. K lies on this circle and is such that HK is a tangent to the circle. Also, lies on the line DC. There's lots of information online about finding tangent lines that pass through a circle and an external point. Pick the tangent line that also intersects the midpoint of DC.

One you find that tangent line, you can trivially find the normal of it along DC. Normalize and scale by 4. That's the location of C. Use this same normal scaled by 2 and -2 relative to H to find A and B.

I understand exactly what you mean. I thought of D being the center of a circle with radius 2 earlier but I have never worked with tangents before so my thought train ended there. I will try to work out a solution with this tomorrow, it looks like a sound solution. Thanks so much!

### #8kidman171  Members

Posted 10 February 2014 - 10:21 PM

One alternative I can think of:

- Consider D to be a hinge.
- Place a new rect A'B'C'D' and point H' directly adjacent to DEFG and treat this as being a rotated version of ABCD.
- You now know the positions of both H' and H. Calculate the angle formed between them using D as the common vertex.
- Use that angle to rotate points A' through C' about D, back to their expected positions.

You could probably do this entirely with matrices and never actually measure an angle (I suspect), but I'm not good enough with linear algebra to verify that.

Not sure I entirely follow. I am going to try to implement SeanMiddleditch's solution tomorrow. Thanks for your response!

### #9Nypyren  Members

Posted 10 February 2014 - 11:19 PM

Not sure I entirely follow. I am going to try to implement SeanMiddleditch's solution tomorrow. Thanks for your response!

Sorry. I edited my post with a picture. I only have mspaint so apologies for the low quality.

### #10Nypyren  Members

Posted 10 February 2014 - 11:27 PM

Hmm. I just realized my technique only works if the problem guarantees the two rectangles will also have the same length, which your original post didn't specify. Disregard my technique if the rectangles can be different lengths.

Edited by Nypyren, 10 February 2014 - 11:28 PM.

### #11SeanMiddleditch  Members

Posted 11 February 2014 - 01:20 AM

I'm not sure I follow, it sounds like you're using DC (which is undefined, as he doesn't have C) to find C.  Am I misinterpreting?

Oops, I did make that assumption, though only for a minor portion of the solution. The trick is that there will be exactly two tangent lines from H onto the circle at D (unless H is on that circle, in which case you get one tangent with a different meaning; you'd be working with fixed-distance points on the circle instead of tangent lines at that point but otherwise the solution is the same, I think). You just need to select the right line to give you the desired K (midpoint of DC). Assuming you have some idea of the topology you're going for (as in the picture), you could filter out the tangent in one of several ways.

One way to do the filtering would be to take candidate vector H->K with the largest possible dot product result with the vector G->D so it'll find the tangent on the side of the circle least likely to be intersecting DEFG. Another way would be to pick the tangent that does not intersect FD. The correct criteria is going to depend on what you plan to generalize out of the given example.

In any event, the answer lies in that circle at point D with radius 2 and tangent lines. Find the tangents, select the one you want to keep, that gives you K, from that find C, and then finding A and B should be trivial.

Game Developer, C++ Geek, Dragon Slayer - http://seanmiddleditch.com

C++ SG14 "Games & Low Latency" - Co-chair - public forums

Wargaming Seattle - Lead Server Engineer - We're hiring!

### #12kidman171  Members

Posted 11 February 2014 - 04:57 AM

@Nypyren - Ah I see now. The picture clarifies what you mean. That sounds like it would work as well.

@SeanMiddleditch - Good notes I will keep this in mind.

### #13kidman171  Members

Posted 11 February 2014 - 07:14 PM

SeanMiddleditch,

Your solution works perfectly. Thanks so much!

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.