Databases
StackOverflow2013
Postsdbo
PODiameter of a Convex polygon using Rotating Calipers
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODiameter of a Convex polygon using Rotating Calipers
    primarykey
    data
    text
    <p>I am trying to solve the problem of finding the diameter of a convex polygon i.e a pair of points that have maximum distance between them.</p> <blockquote> <p><a href="http://cgm.cs.mcgill.ca/~orm/diam.html" rel="nofollow">http://cgm.cs.mcgill.ca/~orm/diam.html</a></p> </blockquote> <p>I have tried to implement the algorithm/pseudo-code mentioned here. But I am getting wrong answer for the polygon made using these points (-3,-4) (2,-3) (4,3) (0,5)</p> <p>Clearly the diameter of polygon is (-3,-4) (4,3). But according to the pseudo-code mentioned here I get diameter as (-3,-4) (0,5)</p> <pre><code>struct vert { long long int x,y,idx; double rad; int next; vert() {} vert(long long int _x,long long int _y) { x=_x; y=_y; rad=atan2(double(y),double(x)); } }; long long int dist(vert a,vert b) { vert ab=b-a; return (ab.x*ab.x+ab.y*ab.y); } int cross(vert a,vert b,vert c) { vert ab,ac; ab=b-a; ac=c-a; return ab.x*ac.y-ab.y*ac.x; } double area(vert a,vert b,vert c) { double x=cross(a,b,c); x=abs(x/2.00); return x; } struct ret { vert a,b; double dist; }; ret comp(ret ans,vert a,vert b) { if(dist(a,b)&gt;ans.dist) { ans.a=a; ans.b=b; ans.dist=dist(a,b); } return ans; } ret rc_diameter(vector&lt;vert&gt; &amp;v) { int i,j,k,l,n; n=v.size(); int a,b; int p,q,p0,q0; p0=p=0; q=1; ret ans; ans.dist=0; while(area(v[p],v[v[p].next],v[v[q].next])&gt;area(v[p],v[v[p].next],v[q])) { q=v[q].next; } q0=q; ans=comp(ans,v[p],v[q]); while(q!=p0) { p=v[p].next; ans=comp(ans,v[p],v[q]); while(area(v[p],v[v[p].next],v[v[q].next])&gt;area(v[p],v[v[p].next],v[q])) { q=v[q].next; if(p!=q0&amp;&amp;q!=p0) ans=comp(ans,v[p],v[q]); else return ans; } if(area(v[p],v[v[p].next],v[v[q].next])==area(v[p],v[v[p].next],v[q])) { if(p!=q0&amp;&amp;q!=p0) ans=comp(ans,v[p],v[v[q].next]); else ans=comp(ans,v[v[p].next],v[q]); } } return ans; } </code></pre> <p>So can any when tell me if there is a problem in the pseudo-code or in my implementation also when I applied this algorithm on the given set of points manually I am still getting (-3,-4) (0,5) as diameter.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USAman Singhal
    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
    1. VO
      singulars
      1. PODiameter of a Convex polygon using Rotating Calipers
      1. USAman Singhal
      1. VTFavorite
    2. VO
      singulars
      1. PODiameter of a Convex polygon using Rotating Calipers
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PODiameter of a Convex polygon using Rotating Calipers
      1. USrrufai
      1. VTFavorite
    1. This table or related slice is empty.
 

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