Databases
StackOverflow2013
Postsdbo
POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
    primarykey
    data
    text
    <p><strong>Edit:</strong> Changed the title. I'm less interested in the two segments being the same, but rather, if they are colinear with each other, within a certain tolerance. If so, then the lines should be clustered together as a single segment.</p> <p><strong>Edit:</strong> I guess a short way of saying this: I'm trying to cluster similar line segments together in an efficient way.</p> <p>Say I have line segments <code>f</code> <code>(fx0, fy0)</code> and <code>(fx1, fy1)</code> and <code>g</code> <code>(gx0, gy0)</code> and <code>(gx1, gy1)</code></p> <p>These come from something like a computer-vision algorithm edge detector, and in some cases, the two lines are basically the same, but are counted as two distinct lines because of pixel tolerances.</p> <p><strong>There are several scenarios</strong></p> <ul> <li><code>f</code> and <code>g</code> share the exact same endpoints, eg: <code>f = (0,0), (10,10) g = (0,0), (10,10)</code></li> <li><code>f</code> and <code>g</code> share roughly the same endpoints, and roughly the same length, eg : <code>f = (0,0.01), (9.95,10) g = (0,0), (10,10)</code></li> <li><code>f</code> is a subset of <code>g</code>, meaning that its endpoints fall within the <code>g</code> segment and share the same slope as the <code>g</code> segment. Think of a roughly drawn line in which the pen has gone back and forth to make it thicker. eg : <code>f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)</code></li> </ul> <p>The following would <strong>not</strong> be considered the same:</p> <ul> <li><code>f</code> and <code>g</code> have a slope difference beyond a certain <code>tolerance</code></li> <li><code>f</code> and <code>g</code> may have the same slope but are separated by a distance beyond <code>tolerance</code>, i.e. parallel lines</li> <li><code>f</code> and <code>g</code> are on the same plane and same slope, but don't overlap at all...i.e. a set of segments within a dashed line.</li> </ul> <p>The easiest way to tell if they are the same is if <code>gx1 - fx1 &lt;= tolerance</code> (repeat for the three other points), but in some cases, line <code>f</code> may be shorter than line <code>g</code> (again, because of pixel differences and/or poor photo scanning). </p> <p>So is it better to convert the two segments into polar coordinates and compare the angles? In that case, the two rho's would be within a tolerance. But then you have to make sure the two line segments have the same "direction", which is trivial to compute in Cartesian or polar coordinates. </p> <p>So this is easy to figure out a way, but I'm just wondering if there's a much cleaner way, based in the linear algebra that I've long forgotten?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAbid Rahman K
    1. USZando
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think you need to be clearer. Specifying a line segment requires four numbers, for the coordinates of the beginning and end of the line, whereas you seem to have given two for each line. Also, would you consider the line from (0,0) to (1,1) to be "the same" as the line from (0,0) to (10,10)? Clearly they are both in the same direction, but one is much longer than the other.
      singulars
      1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
      1. USChris Taylor
    2. COOof, good call. I've added some clarifying terms and pass/fail circumstances. Thanks. And yes, I would consider (0,0) to (1,1) (or a slight variation, such as [0, 0] to [1, 1.02]) the same as (0,0) to (10,10), for the purposes of this exercise.
      singulars
      1. POWhat is the most efficient way to determine if two line segments are part of the same segment, within a tolerance?
      1. USZando
 

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