Timeline for 2 closest points between 2 rectangles
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2014 at 22:11 | comment | added | Konrad Morawski |
@shoham the standard way to calculate distance between two points is to use Pythagorean theorem of course, but when you have to compare two distances (say A-B and A-C), you can do a quick check because if |Ax - Bx| > |Ax - Cx| and |Ay - By| > |Ay - Cy| then you're 100% guaranteed that A and B are further away than A and C and you don't need to calculate square roots to verify that (square roots are many times more expensive computationally than simple arithmetics!). This by itself would optimize your calculations by a few times.
|
|
| Jan 19, 2014 at 13:15 | comment | added | user8709 | @shoham - or you're focussing on the wrong element of a larger problem, perhaps. If you're concerned about the performance, presumably you'll be doing it a lot - meaning there's a larger problem that might have some exploitable structure to reduce how much you do it. Or maybe within that larger problem there's something to gain by building a data structure with all the rectangles. | |
| Jan 19, 2014 at 13:13 | vote | accept | shoham | ||
| Jan 19, 2014 at 13:12 | comment | added | shoham | I understand, I guess I'll have to stick with the brute force solution. Thanks very much. | |
| Jan 19, 2014 at 13:09 | comment | added | user8709 | @shoham - one quick example - if you could eliminate "back-facing" corners, you'd only need to check 9 combinations of corners rather than 16. Given that the rectangles don't overlap, that's not so difficult. For each rectangle, calculate a center point. For each edge, calculate (using IIRC a cross product) which direction faces out. Dot products between cross products and other-rectangle centers yada yada - a lot like backface elimination for 3D games. A corner that has both it's edges as "back facing" cannot be a nearest corner and is eliminated. Trouble is, that's more work than you save. | |
| Jan 19, 2014 at 13:00 | comment | added | user8709 | @shoham - trying to optimise risks slowing it down. A more sophisticated approach means more complex code, working more slowly per item checked. This is only worthwhile when you can avoid checking large numbers of items. In this case, you might be able to use some kind of nearest-neighbour data structure to help "optimise" your search, but I'm betting it would end up slower. If you really need an optimised approach, you'll need to try several alternatives (including this simple brute force) and measure to see how they work out. | |
| Jan 19, 2014 at 12:56 | comment | added | shoham | I need it to be as efficient as possible. How can I optimize it? | |
| Jan 19, 2014 at 12:55 | history | answered | Joel Brown | CC BY-SA 3.0 |