The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves ...

learn more… | top users | synonyms

2
votes
1answer
47 views

Fastest computation to find out if two vectors intersect (programming problem)

I'm trying to write a program that should solve a 12x12 rush hour problem: I won't go in the details of this program to much. The program already works for 6x6 puzzles, but for 12x12 puzzles, it is ...
0
votes
0answers
35 views

Rigid circles inside a square

There are $n$ circles each of radius $r$. They are needed to fit into a square with side length $t$ in a way such that, the circles can't move in any direction (each one is adjacent to some other ones ...
8
votes
0answers
100 views

How to measure the irregularity of a hexagon?

I need to evaluate the quality of a list of machine parts, which roughly has one center point surrounded by 6 exterior points. If the quality is good, then the 6 exterior points will form a regular ...
0
votes
2answers
32 views

Center of mass from shape boundary

It is possible to find a shape center of mass by only its boundary? Would the average coordinates of X and Y would approximate my center of mass? (If it would work how good the approximation is going ...
0
votes
0answers
13 views

What line-polygon clipping algorithm can I use to ensure that the resultant endpoints are always within the polygon?

I have a 2D plane, partitioned into n-sided, convex polygons. I'm using WRF's PNPOLY algorithm for polygon inclusion to ensure that a point belongs inside one and only one polygon. Is there an ...
1
vote
0answers
46 views

Constructing triangulations algorithmically

I am developing a Python package for computations in algebraic topology (namely: cohomology and Massey products on manifolds). Basically all the stuff I'm doing requires an explicit triangulation of ...
0
votes
0answers
27 views

Fencing $n$ points while keeping minimum distance $d$ from each point

Consider this problem **I have a land consisting of $n$ trees. Since the trees are favorites to cows, I have a big problem saving them. So, I have planned to make a fence around the trees. I want ...
0
votes
1answer
117 views

Calculate the area of an irregular cyclic convex polygon

I want to write a program in C++ to calculate the area of irregular cyclic convex polygons. However, the inputs are in the form corner point angles. I am just not sure what the inputs mean and what ...
0
votes
0answers
53 views

The number of facets of an affine image

I have a full dimensional polyhedron $P_1 \subseteq \mathbb{R}^d.$ Now i define another polyhedron as follows: $$P_2 = AP_1 \oplus B$$ with $A \in \mathbb{R}^{(d-1) \times d}, \,\, B \in \mathbb{R}^{...
1
vote
0answers
74 views

Winding Number of a Circle

I'm having a little trouble calculating the winding number of a circle about a point using parametric equations. The definition of a circle of radius $r$ and center coordinates $x_0$ and $y_0$ is the ...
0
votes
0answers
18 views

Natural neighbor interpolation

Recently I am interested in Natural neighbor interpolation, that is : Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function $$P^*(x)=\sum_{...
2
votes
1answer
23 views

2-d pathfinding around connected walls

In a recently released game, characters navigate (poorly) around a 2d martian surface performing tasks. Just for fun, I am trying to come up with a better algorithm. The problem: Given a set of non-...
1
vote
0answers
25 views

Algorithm detect simple curves using Voronoi diagram or Delaunay triangulation?

I wonder if there is algorithm/method to determine if closed (or even non closed) curve is simple or not, using the mathematics from the field of computational geometry? Especially I wonder if exist ...
1
vote
0answers
21 views

Find foci and eccentricity of ellipse given either 5 points or its general equation [duplicate]

I'm considering an arbitrary, non-degenerate ellipse here, i.e., without assuming that it's centred on the origin or either axis, nor oriented at any specific angle. I know either 5 points on the ...
4
votes
0answers
86 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
1
vote
1answer
30 views

Not a polyhedral complex example

I am having difficulty interpreting the definition of a polyhedral complex. Can someone explain it using an example and then walk me through an example which is not a polyhedral complex.
1
vote
1answer
76 views

Shortest polygonal line that connects three disjointing circles

Given three disjointing circles, how to find the shortest polygonal line (consisting of two line segments) that connects the three circles (a line segment connects circle A and B if it starts with ...
1
vote
1answer
40 views

point inclusion in a half-plane 3D

I have a 3D half-plane defined using a line segment an a point (as shown in picture taken from here). I am wondering how I can detect if a point belongs to the half-plane. Is there any way to ...
1
vote
0answers
20 views

Is this projection optimization problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$, we ...
3
votes
3answers
275 views

Check if a point is inside a rectangular shaped area (3D)?

I am having a hard time figuring out if a 3D point lies in a cuboid (like the one in the picture below). I found a lot of examples to check if a point lies inside a rectangle in a 2D space for example ...
0
votes
0answers
54 views

Determining N d-points yielding equal sums of Euclidean distances from M s-points

Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...
0
votes
0answers
36 views

Determing the Two Closest Vertices a Point Lies Between on Circumcircle

For a computational geometry application, I need to determine the two closest vertices that a point lies between on a circle that has been sliced into angular intervals. To illustrate the problem, ...
0
votes
3answers
69 views

How to traverse circle coordinates?

The problem I have is: Fill a circle by drawing one-pixel-wide horizontal lines across its inside area. My initial thought is to generate the circles' coordinates symmetrically to a vertical ...
1
vote
2answers
33 views

Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull)

In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-Rectilinear Convex Hull of a given point set in plane. In ...
3
votes
1answer
177 views

Given 3 random points, what is the probability of these two situations involving a perpendicular bisector and distances?

Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, ...
0
votes
1answer
31 views

Normal to a set of integer vectors

Given a set of $i$ integer vectors resting in $d$ space (with $i$ < $d$), how do you find a normal to the set of vectors while keeping all of the computations in $\mathbb{Z}$?
0
votes
0answers
98 views

how to compute horizontal angle of a pixel from a computer vision camera

My program needs to compute the angle of a pixel from a computer vision camera that has 120 degrees horizontal field of view, and resolution of 640 pixels wide and 480 pixels high. Program receives ...
0
votes
0answers
20 views

Finding the initial facet in giftwrapping

I'm struggling to understand how to find an initial facet via the giftwrapping algorithm. I understand that you start by taking a vertical hyperplane $H_1$, and seeing what point(s) it hits first on ...
0
votes
1answer
269 views

Rotations of a cube

I am trying to create a program using Python 3 which must simulate the rotations of a cube. However, I am struggling to figure out how to rotate that cube. I have the following formulas: ...
3
votes
3answers
121 views

Shortest path in a maze

There is a maze, which is nothing but made of $2$ parallel polylines, which looks like a zig-zag road. We have to find the shortest path between the entrance and exit. Any ideas on how to proceed? ...
3
votes
1answer
149 views

Maximum Side of a Square Dissected into Rectangles

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set $\{1,2,3,4,5,6,7,8,9,10,...
2
votes
1answer
75 views

segment intersecting a tetrahedron

I am trying to write C++ code to find the intersection points of a segment intersecting a tetrahedron. I reduced the problem like this: For each face of the tetrahedron (a triangle), find the ...
2
votes
2answers
42 views

Proof of correctness of a formula for the area of a polygon

Let $P$ be a $n$-gon with vertices $(x_1,y_1),\ldots,(x_n,y_n)$ enumerated clockwise. Then the area $\text{Area}(P)$ of $P$ is $$ \text{Area}(P) = \sum_{i=1}^n\frac{1}{2}(x_{i+1}-x_i)(y_{i+1}+y_i).$$ ...
2
votes
0answers
77 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
78 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
1
vote
1answer
108 views

Total number of lines in a 2D grid

I have a 2D grid of $M \times N$ points. I need to find the total number of lines (not line segments) passing through these points including the diagonals. For example: $M=2,N=2$: Number of lines $= ...
0
votes
0answers
30 views

Extension of Isovist concept for a point - to Isovist for a polygon

There is the concept of Isovist/Visibility polygon. They both talking about volume of space visible from a given point in space. My question: What is the algorithamic solution of this problem for a ...
1
vote
1answer
81 views

What is an offset bisector in 2D polygon skeletonization?

I'll be referring to the definition of the offset bisector from the definitions section of CGAL's 2D Straight Skeleton and Polygon Offsetting module. The halfplane to the bounded side of the line ...
0
votes
0answers
16 views

Integrate gaussian over general simplex

I need to compute the volume of an $n$-dimensional simplex where some dimensions are distributed uniformly and some normally. Can this be approximated well in polynomial time?
-1
votes
1answer
49 views

How can I find an algebraic formula to test whether two line segments intersect or not?

Suppose, $AB$ and $CD$ are two line segments. And, they have slopes $m_1$ and $m_2$ respectively. They will intersect with each other if, $m_1 \ne m_2 .$ Suppose, $A(x1, y1); B(x2, y2); C(x3, y3); ...
1
vote
1answer
50 views

How many techniques are there to test collinearity of $n$ points?

How many techniques are there to test coliniariry of n points? For example, suppose we have 4 points A, B , C, D. How many ways can it be tested that they are collinear? This answer lists 03 ...
1
vote
1answer
29 views

What is the name for the image form you get you take a line segment and sweep it through a region of space?

For instance, if you were to take a line segment and translate it along a coplanar path, then you'd get a plane. If the path is cyclic and on that path you rotate the line segment on the axis ...
1
vote
1answer
93 views

Determining the position of a polygon inside a circle from only the angle of opposing sides/edges.

For illustration click here I have a simple convex irregular polygon (octagon in example image) inside a circle (circle and polygon are not always concentric and never touching or intersecting) and I ...
1
vote
1answer
56 views

differentiating an integral with respect to a variable which also affects the region of integration

I am considering taking the derivative of the function $$F(\mathbb{x_1},\mathbb{x_2},\mathbb{x_3}) = \displaystyle \int_{V_1} ||x-\mathbb{x_1}||\phi(x)\,dx + \int_{V_2} ||x-\mathbb{x_2}||\phi(x)\,dx +...
3
votes
0answers
44 views

'Unrolling' the neighbourhood of a space curve

I have a space curve $\gamma : \mathbb{R} \longrightarrow \mathbb{R}^3$, sampled at $n$ discrete points. I have implemented an algorithm that gives me an approximation to $\gamma$'s tangent, normal ...
2
votes
1answer
65 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is $\frac{s}{2\sin(\...
1
vote
0answers
49 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
4
votes
2answers
122 views

Box-Counting Dimension with finite resolution

Does the method of determining dimension of a shape via the Box-Counting dimension (Minkowski–Bouligand dimension) have to be performed on fractals (objects that look the same at all scales), or can ...
5
votes
0answers
56 views

Reconstruct polyhedron from sections

There is a convex polyhedron $P \subset \mathbb{R}^{3}$ and there are its planar sections $S_{1}, \ldots, S_{n}$ througth planes $\pi_{1}, \ldots, \pi_{n}$, $S_{i} \subset \pi_{i}$. All these $S_{i}$ ...
0
votes
1answer
49 views

equation of a cylinder jacket

how would you calculate this? A circular cylinder, height $14$, base radius $2$, has the axis of rotation! What is the equation of the cylinder jacket when the center of the base circle is the ...