Data structures and algorithms related to geometry.
Data structures and algorithms related to geometry, a branch of mathematics concerned with questions of shape, figures, and dimensions in space.
See also Wikipedia
Questions tagged [geometry]
12992 questions
2017
votes
23 answers
How do CSS triangles work?
There're plenty of different CSS shapes over at CSS Tricks - Shapes of CSS and I'm particularly puzzled with a triangle:
#triangle-up {
width: 0;
height: 0;
border-left: 50px solid transparent;
border-right: 50px solid transparent;
…
Stanislav Shabalin
- 19,028
- 3
- 18
- 18
515
votes
27 answers
How do you detect where two line segments intersect?
How do I determine whether or not two lines intersect, and if they do, at what x,y point?
KingNestor
- 65,976
- 51
- 121
- 152
442
votes
56 answers
Shortest distance between a point and a line segment
I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript).
EDIT: My line segment is defined by two…
Eli Courtwright
- 186,300
- 67
- 213
- 256
436
votes
31 answers
Calculate distance between 2 GPS coordinates
How do I calculate distance between two GPS coordinates (using latitude and longitude)?
nicudotro
- 7,129
- 6
- 25
- 17
400
votes
21 answers
Determine if two rectangles overlap each other?
I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges…
Rob Burke
- 5,365
- 4
- 31
- 30
395
votes
17 answers
Equation for testing if a point is inside a circle
If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?
directedition
335
votes
25 answers
How to determine if a point is in a 2D triangle?
Is there an easy way to determine if a point is inside a triangle? It's 2D, not 3D.
ET 0.618
- 3,433
- 4
- 17
- 5
331
votes
25 answers
How to determine if a list of polygon points are in clockwise order?
Having a list of points, how do I find if they are in clockwise order?
For example:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
would say that it is anti-clockwise (or counter-clockwise, for some people).
Stécy
- 11,951
- 16
- 64
- 89
298
votes
23 answers
Generate a random point within a circle (uniformly)
I need to generate a uniformly random point within a circle of radius R.
I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... R) I would end up with more points…
aioobe
- 413,195
- 112
- 811
- 826
253
votes
6 answers
How to do a scatter plot with empty circles in Python?
In Python, with Matplotlib, how can a scatter plot with empty circles be plotted? The goal is to draw empty circles around some of the colored disks already plotted by scatter(), so as to highlight them, ideally without having to redraw the colored…
Eric O. Lebigot
- 91,433
- 48
- 218
- 260
241
votes
26 answers
Circle-Rectangle collision detection (intersection)
How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)
aib
- 45,516
- 10
- 73
- 79
241
votes
15 answers
An algorithm for inflating/deflating (offsetting, buffering) polygons
How would I "inflate" a polygon? That is, I want to do something similar to this:
The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the example picture they…
Igor Brejc
- 18,714
- 13
- 76
- 95
236
votes
6 answers
Using the "animated circle" in an ImageView while loading stuff
I am currently using in my application a listview that need maybe one second to be displayed.
What I currently do is using the @id/android:empty property of the listview to create a "loading" text.
Waza_Be
- 39,407
- 49
- 186
- 260
224
votes
29 answers
Circle line-segment collision detection algorithm?
I have a line from A to B and a circle positioned at C with the radius R.
What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?
Mizipzor
- 51,151
- 22
- 97
- 138
210
votes
4 answers
How do I calculate the normal vector of a line segment?
Suppose I have a line segment going from (x1,y1) to (x2,y2). How do I calculate the normal vector perpendicular to the line?
I can find lots of stuff about doing this for planes in 3D, but no 2D stuff.
Please go easy on the maths (links to worked…
Piku
- 3,526
- 6
- 35
- 38