Computational Geometry

computational-geometry

Great Reads

Magic Formula of the Intersection Point of Two Line Segments

by Petrov Vladimir

Compact and simply Vector Formula of the Intersection Point of Two Line Segments

Generation of a hexagonal tessellation

by LLLLGGGG

In this article, I am going to explain how to generate a hexagonal tessellation and how to draw it in Unity 3D

Geometric Primitives for OpenGL

by Steffen Ploetz

Box, cylinder, cone and sphere construction for OpenGL with texture and light effects

Parametric Curves and Surfaces in the Public Domain Geometry Utilities Library

by Peter Occil

Describes parametric curves and surfaces and how to generate them using my public-domain HTML 3D library

Latest Articles

Geometric Primitives for OpenGL

by Steffen Ploetz

Box, cylinder, cone and sphere construction for OpenGL with texture and light effects

Magic Formula of the Intersection Point of Two Line Segments

by Petrov Vladimir

Compact and simply Vector Formula of the Intersection Point of Two Line Segments

Parametric Curves and Surfaces in the Public Domain Geometry Utilities Library

by Peter Occil

Describes parametric curves and surfaces and how to generate them using my public-domain HTML 3D library

Generation of a hexagonal tessellation

by LLLLGGGG

In this article, I am going to explain how to generate a hexagonal tessellation and how to draw it in Unity 3D

All Articles

top

Computational Geometry

Magic Formula of the Intersection Point of Two Line Segments

5 Dec 2019 by Petrov Vladimir

Compact and simply Vector Formula of the Intersection Point of Two Line Segments

C++14

C++

Win7

Win10

WinXP

MFC

computational-geometry

Generation of a hexagonal tessellation

25 Jun 2018 by LLLLGGGG

In this article, I am going to explain how to generate a hexagonal tessellation and how to draw it in Unity 3D

Unity3D

Dev

computational-geometry

Geometric Primitives for OpenGL

9 Mar 2021 by Steffen Ploetz

Box, cylinder, cone and sphere construction for OpenGL with texture and light effects

C++

OpenGL

Dev

computational-geometry

Parametric Curves and Surfaces in the Public Domain Geometry Utilities Library

28 Jan 2019 by Peter Occil

Describes parametric curves and surfaces and how to generate them using my public-domain HTML 3D library

HTML

Javascript

computational-geometry

finding point on an ellipse

13 Aug 2012 by Manfred Rudolf Bihy

All you need to solve that is explained rather nicely here: Points of Intersection of an Ellipse and a line[^]. Just rember that a line that goes through the point of origin is inevitably of the form:y = x * aWith a = tan(alpha) with alpha being the angle between the abscissa[^] and the...

C#4.0

computational-geometry

A VB.NET Implementation of the Douglas-Peucker Algorithm without Recursion

21 May 2016 by veen_rp

An add-on tip to articles already posted on Code Project

computational-geometry

Coding challenge: is a point in a polygon?

20 Dec 2016 by Chris Maunder

Today's challenge is late but simple one.Given a set of (x,y) points representing a polygon, determine whether a given (x,y) point is inside or outside the polygon. For example, the polygon defined by the points (counter-clockwise) { (2,0), (4,1), (4,4), (2,5), (1,2) and (2,0) } contains...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

6 Jan 2017 by Kornfeld Eliyahu Peter

For JSOP only :-)IDENTIFICATION DIVISION. PROGRAM-ID. CPCC4-POINT-IN-POLYGON.DATA DIVISION. WORKING-STORAGE SECTION. 01 T1 PIC S9(6) VALUE ZERO. 01 T2 PIC S9(6) VALUE ZERO. 01 T3 PIC S9(6) VALUE ZERO. 01 T4 PIC S9(6) VALUE ZERO. ...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

20 Dec 2016 by Jon McKee

First, I'd like to explain my methodology. Second, I'll explain my code.So first, my technique is similar to the ray-casting algorithm. I double cast a ray in both directions and count the intersections individually then OR them together which allows me to catch points on sides like...

code-challenge

computational-geometry

Find point at specified distance on a straight line

12 Feb 2013 by OriginalGriff

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.Try it yourself, you may find it...

.NET

computational-geometry

Abstract Nonsense in Software Development. Databases

18 Jan 2014 by Petr Ivankov

Application of abstract approach to database domain

Finding centre of the Arc

3 Jul 2014 by YvesDaoust

