The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.

learn more… | top users | synonyms

3
votes
1answer
44 views

How to Check a Hyper-Cube for Defects

I would greatly appreciate some help/references on solving the following problem: You are in charge of searching through a n-dimensional hyper-cube $[0,1]^n$ to make sure that it does not contain ...
0
votes
0answers
28 views

Help with the definition of constraints for a joint optimization problem

A trajectory is piecewise defined by the following polynomial form: $$ f(t) = a + bt+ct^{2}+dt^{3}+et^{4}+ft^{5}+gt^{6}+ht^{7}+it^{8}+jt^{9} $$ for every single segment composing the trajectory (the ...
0
votes
3answers
73 views

Meshing of polygons

I need to generate a sequence of increasingly denser high-quality triangular meshes for some pentagons in MATLAB. I want to supply as my input The coordinates of the 5 vertices of the pentagon ...
0
votes
1answer
74 views

Convex Polygon Intersection

Determining the intersection of two convex polygons is one of the fundamental problems in computational geometry . I'm asking for an algorithm having: INPUT: Given two convex polygons P and Q in 2D ...
1
vote
2answers
72 views

How to determine the support/influence domain for irregularly distributed nodes in the Element-Free Galekin Method?

EDIT (26-12-14):In the Belytschko's EFG code, the domain of influence for uniform distributed node can be calculated using the code below; my question is how to calculate xspac and yspac when the ...
1
vote
2answers
80 views

Determine unit outward normal vector for a curve

It is necessary for me to find the unit outward normal vector for the curve: $$\gamma=(x(t),y(t)) $$ where $$x(t)=\cos(t)−0.5\cos(3t)$$ and $$y(t)=\sin(t)+\sin(7t)+\sin(3t)$$ I know how to find ...
3
votes
2answers
135 views

How to determine a node is outside or inside a curve

Let $$x=0.5\cos(t)-0.3\cos(3t)$$ $$y=1.2+0.6\sin(t)-0.07\sin(3t)+0.2\sin(7t)$$ How could I know an arbitrary point is inside or outside of this curve? Also, another ...
0
votes
0answers
36 views

Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
3
votes
1answer
50 views

Riemann surfaces: computing $f(z) = \int_0^z \frac{dx}{\sqrt{P(x)}}$

I am trying to validate that the Schwartz-Christoffel mapping does indeed take the upper-half plane $\mathbb{H} = \{ z: \mathrm{Re}(z) > 0\}$ to a polygon. This involves integrals of functions ...
3
votes
1answer
59 views

Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
2
votes
2answers
52 views

Finding nearest neighbors using Jaccard distance for positive, real-valued vectors

Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance $d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$ to find ...
6
votes
2answers
341 views

A method to determine whether a point can be contained within a circle with no neighbouring points

I have been working on a particularly challenging problem and was hoping for some guidance. Here is my problem. I have a point cloud containing millions of points. For each point in the set, I need to ...
2
votes
1answer
109 views

What is the exact formulation of compressible Euler equation of gas dynamics in polar coordinates with artificial diffusion in 2D?

The interested equation is advection-diffusion equation. One of the canonical example is Navier-Stokes equations. However, I would like to let the coefficient of diffusion constant goes to zero, ...
1
vote
1answer
132 views

Translate a 3D point along a heading

I need to translate a point (P1) in 3D a certain amount, call it stepSize, along a vector described by a heading composed of ...
1
vote
1answer
47 views

Speedier alternative to “skimage.morphology._pnpoly import points_inside_poly”?

I am using scikit-image's points_inside_poly function, and in my code I am calling it enough times that it takes up about 50% of ...
1
vote
1answer
57 views

Integer simplification of irrational inequality

I'm doing work in computational geometry where the robustness of the algorithm is important. On two separate occasions now have I come across a scenario where I compare the numerical size of two ...
2
votes
1answer
172 views

Unwrap cylinder to plane in Paraview

I want to extract the data from the boundary surface of a cylinder (in a .vtu file) and plot it onto a plane, where the coordinates are theta (rotation angle) and ...
1
vote
0answers
42 views

Algorithm for merging mesh with cad file

I am writing the pre processing program for a porosity based cfd project we just started. Basically I have a 3 dimensional mesh made of cubes and I need to import a STL file over it, and calculate how ...
0
votes
1answer
65 views

difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial ...
0
votes
0answers
33 views

Algorithm for porosity based CFD mesh

I am writing the pre-processing program for a porosity based CFD project. I have a mesh made of cubes, and need to import an object (a stl file: triangular mesh, not solid) over it. The cubes will ...
0
votes
0answers
13 views

Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not. Which software would you suggest for rigid transformations? Thank you
0
votes
0answers
35 views

Convex hull and cartesian Product

Under which conditions, the cartesian product of some closed and bounded polytopes is equivalent to their convex hull?
3
votes
0answers
42 views

How do you mesh and re-mesh a surface (2-manifold) in 4D?

For ease of explanation, suppose that you began with a two-dimensional surface in (x1, x2, x3, x4)-space, and the surface begins as a flat planar region in the (x1, x2)-plane. The boundaries of this ...
3
votes
3answers
134 views

Surface integration over a portion of an ellipsoid

I would like to perform a surface integration over a portion $D$ of an ellipsoid. A plane arbitrarily intersects the ellipsoid forming two sections, of which one is $D$. I do not know how I can ...
1
vote
0answers
58 views

NURBS surface fitting for a closed region on mesh

I'm developing a tool that allows users to select a closed boundary (a polygon) on the triangle mesh and then from this boundary, generate a NURBS surface fitting the original mesh surface. My idea ...
1
vote
1answer
68 views

Number of faces in a 3D multi-type unstructured grid

Given a 3D unstructured grid consisting of mixed types of shapes (hex, tet, ...), is there a method to know how many faces (including boundary faces) are contained in the grid?
2
votes
1answer
77 views

Mesh with constraints

Is it possible to construct a constrained tetrahedral mesh of a domain using Tetgen or similar software? What I mean by constrained is that there are some nodes or edges that are not free but are ...
2
votes
1answer
210 views

area of voronoi cell

I have a Voronoi diagram that I need to calculate the area of each cell. This Voronoi diagram is produced by Voronoi command in MATLAB. To find the vertices of the Voronoi cell I use ...
4
votes
2answers
46 views

Fitting a surface to scalar functions given on the edges of a triangulation

Given a triangle mesh $\mathcal{T}$ with vertices $V=\{\mathbf{v}_i\}_{i=1}^n$ in $\mathbb{R}^3$ and triangles $T_{ijk}=[\mathbf{v}_i, \mathbf{v}_j, \mathbf{v}_k]$. For each vertex $\mathbf{v}_i$, I ...
2
votes
0answers
74 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is ...
4
votes
2answers
135 views

K-nearest neighbours search in subspaces of a high-dimensional space

I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional ...
2
votes
1answer
74 views

Algorithm to equalize the area of random tessellation of various polygons

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
4
votes
3answers
103 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
54 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...
3
votes
2answers
265 views

Best incremental multidimensional Delaunay tessellation algorithm

I'm looking for a specific type of Delaunay tessellation algorithm. The algorithm should be: incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex ...
5
votes
1answer
153 views

Finding closed equipotential surfaces on a 3D grid

In short, I'm looking for either: (1) Publications or other sources dealing with contour/isosurface finding algorithms, so that I can write my own implementation (and parallelize as best I can), or ...
2
votes
1answer
58 views

The closed form solution of a point on a plane

Given a plane in 3D Euclidean space is $\pi$: $ax+by+cz+d=0$ and a point $P$:$(X,Y,Z)\in \mathbb{R}^3$. Find a point $Q:(X^*,Y^*,Z^*)\in \pi$ such that: $$Q= ...
3
votes
1answer
77 views

Extract 3D lower hull from convex hull

For my problem I need to extract the lower convex hull of a set of 3D points (X,Y,Z). In Matlab, one can find the convex hull using the convhull function as follows: K = convhull(X,Y,Z). Could ...
3
votes
0answers
33 views

Auto labeling algorithm [closed]

I have a set of points (2D space), and for every point there's a label (like city names on a map). I want to find a real-time algorithm that allows labels to avoid overlapping, moving them from their ...
2
votes
2answers
125 views

How can I generate shell elements to a mesh

I have a program that generates mesh for given 3d models. The generated mesh must use quadrangle elements. It is required to add "shell elements generation capabilities". The requirement is as ...
3
votes
1answer
103 views

how to do geometry clean up in paraview? [closed]

I have a vtk file which has a bunch of points, I would like to delete a few points because, those distort my geometry (basic geometry clean up), is there a way I can do it in paraview? I just want to ...
1
vote
1answer
75 views

Inclined plate capacitor grid/ mesh

You can calculate the electric potential over every point in a defined space by solving Laplace's equation. To do this in a computer program you set up an 2-d array/ matrix and loop the internal ...
0
votes
1answer
749 views

Vertical and horizontal segments intersection (Line Sweep)

Introduction: I have a vertical segment S That i want to move across a plane (Left --> Right), and find intersections with horizontal lines. Problem : The problem which i am having is the ...
0
votes
1answer
117 views

Line segment straddle

What is exactly the definition of "Straddle"? Can you please explain what do they mean exactly or a sketch? A segment P1P2 Straddles a line if point P1 lies on the one side of the line and point P2 ...
1
vote
0answers
64 views

How can i find the coordination number with voro++?

Could anybody please help with voro++ cause i am new to this software?My problem is how can i find the coordination number of an atom ,cause i checked it for a bcc lattice and it gave me 24 for all ...
5
votes
4answers
162 views

Computational science contests. Why arent there any?

I was wondering why there are no online or offline computational science contests? At least I couldn't find much by googling. I mean, like a topcoder for computational sciences. I assume one reason is ...
2
votes
1answer
65 views

Equal Area Sampling on Curved Surface:

I have a quantity $\beta(\mathbf{x}) \in \mathbb{R}$ that I wish to compute on a curved, smooth surface defined by $\{\mathbf{x}: \Gamma(\mathbf{x})=0\} \subset \mathbb{R}^{3}$. (This surface is ...
1
vote
0answers
53 views

Environment for implementing/testing Computer Graphics algorithms [closed]

I need to code up a computer graphics algorithm for Surface Registration. Briefly surface registration is the process of finding "optimal" one-one correspondence between surfaces, where the meaning ...
7
votes
3answers
699 views

Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
1
vote
0answers
202 views

MATLAB Detection of the point where regions meet

A totally beginner here. I've read all the coordinates of nodes of a face from the corresponding file into an [X Y Z] array and displayed as a mesh. The top-most node of the nose i.e. the tip of the ...