Stack Overflow
Stack Overflow

Questions tagged [computational-geometry]

is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.

The computational-geometry tag should be assigned to questions about computation and manipulation of locations or properties of geometric identities or objects. Since geometry computations are highly tolerance dependent, definition and computation of tolerances are welcome, too. Sample Questions are: How to compute line-line intersection on 3D? What is the better way of handling geometrical identities as data structures? How to compute volume of a solid? How to deform a solid? How to obtain parametric solids or surfaces?

2743 questions
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
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
183
votes
8 answers

Sort points in clockwise order?

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with something looking rather "solid", as convex…
Philipp Lenssen
  • 8,818
  • 13
  • 56
  • 77
77
votes
9 answers

robust algorithm for surface reconstruction from 3D point cloud?

I am trying to figure out what algorithms there are to do surface reconstruction from 3D range data. At a first glance, it seems that the Ball pivoting algorithm (BPA) and Poisson surface reconstruction are the more established methods? What are…
Fredriku73
  • 3,170
  • 4
  • 35
  • 32
60
votes
10 answers

How do I efficiently determine if a polygon is convex, non-convex or complex?

From the man page for XFillPolygon: If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection. If shape is Convex, for every pair of points inside the polygon, the…
hhafez
  • 38,949
  • 39
  • 113
  • 143
58
votes
16 answers

Geo Fencing - point inside/outside polygon

I would like to determine a polygon and implement an algorithm which would check if a point is inside or outside the polygon. Does anyone know if there is any example available of any similar algorithm?
Niko Gamulin
  • 66,025
  • 95
  • 221
  • 286
56
votes
6 answers

Calculating normals in a triangle mesh

I have drawn a triangle mesh with 10000 vertices(100x100) and it will be a grass ground. I used gldrawelements() for it. I have looked all day and still can't understand how to calculate the normals for this. Does each vertex have its own normals or…
Vince
  • 613
  • 1
  • 7
  • 8
53
votes
7 answers

Largest circle inside a non-convex polygon

How can I find the largest circle that can fit inside a concave polygon? A brute force algorithm is OK as long as it can handle polygons with ~50 vertices in real-time.
Plow
  • 4,001
  • 3
  • 20
  • 21
49
votes
7 answers

Find if a point is inside a convex hull for a set of points without computing the hull itself

What is the simplest way to test if a point P is inside a convex hull formed by a set of points X? I'd like an algorithm that works in a high-dimensional space (say, up to 40 dimensions) that doesn't explicitly compute the convex hull itself. Any…
dimi
  • 601
  • 1
  • 6
  • 5
49
votes
9 answers

What is the fastest way to find the closest point to a given point?

What is the fastest way to find closest point to the given point in data array? For example, suppose I have an array A of 3D points (with coordinates x, y and z, as usual) and point (x_p, y_p, z_p). How do I find the closest point in A to (x_p, y_p,…
qutron
  • 1,710
  • 4
  • 18
  • 30
49
votes
9 answers

What is the most efficient algorithm to find a straight line that goes through most points?

The problem: N points are given on a 2-dimensional plane. What is the maximum number of points on the same straight line? The problem has O(N2) solution: go through each point and find the number of points which have the same dx / dy with relation…
Leonid
  • 22,360
  • 25
  • 67
  • 91
47
votes
6 answers

Algorithm to generate random 2D polygon

I'm not sure how to approach this problem. I'm not sure how complex a task it is. My aim is to have an algorithm that generates any polygon. My only requirement is that the polygon is not complex (i.e. sides do not intersect). I'm using Matlab for…
s5s
  • 11,159
  • 21
  • 74
  • 121
47
votes
3 answers

How to check if line segment intersects a rectangle?

If you have 2 points, (x1, y1) and (x2, y2), which represent two opposite corners of a rectangle, and 2 other points, (x3,y3) and (x4,y4), which represent 2 endpoints of a line segment, how can you check if the line segment intersects the…
omega
  • 40,311
  • 81
  • 251
  • 474
44
votes
15 answers

Perpendicular on a line from a given point

How can I draw a perpendicular on a line segment from a given point? My line segment is defined as (x1, y1), (x2, y2), If I draw a perpendicular from a point (x3,y3) and it meets to line on point (x4,y4). I want to find out this (x4,y4).
Zinx
  • 2,291
  • 3
  • 28
  • 37
40
votes
11 answers

Algorithm to compute a Voronoi diagram on a sphere?

I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code too.
stevenvh
  • 2,971
  • 9
  • 41
  • 54
1
2 3
…
99 100