The start-end vector together with the normal direction allow you to compute the direction of the line perpendicular to the chord in the circle plane.r = SE/||SE|| /\ nMake it pass through the midpoint.M = 1/2(S + E).By Pythagoras, you will find the altitude of the triangle...

computational-geometry

mathematics

What is an efficient algorithm to find total area of two region which is overlapped

3 Mar 2015 by Sergey Alexandrovich Kryukov

I like the problem, it is pretty funny purely algorithmic problem, not very much of programming. But you are supposed to be the author of the solution, which looks like a home assignment. Therefore, let's do this: I though just a bit at it and came to a pretty interesting simple idea. I'll share...

computational-geometry

algorithm

What does it indicate if slope of line 1 is less than slope of line2 and vice versa?

23 May 2015 by Sergey Alexandrovich Kryukov

The question makes no sense, by the following reason: if you have two straight lines, you can always characterize their slopes, but you can compare them to tell which is greater only if you tell the coordinate system for comparison.Say, if you have to vectors in X-Y coordinates, you can...

computational-geometry

algorithm

Why are slopes of lines compared for the below solution?

23 May 2015 by Sergey Alexandrovich Kryukov

The question does not make any definitive sense. I explained part of it in my recent answer: What does it indicate if slope of line 1 is less than slope of line2 and vice versa?[^].Even at this level, it seems apparent that continuing this discussion does not make much sense.You...

algorithm

computational-geometry

programming

Coding challenge: is a point in a polygon?

16 Dec 2016 by Ramza360

