Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Checking whether a point is inside or outside a semi-circle (or a rectangle for that matter) is a constant-time operation. </p> <p>Checking N points lie inside or outside a semi-circle or rectangle is O(N). </p> <p>Sorting your N points is O(N*lg(N)). </p> <p>It is asymptotically faster to test all points sequentially than it is to sort and then do a fast culling of the points based on a binary search. </p> <p>This may be one of those times where what seems fast and what is fast are two different things.</p> <p><strong>EDIT</strong></p> <p>There's also a dead-simple way to test containment of a point in the semi-circle without mucking about with rotations, transformations, and the like.</p> <p>Represent the semi-circle as two components:</p> <ul> <li>a line segment from point <strong>a</strong> to <strong>b</strong> representing the diameter of the semi-circle</li> <li>an orientation of either <em>left-of</em> or <em>right-of</em> indicating that the semi-circle is either to the left or right of line segment <strong>ab</strong> when traveling from <strong>a</strong> to <strong>b</strong></li> </ul> <p>You can exploit the right-hand rule to determine if the point is inside the semicircle.</p> <p>Then some pseudo-code to test if point <strong>p</strong> is in the semi-circle like:</p> <pre><code>procedure bool is_inside: radius = distance(a,b)/2 center_pt = (a+b)/2 vec1 = b - center_pt vec2 = p - center_pt prod = cross_product(vec1,vec2) if orientation == 'left-of' return prod.z &gt;= 0 &amp;&amp; distance(center_pt,p) &lt;= radius else return prod.z &lt;= 0 &amp;&amp; distance(center_pt,p) &lt;= radius </code></pre> <p>This method has the added benefit of not using any trig functions and you can eliminate all square-roots by comparing to the squared distance. You can also speed it up by caching the 'vec1' computation, the radius computation, center_pt computation, and reorder a couple of the operations to bail early. But I was trying to go for clarity.</p> <p>The 'cross_product' returns an (x,y,z) value. It checks if the z-component is positive or negative. This can also be sped up by not using a true cross product and only calculating the z-component.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhat algorithm can I use to determine points within a semi-circle?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USuser21714
    1. USuser21714
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhat algorithm can I use to determine points within a semi-circle?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    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. COAh, interesting. I guess that will always be true since no data structure can maintain them in less than linear time. It is just so tempting to try to reduce the number of points I check.
      singulars
      1. PO
      1. USkhayman218
    2. COThe spatial partitioning suggested by Breton in another answer could reduce the points to be checked. It will still be replacing one constant time operation with another; however, I think maintaining the positioning metadata will be less than doing the distance calculation.
      singulars
      1. PO
      1. USkhayman218
    3. COBut note that if you have many semicircles to test against, you can still obtain an asymptotic speedup by sorting just once and then binary searching.
      singulars
      1. PO
      1. USj_random_hacker
 

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