Questions tagged [computational-geometry]
is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
2,744
questions
0
votes
0
answers
20
views
When building a world in square mesh chunks, is there a way to blend varied height mulitpliers so chunks' edges line up?
I am working on a procedurally generated world. The world is built in mesh chunks. Each chunk has its own height multiplier that is used to set the heights of the vertices. However, as having ...
2
votes
0
answers
50
views
Trajectories with collisions... And plasma guns
I'm creating a game with plasma guns:
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 ...
0
votes
0
answers
30
views
Single threading to Multithreading in the middle of a computation, is it possible?
Given the inherent complexity of multi-threaded programming, can we explore the practicality and level of difficulty involved in introducing threads into an already executing code?
For example: Assume ...
0
votes
1
answer
43
views
how to create computational mesh of a geometry with known level set function definition of its boundary
I have a level set function, that defines a "flower like" shape geometry. I want to create a 2D fitted computational mesh around this flower geometry (flower geometry inside a unit square) ...
0
votes
1
answer
41
views
Creating a Tangential Arc between 2 intersecting circles and a known point
I have been struggling with the problem of trying to setout a tangential arc between C1 and C2 through point P. I was hoping to find a method of how to solve this either using math or geometry as i ...
0
votes
2
answers
70
views
SVD decomposition of nalgebra is incomprehensible
I am trying to compute the SVD of matrices, as a toy example I used a vector.
I ran my code:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=...
-1
votes
1
answer
44
views
Best Algorithm For Merging GDS Polygons Close to Each Other
background:
I have GDSII layout with many rectangles all on the same layer. For those not familiar, GDSII is a file format used to store integrated circuit layouts (electronics/photonics/etc). ...
0
votes
0
answers
21
views
I have a oriented bounding box calculated using MathGeoLib. I want to find the orientation of the bounding box in Unity
https://github.com/juj/MathGeoLib
http://clb.confined.space/MathGeoLib/nightly/docs/OBB_summary.php
I have calculated the bounding box for a set of points, I want to create a cube with the orientation ...
0
votes
2
answers
71
views
Identifying Rectangles from a Large Set of Line Segments in Python
Hello StackOverflow community!
I am currently facing a challenge in detecting rotated rectangles that can be formed from a given set of line segments. With a total of approximately 5000 line segments, ...
0
votes
1
answer
44
views
Draw Circular rings around Arc points - VTK UnstructuredGrid
I am trying to create circular rings aroung arc points. I'm trying to create a Cylinderical bend between two points. For this I have done Following:
Draw an ARC between two points. For that, I have 2 ...
0
votes
0
answers
25
views
How to handle degenerate cases in Seidel's Triangulation Algorithm?
I'm trying to implement Seidel's Triangulation Algorithm, and already completed the core logic, which works perfectly for non-degenerated polygon with holes. But I don't know how to preceed to handle ...
0
votes
0
answers
35
views
Trying to find out n equi-spaced points on the boundary of an an ellipse when starting point is given [duplicate]
I have to find out n equi-spaced points on boundary of an ellipse when a (semimajor axis) and b (semiminor axis) are given.
Starting point is considered as (a, 0). The formula given in code is used to ...
1
vote
1
answer
53
views
Computing curvatures with CGAL
I am trying to understand how I can compute the principal curvatures of a SurfaceMesh (and so the gaussian one) using CGAL.
First of all, since I didn't see it, is there any function that computes a ...
0
votes
1
answer
63
views
Finding rotation that match two sets of points
I have two sets of points in 3D, up to 10 points each. Their translations and scales are such that, for both sets, the distance between each point and origin is 1. One set of points should map to the ...
1
vote
1
answer
181
views
open3d | How to calculate the volume of a mesh created by point cloud?
I create a mesh by using 'open3d.geometry.TriangleMesh.create_from_point_cloud_alpha_shape' function and wanted to calculate the volume of it. But a RuntimeError occurs as the following shows:
[Open3D ...
0
votes
0
answers
29
views
Containment algorithms and Convex hull algorithms to check if a point is inside the d dimensional convex hull spanned by n vectors
For n of d dimension vectors, I wanted to check if a d dimension point was inside the convex hall spanned by the d dimension vectors.
There are algorithms to compute the Convex hull algorithms, but ...
1
vote
0
answers
64
views
Rectilinear Polygon Decomposition in Python
I'm trying to find a library that works for decomposing (or partitioning) a rectilinear polygon into separate rectangles. Some libraries such as poly_decomp are for Python 2 and while I was able to ...
3
votes
3
answers
133
views
Numerically stable approach to computing a signed angle between vectors
My first Stack Exchange question regarding numeric stability in geometry. I wrote this function (below) for computing a signed angle from one vector to the other, inspired by the idea presented here, ...
0
votes
0
answers
48
views
How to precisely calculate the intersection point of two almost parallel segments?
I'm currently implementing a sweep-line-like algorithm and need to find the intersection point if 2 line segments (defined by endpoints) are intersected and almost parallel. Since a small error in the ...
1
vote
1
answer
119
views
How to handle edge coincidence and intersection in a trapezoid map?
I'm currently implememting a really general trapezoid map
https://ibb.co/THsqnYz
, and have to resolve the following occasions:
vertex coincidence
edge coincidence (say edge from (0,0) to (0,1) and ...
0
votes
0
answers
27
views
The signed distance from a given point to a 2D slice of a given 3D mesh (for example, obj file)
Given a 3D mesh file (.obj) with a point, make a slice across the point to intersect this 3D mesh to get a 2D slice. How to get the signed distance of this point to this 2D profile efficiently? Is ...
0
votes
0
answers
34
views
Issues when using Möller–Trumbore intersection algorithm to figure out if a vertex is within a shape
I am making a program in C++ that creates a grid of vertices an then imports an stl image. I then use the Möller–Trumbore intersection algorithm on every vertex of my grid to count the number of ...
0
votes
1
answer
70
views
How to find the coodinates of the bounding rectangle from four circles around the vertices of an existing bounding rectangle
I have a bounding box which I have created. I know the lat lon of the four vertices of the box. On these vertices I have created a buffer circle of radius 10m and now I want to calculate a new ...
0
votes
0
answers
42
views
Shrinkwrapping algorithm
I would like to implement a shrinkwrapping algorithm for Rhinoceros 7. I often find myself using the Unified Skin tool in Zbrush to create a single watertight mesh from a collection of overlapping ...
0
votes
0
answers
71
views
How to check if two actors/polyData intersect each other in VTK?
I am a beginner in VTK and want to check for collision/intersection between two vtkActors. I have a list of actors to check intersection within them. I have tried many implementations from the ...
1
vote
2
answers
137
views
Calculate the area of intersection of curves using the Monte Carlo Method in Python
I'm making a list of exercises in which I have the following exercise:
"Use the Monte Carlo method to calculate the area of intersection between the curves given below. For random number ...
0
votes
0
answers
45
views
Algorithm to find the optimal line among 2D - point cloud
I am asking the community after some time trying to find an algorithm that could produce some median/optimal continuous line in a cloud of point as the one there.
I tried this paper's algorithm
Total ...
2
votes
2
answers
93
views
Algorithm to find the shortest connection between two points on a series of cylinder/cone segements & find a specific point on the connection
I have a series of cylinder segments and circular cone segments (cone frustums). The center axes of the cylinder and cone segments are identical with the Z-axis. All segment dimensions (radius, height,...
1
vote
1
answer
67
views
3d triangle approximation with rectangular prisms
I am trying to approximate 3d triangles with rectangular prisms but I cant figure out the math
Im using lua
Ive tried flattening the triangle to a 2d plane and approximating the triangles with normal ...
1
vote
2
answers
71
views
Find smallest partition of intersecting intervals
Given a set of integer intervals SI = {I1,I2,...,In}, I need to find the smallest partition of SI such that all the intervals of a subset of the partition are intersecting.
That is find the smallest P ...
2
votes
2
answers
234
views
I need an algorithm to calculate the outer boundary of a polygon
I have a polygon that can have an arbitrary number of self-intersections defined as an array of boundary points (two consecutive points form an edge in the polygon boundary). I want to calculate just ...
1
vote
1
answer
72
views
Algorithm for generating polygons of land allocation within a defined boundary
We are looking for a solution to create novel land allocations of an existing area into a subset of polygons for each allocation within the existing space.
A high level overview of the requirements ...
2
votes
1
answer
137
views
An algorithm for offsetting multiple polygons without overlaps
Given a list of polygons that are guaranteed to be not intersecting each other (and also guaranteed to not be self-intersecting), I would like to write an algorithm (or use a library) that generates ...
1
vote
1
answer
111
views
How do I differentiate self-intersection vs. self-touching in shapely?
How can I determine if a polygon is self-touching(!) like the blue one, but not self-intersecting like the red one
Vertices for the two polygons shown in the images is here:
from shapely.geometry ...
1
vote
2
answers
110
views
Queries to count points lying on arbitrary line
Suppose we have N points on XY plane, ie. (x, y) and x and y are integers and there are multiple queries where each query is of the form y = mx + c and given m and c where m and c are integers.
Is it ...
0
votes
1
answer
159
views
How can I calculate the Union of rectangles using a divide-and-conquer algorithm in Python?
How to calculate the Union of rectangles? Each rectangle is given as top_left and bottom_right point.
The Union algorithm should be act follows:
Given a set of rectangles, output another set of ...
4
votes
1
answer
97
views
Removing overlap between convex hulls
In two dimensions, we are given two sets of points A and B and their respective convex hulls C_A and C_B. Assume that C_A and C_B overlap.
What is the best algorithm to find the minimal set that must ...
0
votes
0
answers
56
views
What algorithm can simplify a polygon while minimizing changed area and edge lengths?
I would like to simplify polygons so that they look aesthetically pleasing in the following way:
Move edges such that they have only certain inclinations like 0, 45, 90, .. degrees.
Changes edges ...
-1
votes
1
answer
78
views
What is wrong with my Python turtle code that creates a Sierpinski fractal?
import turtle
import random
import math
import time
def is_point_inside_shape(x, y, vertices):
# Use ray-casting algorithm to check if point is inside the shape
num_intersections = 0
for ...
1
vote
0
answers
47
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.
The grids are perfectly stacked horizontally and ...
0
votes
1
answer
49
views
How do you detect the point of impact between a moving circle and a rectangle?
If you have a circle C that is moving at velocity V, how do you calculate the impact point of a collision with rectangle R?
I'm asking this and going to immediately answer my own question in hopes ...
0
votes
0
answers
46
views
How can I generate a straight skeleton of each face of a cube generated by a Python script?
I have a Python script that generates a cube around a set of voxel coordinates stored in a file called plotted.txt. The script looks like this:
from mpl_toolkits.mplot3d import*
import numpy as np
...
0
votes
0
answers
52
views
Split a 2D polyline defined through segments and arcs with Python
I'm looking for a library (preferably in pure Python) or an algorithm able to split, with an arbitrary line, a 2D polyline made of segments and arcs.
The polyline is a sequence of
segments [(x1,y1),(...
0
votes
0
answers
17
views
Cluster of Triangles: Which Can See the Outside?
I have a mesh of triangles that is like the blueprints of a structure, where some triangles represent interior things. I want to isolate just the triangles that form the sort of exterior. The mesh ...
4
votes
0
answers
326
views
Calculating world coordinates of a pixel from a camera picture
Sorry for this question. I know there are many similar questions but I really know nothing about math that involves this case (I'm not a 3D programmer) and those answers are very obscure to me, so I ...
1
vote
2
answers
95
views
surface of mesh cannot be seen from outside, only from inside
Note that this question is not about particular software. Rather, question is about mesh visualization in general.
I have problem in visualizing a mesh file https://gist.github.com/HiroIshida/...
0
votes
0
answers
49
views
3D procedural mesh generation: How do I properly split a tree branch into 2?
Im trying to procedurally generate a tree by recursively running a branch generating function.
The vertices are created floor by floor. When a split occurs I want to create 2 new floors with adjusted ...
0
votes
0
answers
68
views
Finding the markersize/radius of circles, some of which overlap, needed to cover a given percentage of a polygon in Python
I am trying to figure out the markersize needed in python so that the green circles in the attached figure cover a specific percentage, say 20%, of the area bounded by the blue polygon.
The green ...
4
votes
1
answer
111
views
Trouble understanding a constant work-space algorithm for trapezoidal decomposition
I'm looking at an algorithm for trapezoidal decomposition of a simple polygon in constant work-space shown in this paper. (page 51, section 3.2).
The idea of the algorithm is to traverse the polygon ...
-2
votes
1
answer
78
views
How to execute skeleton code on different binary images [closed]
I want to draw the skeleton of the following image, enter image description here I've tried with the following Python code:
usr/bin/env python
# coding: utf-8
# # 2D AOF Skeleton
#This is a jupyter ...