Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think there are 3 pieces to this.</p> <ol> <li><p>calculate the intersection of the 2 lines, and hold on to the X and Y coordinates of that point</p></li> <li><p>find the section that the given point is in. This should be easy enough, because you have the slope of the 2 lines, and the slope of the line created by the given point and the point of intersection. Call them <code>m_line1</code>, <code>m_line2</code> and <code>m_intersect</code>. If <code>m_intersect</code> There's a formula to figure out the section using these values and the location of the given point.</p></li> <li>find the closest integer. There is also a straightforward calculation of this once you know the values from #1 above, and the slopes from #2. You can brute-force it, but there is an elegant mathematical solution.</li> </ol> <p>These are the steps I took, at least.</p> <p><strong>Updated to add more substance</strong></p> <p>OK, I'll start us off with a discussion on #2.</p> <p>If you calculate the slope of the given point and the intersection point, then you arrive at <code>m_intersection</code>. This is the slope of a line that passes through the intersection point. Let's assume that <code>m_line1</code> is the greater of the 2 slopes, so that line1 is "above" line2 as x increases after the intersection. It makes it easier to think about for section names. We'll call section <strong>A</strong> the section given by the sliver between line1 and line2 for x larger than the intersection coordinate x, and then we'll name the other 3 sections clockwise, so that <strong>A</strong> and <strong>C</strong> are opposite each other.</p> <p>If <code>m_intersection</code> is between <code>m_line1</code> and <code>m_lin2</code>, then it must be in one of the 2 sections <strong>A</strong> or <strong>C</strong>. Which section is a simple test of the x coordinate value against the intersection's x coordinate. We defined <strong>A</strong> to be the section with greater value. A similar calculation can be made if the slope is outside <code>m_line1</code> or <code>m_line2</code>.</p> <p>This gives you the section that your point lies in. All you did was calculate 1 intersection (5 multiplications, 2 divisions and a handful of subtractions if you do it the traditional way), 3 slopes, and then a couple integer comparisons.</p> <p><strong>Edit #3 - back by (un)popular demand!</strong></p> <p>So here is how I calculated #3, the closest integer point to the intersection. It may not be the best, but it uses binary search, so it's O(log n) where n is related to the inverse of the difference of the line slopes. The closer they are together, the larger n is.</p> <p>First, take the difference between the slopes of the two lines. Say it's 1/8. This means that from the point of intersection, you have to go out 8 units along the x axis before you are guaranteed that there is a whole integer on the y axis in between the two lines (it may be on one of the lines). Now, if the intersection itself is not on an integer x coordinate, then you'll need to step out further to guarantee that your starting point is on an integer x coordinate, but it is bounded. If the intersection is at x = 1.2, then in the above example, at worst you'd start at x = 41, then move down ~5 units along the y axis. Choose either the ceil or floor of the y value that you get. It's not terribly critical.</p> <p>Now that you have a starting point, the closest point can be approximated by binary search. Your new line segment is between the intersection and the starting point, and your units of movement are multiples of that line segment's slope. Calculate the midpoint of the line segment and see if it lies in between the two lines. Add or subtract 1 to it if it is not a direct hit, and if either of those hits, cut the remaining distance in half and do it again. Otherwise search the further half of the segment.</p> <p>If you don't have a slope difference &lt; 1, I think the problem may be simpler (brute force the space around the intersection). But it's just a special case of the search above, where you don't need to step out that far to find a starting point.</p>
    singulars
    1. This table or related slice is empty.
    1. POGiven two lines on a plane, how to find integer points closest to their intersection?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USPhil
    1. USPhil
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI didn't downvote because I don't know if this method has potential or not, but your answer is not very helpful. Just saying "there's a way to do this" on every important step is really not helping anyone.
      singulars
      1. PO
      1. USIVlad
    2. CO@IVlad, this method is as helpful as Fermat's proof of his Last Theorem :-)
      singulars
      1. PO
      1. USP Shved
    3. COSorry for the terseness. I've given homework answers accidentally before. Also, I was in the middle of cooking and didn't have time to fully flesh out everything.
      singulars
      1. PO
      1. USPhil
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload