Questions tagged [computational-geometry]

is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.

Filter by
Sorted by
Tagged with
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 ...
Mpsteve137's user avatar
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 ...
cdupont's user avatar
  • 1,158
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 ...
eln05's user avatar
  • 51
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) ...
noname 's user avatar
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 ...
Impresario_2244's user avatar
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=...
Makogan's user avatar
  • 8,287
-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). ...
somerv's user avatar
  • 9
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 ...
Aman Yadav's user avatar
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, ...
Nguyễn Anh Bình's user avatar
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 ...
Ans shakeel's user avatar
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 ...
Nekomiya Kasane's user avatar
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 ...
CKJ_1630's user avatar
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 ...
senseiwa's user avatar
  • 2,369
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 ...
sodiumnitrate's user avatar
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 ...
Xiaoqing Li's user avatar
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 ...
ShoutOutAndCalculate's user avatar
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 ...
TheDeafOne's user avatar
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, ...
matanster's user avatar
  • 15.1k
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 ...
Nekomiya Kasane's user avatar
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 ...
Nekomiya Kasane's user avatar
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 ...
Augen Pupillen's user avatar
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 ...
dimflix 123's user avatar
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 ...
sneha_jerin's user avatar
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 ...
Steve Scott's user avatar
  • 1,451
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 ...
Prakhar's user avatar
  • 49
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 ...
Vitor Fernandes Reis's user avatar
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 ...
user1832084's user avatar
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,...
user3384674's user avatar
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 ...
Bug's user avatar
  • 13
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 ...
J. M. Aziz's user avatar
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 ...
yosmo78's user avatar
  • 487
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 ...
mattscooter's user avatar
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 ...
fisch's user avatar
  • 23
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 ...
nickponline's user avatar
  • 25.4k
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 ...
bihariforces's user avatar
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 ...
Hello's user avatar
  • 11
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 ...
A. Roy's user avatar
  • 366
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 ...
nickponline's user avatar
  • 25.4k
-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 ...
Joe Smith's user avatar
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 ...
kil47's user avatar
  • 53
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 ...
Jason Boyd's user avatar
  • 1,202
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 ...
deepjyoti7147's user avatar
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),(...
mmj's user avatar
  • 5,544
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 ...
Xiutecuhtli's user avatar
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 ...
Magno C's user avatar
  • 1,922
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/...
orematasaburo's user avatar
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 ...
yrneh's user avatar
  • 1
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 ...
efish's user avatar
  • 1
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 ...
Koy's user avatar
  • 506
-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 ...
nazgooolll Zkh's user avatar

1
2 3 4 5
55