I have a set of points W={(x1, y1), (x2, y2),..., (xn, yn)} on the 2D plane. Can you find an algorithm that takes these points as the input and returns a point (x, y) on the 2D plane which has the ...

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 ant...

I have a bunch of coplanar points defining a polygon in 3D space. These are always wound the same way (e.g. clockwise). I need to determine the signed normal to the plane containing this polygon, i...

Given a set of points S (x, y, z). How to find the convex hull of those points ? I tried understanding the algorithm from here, but could not get much. It says: First project all of the points...

In 2D plane, I have a point and a line. How to get the mirror point along this line?

Greetings, We have a set of points which represent an intersection of a 3d body and a horizontal plane. We would like to detect the 2D shapes that represent the cross sections of the body. There c...

Can somebody recommend an algorithm that creates a point sample from a 3D solid which is represented by triangles? The point sample should be nearly uniformly distributed on the surface and it shou...

I am trying to find the distance between two points on a triangulated surface (geodesic distance). It looks like a basic operation and is not trivial. So I am wondering if there are any libra...

I'm looking for a library or a paper that describes how to determine if one triangular mesh intersects another. Interestingly I am coming up empty. If there is some way to do it in CGAL, it is elu...

I have a lot of points on the surface of the sphere. How can I calculate the area/spot of the sphere that has the largest point density? I need this to be done very fast. If this was a square for e...

I will be working with a set of thousands of points. I can implement or use existing implementations of Fortunes Algorithm to produce the Voronoi diagram of the points, but my application also requ...

I'm attempting to determine if a specific point lies inside a polyhedron. In my current implementation, the method I'm working on take the point we're looking for an array of the faces of the polyh...

I am having a bit of a problem with an algorithm that I am currently using. I wanted it to make a boundary. Here is an example of the current behavior: Here is an MSPaint example of wanted be...

Is there any extension to the Hilbert space/plane filling curve that maps a non-square surface to a vector/line [for image mapping to vector]?

I am interesting in finding the diameter of two points sets, in 128 dimensions. The first has 10000 points and the second 1000000. For that reason I would like to do something better than the naive...

I have in mind this video, or this simulation, and I would like to reproduce the geodesic lines on some sort of surface in 3D, given by a function f(x,y), from some starting point. The midpoint me...

Following is a question from careercup.com's Google Interview section: Given 2*n + 3 points in 2d space, with no 3 points collinear and no 4 points lying on a circle, devise an algorithm that wil...

I have a point p, and n line segments in the 2d space. Is there a way I can preprocess the line segments so that I can efficiently (i.e. sublineraly) find the line segment closest (i.e with lowest ...

Suppose that I have a non-simple polygon, how CGAL can help me to partition it into a set of simple polygons? For example, give a polygon represented by a sequence of 2D points: (1, 1) (1, -1)...

I have a set of 2D points. I need to find a minimum area ellipse enclosing all the points. Could someone give an idea of how the problem has to be tackled. For a circle it was simple. The largest d...

What the most efficient way in the programming language R to calculate the angle between two vectors?

Is there any existing Bentley-Ottmann Algorithm Implementation/library in C# or Java?

Please see Image: https://i.sstatic.net/NPUmR.jpg I have an undirected graph which contains one or more connected sub graphs. The graph is defined by a set of ordered pairs of connected vertices. ...

I am experimenting with creating high-performance, good-looking pencil tools using SVG paths. I am logging the mouse coordinates to draw a path. To get a high-fidelity path (accurate to the user's...

I am trying to grasp the explanation of the closest pair point problem in various literatures. While the basic approach is the same in all of them, divide-solve-combine (divide and conquer), and ge...