Stack Overflow
Stack Overflow

Questions tagged [grahams-scan]

Graham's scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary.

34 questions
36
votes
3 answers

Sort latitude and longitude coordinates into clockwise ordered quadrilateral

Problem Users can provide up to four latitude and longitude coordinates, in any order. They do so with Google Maps. Using Google's Polygon API (v3), the coordinates they select should highlight the selected area between the four…
Dave Jarvis
  • 30,436
  • 41
  • 178
  • 315
10
votes
3 answers

Sorting points by their polar angle in Java

I'm using Graham scan algorithm to find the convex-hull of set of points I'm trying to sort the points by their polar angle but I have no idea how to do it (I've already sorted the set of points by their Y coordinates). What I've already wrote is…
Navid Koochooloo
  • 285
  • 1
  • 5
  • 20
5
votes
2 answers

Sorting by Polar Angle

I'm trying to implement the Graham’s Scan algorithm for a convex hull in Java, and have trouble sorting the points by polar angle with respect to the point with lowest y-value. I have found this answer and understand how to calculate the polar…
Pakchoiandbacon
  • 55
  • 1
  • 7
5
votes
2 answers

algorithm to calculate perimeter of unioned rectangles

I'm trying to calculate the perimeter of the union of a n rectangles, of which I have the bottom left and top right points. Every rectangle sits on the x axis (bottom left corner of every rectangle is (x, 0)). I've been looking into different ways…
Talen Kylon
  • 1,908
  • 7
  • 32
  • 60
3
votes
1 answer

Erroneous points produced on convex hull despite following Graham scan

I've essentially followed the wikipedia entry for Graham scan every step of the way as I've coded this little convex hull visualizer. It generally works as intended, but at much higher input sizes there are often erroneous points. The program starts…
MattDs17
  • 401
  • 1
  • 4
  • 20
3
votes
2 answers

Why stack in convex hull

I was reserarching about Convex hull and Graham Scan to implement it and It drew my attention that everyone has used stacks. So I wanted to ask why are the stacks used in the algoithm precisely, what's the benefit of using stacks?
Ege
  • 941
  • 4
  • 17
  • 36
3
votes
2 answers

Convex Hull Misunderstanding?

I wrote an implementation of Graham's Scan convex hull algorithm and for test data I used the points [(2.0,2.0),(4.0,2.0),(0.5,2.5),(3.0,3.5),(1.0,4.0),(0.0,4.0),(1.0,1.0),(3.0,2.5),(4.0,4.0),(3.5,1.5),(0.5,1.0)] According to my program the convex…
Ra is dead
  • 569
  • 2
  • 18
2
votes
1 answer

Struct comparator accessing another field in c++

I am trying to implement Graham scan, and I want to do something like this: private static void sortByPolar(Point[] points, Point r) { Arrays.sort(points, (p, q) -> { int compPolar = ccw(p, r, q); int compDist = dist(p, r) - dist(q, r);…
apluscs
  • 75
  • 5
2
votes
2 answers

Haskell length and filter to determine convexity or concavity of a line

I am reading Real World Haskell, trying to solve Ch3, Q10 using ghc online. So far I have the following code: data Direction point = MyLeft point | MyRight point | Straight deriving (Show) getDirectionFromTriple :: Direction p -> Direction p ->…
mushishi
  • 141
  • 1
  • 10
2
votes
0 answers

Jarvis algorithm (gift-wrapping) or graham-scan - C#

I have a list of Shapes and I have to make a convex hull around them. I tried to do a gift-wrapping algorithm (Jarvis). So far I have foud a plenty of pseudocodes and I understand the logic, but I can't program it. Could only do the 1st step -…
Moth Lamp
  • 21
  • 2
2
votes
2 answers

Convex Hull Algorithm - Graham scan fastest compare function?

I am already implemented Graham scan, but i see that the bottleneck of my program is the sorting (80% of the time). I want to improve in it, now I am doing the following: std::sort(intersections.begin() + 1, intersections.end(), [&minElement](Point…
Ryper
  • 338
  • 3
  • 15
2
votes
1 answer

Is there a way to further optimize Graham Scan algorithm to find the convex hull?

I went through chan's algorithm. It doesn't seem much better to me. Is there a way I can replace that sorting part in graham scan with anything else ? so that O(nlogn) time could be further reduced. Java implementation is preferred.
rishu
  • 21
  • 3
2
votes
1 answer

Merging two tangled convex hulls

How to merge two tangled convex hulls (like this) to form a Convex Hull using Graham's Scan or anyother algorithm in linear time?
emotionull
  • 595
  • 2
  • 8
  • 24
2
votes
2 answers

Input for Jarvis algorithm so that is faster than Graham's (convex hull)

Jarvis: This algorithm requires O(nh) time in the worst case for n input points with h extreme points. Graham: O(nlogn) in the worst case scenario. Source the ref of CGAL, from where I use the two algorithms. That means that Jarvis can be faster…
gsamaras
  • 71,951
  • 46
  • 188
  • 305
1
vote
1 answer

C++ Convex hull using Graham scan algorithm

So i need to make a Convex hull using Graham scan algorithm, but i have problem, i get this kinda convex: void draw_line(Line l, Canvas& canvas) { canvas.draw_line(l.a, l.b); } double drandom(){ return rand() * 1. / RAND_MAX; } bool…
Eldarion
  • 59
  • 1
  • 8
1
2 3