Questions tagged [computational-geometry]
Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.
856
questions
1
vote
0
answers
36
views
Find maximum sized rectangle on a plane
I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
- 31
3
votes
0
answers
42
views
Shortest path in polygon from 2 points such that entire polygon is visible
Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon,
find the shortest path traveling only in the direction of the x or y ...
1
vote
0
answers
19
views
Computing the centroid of an "ellipsoid slice"
I want to compute the centroid of a body of the following form:
$$
E\cap H_1\cap \cdots \cap H_T
$$
where:
$E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
- 5,730
2
votes
0
answers
37
views
Related papers about finding longest vector(maximum in magnitude) as subset sum from given set of 2d vectors [duplicate]
Given a set of 2D vectors. Find maximum magnitude of sum of a subset of the set.
I want to do my undergrad thesis on this topic. Can anyone suggest me some existing papers related to this topic or its ...
1
vote
1
answer
14
views
How to avoid global delaunay check in conforming triangulation?
I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
- 331
1
vote
0
answers
26
views
How to actually implement ruppert's algorithm?
I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2:
...
- 331
1
vote
1
answer
39
views
Fast measurement of distance from point to mid segment?
Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge.
This is very straightforward:
$$d = \|\frac{a + b}{2} - p\|$$...
- 331
0
votes
1
answer
44
views
Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space
Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point ...
- 103
0
votes
1
answer
31
views
compute the intersection of two polytopes and it's corner points
I am looking for a method in python/matlab to calculate the corner points of polytope which is an intersection of a polytope with half spaces.
I have a polytope P1 of the form
-1<= x0 <= 1
-1&...
- 21
0
votes
0
answers
25
views
Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"
I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
- 101
0
votes
1
answer
76
views
Matching points on a plane with maximum total weight
I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
- 95
0
votes
2
answers
201
views
An efficient way of finding the closest point of a sampled function to another point
I have a function $f(x)$, has been sampled into a sequence
$$
y_0, y_1, ..., y_{n - 1}
$$
at points $x_k = k \Delta x$. $f(x)$ is neither smooth or monotone.
Under this assumption, what is the fastest ...
- 147
2
votes
1
answer
76
views
Efficient algorithm for finding a point P with the highest winding number
Given an ordered list of two-dimensional points $P$ that represent the vertices of an $N$-sided (very) self-intersecting polygon, find a point $p_{best}$ with the highest winding number of all points ...
- 131
3
votes
1
answer
34
views
Trajectories with collisions
Say that I have a plasma gun:
It's easy to compute the trajectory of the plasma ray starting from the gun.
However, another ray may come from afar:
As everybody knows, plasma rays are deviated when ...
- 131
1
vote
0
answers
37
views
Given a set of railroad tracks of certain shapes, find all closed tracks that can be build with it
Imagine having a number of straight and curved train track segments (e.g. 90° to the left and right, but they could have other values in the general case), how is it possible to find all complete (...
- 191
0
votes
1
answer
24
views
How to enforce convexity of triangulation output?
I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue.
The algorithm starts by creating a bounding triangle that it then splits recursively ...
- 331
1
vote
1
answer
36
views
Detecting non-airtight geometry
I have a finite region of 3D space that some (arbitrarily-shaped, concave) geometry occupies, and I need to identify whether that geometry forms a closed 3D volume (or multiple disjoint closed 3D ...
0
votes
0
answers
34
views
Data Structure for Positioning Non-Overlapping Rectangles Into Grid
I'm trying to implement a very crude form of the css grid layout. It's layout algorithm is as documented.
“sparse” packing (default behavior)
Set the column-start line of its placement to the ...
- 113
1
vote
3
answers
77
views
Matching the segments of a set to longer segments of another set
Consider a set $S$ of segments in the plane. Split each segment in $S$ into a few pieces, and slightly modify the extremities of each obtained segment (by adding a small random value to their ...
- 625
0
votes
0
answers
20
views
Getting a V-representation from an H-Representation of a polytope
I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
- 331
0
votes
0
answers
18
views
Implementation of algorithm to enumerate all vertices of a convex polyhedron defined as linear inequalities?
I am looking for an implementation for any of the methods to enumerate all vertices of a convex polyhedron defined by $Ax \leq b$
I have found some papers that talk about the problem, for example this ...
- 331
1
vote
0
answers
39
views
Algorithm for Steiner points?
I am trying to find resources that explain an easy to implement (not necessarily optimal but reasonable runtime) algorithm for inserting Steiner points in a triangulation.
There seems to be little ...
- 331
4
votes
2
answers
494
views
Detecting if an edge is "inside" a polygon?
I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon.
The objective is to detect all edges which are inside the polygon, that is, an edge where ...
- 331
0
votes
0
answers
11
views
Compute the intersection and difference of multiple polygons
I have multiple (possibly concave) simple polygons, and need to compute the union and difference of them, some polygons have to be added, some subtracted from the final shape. I have found algorithms ...
3
votes
2
answers
82
views
Constrained Delaunay triangulation algorithm?
I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the ...
- 331
3
votes
2
answers
64
views
Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?
I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things.
Ever resource I read on the matter says:
Make ...
- 331
0
votes
0
answers
16
views
Algorithm for computing the vertices of a polytope defined as the intersection of half spaces
There's a very similarly sounding question with an answer already, but my setup is very, very different.
You are given $k$ half spaces in dimension $d$, defined by a point and a direction. You want to ...
- 331
4
votes
1
answer
139
views
Rotating sort algorithm
Take a set of $n$ points in the plane. You want to sort them by increasing abscissa. But you also want to sort them by abscissa after several arbitrary rotations, say $k$, in increasing angles.
The ...
user16034
1
vote
0
answers
50
views
Are there known algorithms to find a line that intersects a given set of segments?
Are there known algorithms to find a line that intersects a given set of segments?
In:
A finite set of segments.
Out:
A line that cross all these segments or explicit answer that there is no such line....
1
vote
1
answer
103
views
Orthogonal connectors with non-overlapping horizontal or vertical line segments
I have an upper row of $N$ equally spaced 'units' and a lower row of $N$ equally spaced 'units'. I would like to connect any of the upper row of units to the lower units via orthogonal connectors (...
- 153
1
vote
0
answers
23
views
Matching a 2D points cloud to polylines
I have a (2D) point cloud of reasonable size (say some thousands of points) and a set of (2D) polylines also of a reasonable size. I want to assess the discrepancies between the two geometries and for ...
user16034
0
votes
0
answers
27
views
NURB Sphere surface degree elevation and knot insertion
The code for degree elevation of curves in The NURBS Book by Les Piegl and Wayne Tiller pages 206--209(The_NURBS_Book) assumes the knot vector for the curve is given as:
$$(0,...,0,...,1,...,1)$$
...
- 1
2
votes
1
answer
74
views
Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:
df1 for distributor 1.
...
- 280
1
vote
1
answer
196
views
How to turn a 3D polytope into a mesh?
Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N ...
- 331
3
votes
0
answers
71
views
Minimum spanning tree between blobs
We have a binary raster image in which we consider the white blobs (connected components). We define a distance between two blobs to be the length of the shortest path between any two respective ...
user16034
7
votes
2
answers
331
views
Queries to count points lying on arbitrary line
Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$.
Is it possible to count number of points ...
- 105
0
votes
1
answer
46
views
Finding pixel closest (grid points) to rectilinear polygons
I have rectilinear polygons present, and they are surrounded by grids(grey rectangle with dots denoting center) as shown in the diagram below. There are some areas where grids are not present - like ...
- 3
2
votes
1
answer
85
views
Red-blue orthogonal line intersection algorithm
I need to efficiently find the intersections between a set of vertical line segments and a set of horizontal ones. The segments in both families can overlap (but there are no duplicates). Presumably ...
user16034
3
votes
3
answers
150
views
Find a unit square containing most of the points
Given points $p_1,\ldots,p_n$ in $\mathbb{R}^2$, the task is to find an axis-aligned unit square containing the maximum number of points. I came up with and $O(n^3)$ algorithm as follows.
Observation ...
- 267
2
votes
0
answers
44
views
Minimal bounding quadrilateral of a convex polygon
I am looking at the problem of finding the quadrilateral of minimum area that encloses a convex polygon.
I found the following articles:
An Optimal Algorithm for Finding Minimal Enclosing Triangles ...
user16034
4
votes
0
answers
48
views
Minimum stabbing problem for a set of convex polygons
Let $S = \{P_1, P_2, ..., P_m\}$ be a set of convex polygons in $\mathbb R^2$ with a total of $n$ vertices. Polygons are defined by ordered lists of vertices, and each vertex is represented by a pair $...
- 3,048
0
votes
2
answers
51
views
Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?
Given an undirected graph with nonnegative edge weights and a partition of the vertex
set into terminals and Steiner vertices, the Steniner tree problem consists in finding a
minimum weight tree in ...
- 423
3
votes
3
answers
870
views
Multi-line fitting problem
Given a set of n points, and a number k decide whether there exist k straight lines such ...
- 53
0
votes
0
answers
32
views
Generalizing the de Casteljau algorithm to cubic Bézier curve trisection
Splitting the Bézier cubic defined by the four control points $P, Q, R$, and $S$ in two parts corresponding to the two parametric subintervals $[0, t]$ and $[t, 1]$ is relatively easy: we perform ...
user16034
2
votes
1
answer
85
views
Finding 2 points that are k'th closest and their distance is minimal among such points with Chebyshev distance
Let $p_1,p_2 \dots p_n$ be $n$ points in 2D such that $p_i= ( x_i,y_i) $
Let $d(p_i,p_j)= \max (|x_i-x_j|,|y_i-y_j|)$, or better known as Chebyshev distance.
Find a point $p_i$ such that the distance ...
- 232
0
votes
0
answers
32
views
Translating math notation from paper into something more accessible to a layman
I have been struggling trying to understand this differential geometry paper:
https://cseweb.ucsd.edu/~alchern/projects/MinimalCurrent/MinimalCurrent.pdf
I would like to ask for someone with more ...
- 331
2
votes
0
answers
26
views
Topologizing boundaries in 3D space
I have a set of closed curves (not convex, not planar) in 3D.
The goal is to produce A mesh (any will do) that is manifold and contains the closed curves as boundaries/holes.
For example like this ...
- 331
2
votes
2
answers
111
views
How to handle coplanarity in convex hull?
I implemented the $O(n^2)$ convex hull algorithm. That is:
Find a triangle known to be in the hull (by finding the lowest point, a point connected to it in the 2D convex hull, and the point that ...
- 331
0
votes
0
answers
20
views
Original paper for a linked-list based circular packing algorithm
A circular packing algorithm to pack an array of radii roughly into a circle was implemented by someone else but they do not remember the paper in which they took the algorithm from. All I know is ...
- 1
1
vote
1
answer
40
views
Efficient algorithm to compute the number of points at the lower left of another point
Consider $N$ points that are located on a 2D plane where the $i$-th point’s location is denoted as $(x_i, y_i)$.
Is there any efficient algorithm that can compute $d_i$ that is defined as the number ...
- 163