Adding another example using most of what OriginalGriff wrote except no foreach loop.public class TestPoints { GraphicsPath path; public TestPoints(Point[] points) { path = new GraphicsPath(points); } public bool CheckVisible(int x, int y) { ...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

16 Dec 2016 by Thomas Daniels

Time for some maths! My code uses the ray casting algorithm: it looks at how many times a ray, starting from the given point to whatever direction, intersects with the polygon. If this number is odd, the point is inside the polygon. If it's even, the number is outside the polygon./*...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

16 Dec 2016 by Marc Clifton

If you allow me an extension method so I can get fluent coding: public static class GPExt { public static GraphicsPath AddPolygon2(this GraphicsPath gp, PointF[] points) { gp.AddPolygon(points); return gp; } }I can...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

5 Jan 2017 by Peter Leow

Picked out this new mission while waiting for my flight home. One look and this is going to involve geometry, that means Cartesian coordinate system, vectors, edges, and angles sort of things. To kill time, I started drawing out my thought on the phone... There are three ways to solve this...

code-challenge

computational-geometry

Draw polygon with innerRing.

30 Jan 2013 by gilvani

The problem is the following.I have 2 arrays of points. In a graphics I need to paint the polygon (array 1) without painting the inside (array 2), As this...

computational-geometry

graphics

Draw polygon with innerRing.

30 Jan 2013 by gilvani

hello, I found the solution.In graphics I changed the CompositingMode that determines when to paint a polygon on the other it is overwritten and not superimposed.Bitmap img = new Bitmap( 200, 200 );Graphics imgGraph = Graphics.FromImage( img );imgGraph.CompositingMode =...

computational-geometry

graphics

Geometry shader with stream output

11 Feb 2013 by IDominator

Hi folks, I've been trying to generate shadow volumes with the gpu.But can't get the geometry shader to produce output.So how can I create a shader with stream output in slimdx? Can someone give me an example with code in hlsl and slimdx?Edit:@ CHill60here's some...

.NET

DirectX

computational-geometry

HLSL

stream

Find point at specified distance on a straight line

12 Feb 2013 by Anurag Sinha V

Hi,Let us talk in some simple terms.There are 2 points (x1,y1) and (x2,y2) and you need to find a point in between these above points which is at a distance z from the first point.I think you will have to provide the distance between (x1,y1) and (x2,y2) also, coz after that the number of...

.NET

computational-geometry

Find point at specified distance on a straight line

12 Feb 2013 by lukeer

Let's assume you have written an extremely useful library for co-ordinate manipulation, which includesPointF Add(PointF p0, PointF p1)PointF Sub(PointF p0, PointF p1)PointF Multiply(PointF p0, float factor)PointF Multiply(float factor, PointF p0) // Commutativeness is not for freefloat...

.NET

computational-geometry

Python or Java Program to find Slope and intercept of a line with GUI?

20 Mar 2013 by Joshi Kumar AV

I am trying to write a program that calculates the slope and intercept of series of points and plot it in a graph using line fitting algorithm. I want to develop this program into a stand alone exe file to run independently. Please guide me how do I go about?I did do my homework trying to...

Python

computational-geometry

graphics

Matrix3 -> Quaternion & Quaternion -> Matrix3 (must support reflection)

6 Aug 2013 by Dusan Paulovic

Hello, do you know about any robust library which supports conversions between rotation matrix and quaternion? I have found any using google, but these does not support reflections.Also it should be able to ortho-normalize rotation matrix. Thanks in advance.

C++

mathematics

computational-geometry

how to draw with Path Markup Syntax /Geometry a figure in c#-WPF

28 Oct 2014 by Kinna-10626331

Hi ,as a test I am adding as background of a Grid column a DrawingBrush element which using PElipseGeometry draws something similar a strech ellipse.Here is the code: ...

C#5.0

XAML

computational-geometry

path

drawing

how to draw with Path Markup Syntax /Geometry a figure in c#-WPF

30 Oct 2014 by AeroClassics

Make you map using Adobe Illustrator or Photoshop. Then import the file into Blend. When it is imported you will see all the Path Objects with data. Copy these into you XAML file and use them.I do this when adding glyphs to my buttons.Doug

C#5.0

XAML

computational-geometry

path

drawing

What is an efficient algorithm to find total area of two region which is overlapped

2 Mar 2015 by Member 11380284

My situation Input: a set of rectangles each rect is comprised of 4 doubles like this: (x0,y0,w,h) they are not "rotated" at any angle, all they are "normal" rectangles that go "up/down" and "left/right" with respect to the screen they are randomly placed - they may be...

computational-geometry

algorithm

Exponential map algorithm gives bug in case of sphere, need solution to fix issue

18 Mar 2015 by Member 9977262

I am trying to decal sketch on mesh using exponential map. While generating exponential map, I am calculating plane by initial point on mesh and normal calculated on mesh by that point. then algorithm calculates nearest vertices from that point and traverse to them by edges.Then Edges are...

C++

computational-geometry

AutoCAD

How Can I Find Angle Of A Pentagon

10 Jun 2015 by Fredrik Bornander

Right, two answer this I am going to make the assumption that the following is know;All the lengths of the five sides of the pentagon.Two angles between segments, these need to be adjacent angles.Let's assume a pentagon going through the 5 points A, B, C, D and E.The length from A...

computational-geometry

Coding challenge: is a point in a polygon?

16 Dec 2016 by OriginalGriff

Well ... you could just use standard framework methods:Point[] points = new Point[] { new Point(2, 0), new Point(4, 1), new Point(4, 4), new Point(2, 5), new Point(1, 2), new Point(2, 0 ) };GraphicsPath path = new GraphicsPath();Point last = points[0];foreach (Point p in points) {...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

16 Dec 2016 by Duncan Edwards Jones

If I recall you take an imaginary line from your point (x,y) to (xMax,y) and check if each of the vertices crosses it. If the number that crosses is even you are outside the polygon (inclusive of 0) otherwise you are inside the polygon.

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

19 Dec 2016 by Patrice T

Here is my submission.Looks like I took a little original approach. I guess the method is known but I have no clue about it. The method works with clockwise and non clockwise polygons, convex or not.First I move the polygon as if the testing point was {0,0}.Then I compute the angle covered...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

19 Dec 2016 by Niklas L

Abusing Chris' generosity regarding data type, I made a solution which has rather nice runtime complexity :p#include #include #include using namespace std;class point{public: bool x, y; point(bool _x, bool _y) : x(_x), y(_y) {} bool...

code-challenge

computational-geometry

Coding challenge: is a point in a polygon?

20 Dec 2016 by CDP1802

using System;using System.Collections.Generic;using System.Windows.Media.Media3D;class Program{ public static bool TestPointAgainstPolygon(List Polygon, Vector3D TestPoint) { Vector3D Normal; int...

code-challenge

computational-geometry

How to get all triangles affected by light or by a set of rays?

8 Feb 2018 by Member 11733943

Hi Everyone! I´m working in an aerial mapping application which tries to determine what part of the terrain is viewed from an aerial camera. First I have rendered DEM (Digital Elevation Model) from existing .tif file, generating all the triangles of the mesh by .tif positions and values. I...

Visual-Studio

computational-geometry

Number of line segment intersection ?

14 Mar 2020 by Patrice T

Quote: Can anyone teach me what approach will be best and most effective in terms of time complexity? The approach is brut force, test very single segment against every horizontal segment. Apply the KISS method a list of N-1 segments, a list of...

Python

computational-geometry

Wpf: how to animate a bezier curve?

26 May 2020 by RickZeeland

See this CodeProject article: A Purely XAML Coded Animated Bezier Curve via WPF[^]

WPF

computational-geometry

animation

Is there any library for WPF that contains electronic components shapes

24 Sep 2020 by DoingWork

Is there any library for WPF (XAML code) that contains Shapes or Geometries of Electronic Components like Fuse, Transformer, Wire, Resister, Diode and etc What I have tried:

XAML

WPF

Visual-Studio

computational-geometry

Is there any library for WPF that contains electronic components shapes

24 Sep 2020 by Dave Kreskowiak

Probably doesn't exist. You're best source for component outlines is probably going to be for PCB layout software like Eagle. That have large numbers of libraries of components that have outlines for the device itself as well as pad layout and...

XAML

WPF

Visual-Studio

computational-geometry

I want to convert visio shapes to path data to use in xaml (WPF)

30 Sep 2020 by Gerry Schmitz

You're not "reinventing the wheel" when your only other alternative is to "buy" the wheel. That's what commerce and trade are all about and why I don't make my own shoes. And if it was that easy, there comes the question of "fair use": MS could...

XAML

WPF

Visual-Studio

computational-geometry

Abstract Nonsense in Software Development Outlook

10 Dec 2013 by Petr Ivankov

Multidisciplinary paradigm of software development

Coding Challenge: Smallest Circle Problem

11 Jan 2017 by Kornfeld Eliyahu Peter

Think algorithm...

computational-geometry

code-challenge

mathematics

C++ 2D Game Engine (Novice to Novice) - Part 1

4 Apr 2015 by BrainlessLabs.com

In this tip series, we will create a small C++ game engine.

computational-geometry

game

Interactively Add Multiple Shapes Using Linked Lists GDI+ SVG

3 Mar 2016 by The Zakies

Tutorial 2 (how to interactively add multiple shapes GDI using linked lists)

finding point on an ellipse

6 Sep 2012 by ravithejag

http://math.stackexchange.com/questions/96750/how-to-get-the-x-y-point-with-a-given-angle[^]

C#4.0

computational-geometry

Can a WPF Custom control use the Background Brush of the control's container.

17 Jan 2016 by cmbay

I am creating a WPF Custom Control Template and I would like one of the GeometryDrawing Brushs to use the Background Brush of the control's container. For example if I put this control on a Window I would like this particular Brush to use the Window's Background Brush. Like wise if the control...

WPF

templates

drawing

computational-geometry

custom-controls

How to get all triangles affected by light or by a set of rays?

8 Feb 2018 by Rick York

There are tons of research papers written on this topic or relatives of it and there are several tactics used. One of the most common is subdividing the mesh and checking each division. Generally this is done by dividing the mesh in quarters and doing a hit check on each quarter and then for...

Visual-Studio

computational-geometry

2D Drawing - Doc/View architecture

20 Jul 2012 by Sunil P V

This article is a simple geometry library for drawing lines, circles, arcs, text, etc.

VC10.0

C++

MFC

computational-geometry

drawing

Spiraling Twisting Polygons and Roses

30 Jan 2018 by Voevudko A. E., Ph.D.

Presenting one kind of the exotic spiral, i.e., using big round dots, twisting polygons and, possibly, your own photo. Offering web-page used to illustrate different aspects of it.

computational-geometry

graphics

Can a WPF Custom control use the Background Brush of the control's container.

18 Jan 2016 by Sergey Alexandrovich Kryukov

cmbay asked:…So the question is, is it possible to bind the Background of my control to its' container's background without explicitly identifying the container.It can be done by binding using RelativeSource. Please see:RelativeSource Class (System.Windows.Data)[^],C# Corner:...

WPF

templates

drawing

computational-geometry

custom-controls

What is an efficient algorithm to find total area of two region which is overlapped

2 Mar 2015 by Praneet Nadkar

Hi,Have a look at the examples and the discussion going here:http://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles[^]Hope this helps !! :)

computational-geometry

algorithm

Finding centre of the Arc

29 Jun 2014 by Madhan Mohan Reddy P

I Have arc start point, end point, radius and normal direction.With this data how to find arc centre point in 3D coordinates.Thank You.

computational-geometry

mathematics

finding point on an ellipse

9 Aug 2012 by ravithejag

hi I want to find the point on the ellipse that intersects with an given angle taken from the origin.

C#4.0

computational-geometry

What are the naming rules used in the HOOPS 3D source code?

7 Aug 2013 by sl65agm

I am try to modify the HOOPS 3D source code to satisfy the demand of occlusion culling of large amount of triangles, for the reason that the dx9 driver can not discard triangle primitives in its render pipeline. So I have to figure out the render process of the platform by reading its source...

computational-geometry

rendering

graphics

Find point at specified distance on a straight line

12 Feb 2013 by pvt_infotech

HI All,i have two points (x1,y1) and (x2,y2). I want to know the point which lies at specific distance from the first point(x1,y1) assuming a straight line between above two points.for suppose, if i say 10 meters distance, then the output point should be on the same straight line of...

.NET

computational-geometry

How can I avoid intersecting triangles in regular triangulation?

11 Jul 2014 by phpdna

It gives me intersecting triangles with a regular triangulation. I have 2 questions a) is this possible? b) How can I remove intersecting triangles? Question a) Seems to me logical with human sense but what is with question b)? Is there a library that can do regular triangulation with any...

computational-geometry

How can I avoid intersecting triangles in regular triangulation?

23 Jul 2014 by phpdna

I think it's a programming question. Anyway I think I solved the problem.

computational-geometry

Infinity edges with n-dimension delaunay triangulation?

23 Jul 2014 by phpdna

I wonder how I can see the infinity edges with the n-dimension delaunay triangulation. ATM I use the incremental bowyer-watson algorithm with infinity edges but how to do this with the n-dimension solver, i.e. when you project the points onto a paraboloid?

computational-geometry

Empty regions in power diagram how is it useful?

10 Aug 2014 by phpdna

Sometimes there is empty regions in power diagram. It looks like some regions are smaller compared to the normal Voronoi diagram? How is this possible and how is this useful? Here is an example:http://groups.csail.mit.edu/graphics/classes/6.838/F01/lectures/MedialAxisEtc/presentation/13.html[^]....

computational-geometry

Check Whether the lat,Long is inside boundary of list of lat longs

29 Oct 2014 by Vijay m. parmar

i am Working on an Application in that i have to know that the given latitude and longitude is inside of given range of latitude and longitude.for example i have multiple lat,long of an area now i put a single lat,long. and application check that the single lat,long in inside of given range...

C#3.5

geolocation

computational-geometry

How to use math formulas with javascript?

6 May 2016 by Member 12508138

I created a program located at http://www.ptrone.com/ Where changing the value of z tocos(point)*120+120Creates a circle that is rotating in a circular motion. Can anyone tell the formula to create a triangle that rotates in a circular motion?What I have tried:cos(), sin(), exp()...

HTML

Javascript

mathematics

computational-geometry

Matrix

calculus

How to use math formulas with javascript?

6 May 2016 by Karthik_Mahalingam

use Math object refer: JavaScript Math Reference[^]JavaScript Math Functions[^]JavaScript The Math Object[^]Math Object (JavaScript)[^]example:var value = Math.cos(25);alert (value);

HTML

Javascript

mathematics

computational-geometry

Matrix

calculus

Number of line segment intersection ?

14 Mar 2020 by Member 14773225

You are given N points in a plane (numbered 1 through N); for each valid i, the i-th point is Pi=(i,Ai). There are N−1 line segments between them (numbered 1 through N−1); for each valid i, the i-th line segment is formed by connecting the points...

Python

computational-geometry

Wpf: how to animate a bezier curve?

26 May 2020 by Member 12618031

Using the following code, I get a circle or arc drawing effect. using Microsoft.Expression.Shapes; Arc a = new Arc(); a.ArcThicknessUnit = Microsoft.Expression.Media.UnitType.Pixel; a.ArcThickness = 10; a.StrokeThickness = 1; a.Fill = new...

WPF

computational-geometry

animation

I want to convert visio shapes to path data to use in xaml (WPF)

30 Sep 2020 by DoingWork

I want to convert Visio Shapes to Path Data. Then I want to use these path data in Xaml (WPF) If I spend my time on re-inventing the wheel, it will take too much time Any Help ? What I have tried: I have spent very large time on Shapes and...

XAML

WPF

Visual-Studio

computational-geometry