C RUBY-ON-RAILS MYSQL ASP.NET DEVELOPMENT RUBY .NET LINUX SQL-SERVER REGEX WINDOWS ALGORITHM ECLIPSE VISUAL-STUDIO STRING SVN PERFORMANCE APACHE-FLEX UNIT-TESTING SECURITY LINQ UNIX MATH EMAIL OOP LANGUAGE-AGNOSTIC VB6 MSBUILD

# Number of Triangles Containing The Point (0,0)

By : Anchorer
Date : November 22 2020, 10:38 AM
To fix this issue Let there be a triangle with 3 points p1=(x_1,y_1),p2=(x_2,y_2) and p3=(x_3,y_3). Let p1,p2,p3 be the position vectors.If origin lies within, then cross product of any one position vector with other two will be different in sign ( one negative , one positive ). But if origin lies outside then there will be one point which has negative cross product with both the other points. So for each point i find points whose cross product is less than 0.Now if you select any two of these points and make a triangle along with point i , origin will be outside this triangle.Thats why you subtract from res ( selection of 2 from such points + point i ). This was by far the best solution many implemented as it did not have the problem of precision with double etc.
code :

Share :

## How to get Point indexes for triangles from a set of points

By : Andrea Manica
Date : March 29 2020, 07:55 AM
around this issue There is a lot of research in this area. It's normally much faster to draw triangle strips than individual triangles because you only need to specify N+1 points for N triangles rather than 3*N points.
Most of the research is to take an arbitrary mesh (from eg a Delauney triangulation) and convert it into the minimum number of stripes.

## Closest point projection of a 3D point to 3D triangles with numpy/scipy

By : Андрей
Date : March 29 2020, 07:55 AM
hope this fix your issue Here's the code i came up with. I couldn't find anything in scipy that could help me directly, and this solution is about 2x faster than querying CGAL. It doesn't handle collapsed triangles, but that could be fixed by checking edge lengths and return the closest point on the longest edge instead.
code :
``````import numpy as np
from numpy.core.umath_tests import inner1d

def pointsToTriangles(points,triangles):

with np.errstate(all='ignore'):

# Unpack triangle points
p0,p1,p2 = np.asarray(triangles).swapaxes(0,1)

# Calculate triangle edges
e0 = p1-p0
e1 = p2-p0
a = inner1d(e0,e0)
b = inner1d(e0,e1)
c = inner1d(e1,e1)

# Calculate determinant and denominator
det = a*c - b*b
invDet = 1. / det
denom = a-2*b+c

# Project to the edges
p  = p0-points[:,np.newaxis]
d = inner1d(e0,p)
e = inner1d(e1,p)
u = b*e - c*d
v = b*d - a*e

# Calculate numerators
bd = b+d
ce = c+e
numer0 = (ce - bd) / denom
numer1 = (c+e-b-d) / denom
da = -d/a
ec = -e/c

# Vectorize test conditions
m0 = u + v < det
m1 = u < 0
m2 = v < 0
m3 = d < 0
m4 = (a+d > b+e)
m5 = ce > bd

t0 =  m0 &  m1 &  m2 &  m3
t1 =  m0 &  m1 &  m2 & ~m3
t2 =  m0 &  m1 & ~m2
t3 =  m0 & ~m1 &  m2
t4 =  m0 & ~m1 & ~m2
t5 = ~m0 &  m1 &  m5
t6 = ~m0 &  m1 & ~m5
t7 = ~m0 &  m2 &  m4
t8 = ~m0 &  m2 & ~m4
t9 = ~m0 & ~m1 & ~m2

u = np.where(t0, np.clip(da, 0, 1), u)
v = np.where(t0, 0, v)
u = np.where(t1, 0, u)
v = np.where(t1, 0, v)
u = np.where(t2, 0, u)
v = np.where(t2, np.clip(ec, 0, 1), v)
u = np.where(t3, np.clip(da, 0, 1), u)
v = np.where(t3, 0, v)
u *= np.where(t4, invDet, 1)
v *= np.where(t4, invDet, 1)
u = np.where(t5, np.clip(numer0, 0, 1), u)
v = np.where(t5, 1 - u, v)
u = np.where(t6, 0, u)
v = np.where(t6, 1, v)
u = np.where(t7, np.clip(numer1, 0, 1), u)
v = np.where(t7, 1-u, v)
u = np.where(t8, 1, u)
v = np.where(t8, 0, v)
u = np.where(t9, np.clip(numer1, 0, 1), u)
v = np.where(t9, 1-u, v)

# Return closest points
return (p0.T +  u[:, np.newaxis] * e0.T + v[:, np.newaxis] * e1.T).swapaxes(2,1)
``````
``````    import numpy as np
import cProfile

N_TRIANGLES = 10**4 # 10k triangles
N_POINTS    = 10**2 # 100 points
points      = np.random.random((N_POINTS,3,)) * 100
triangles   = np.random.random((N_TRIANGLES,3,3,)) * 100

cProfile.run("pointsToTriangles(points,triangles)") # 54 function calls in 0.320 seconds
``````

## Efficient checking of whether a point is inside a large number of triangles in 2D

By : Devidayal Kushwaha
Date : March 29 2020, 07:55 AM
To fix this issue The classical approach from computational geometry is to triangulate and then do point location, but it's a lot easier to just use a k-d tree, putting triangles that intersect the partitioning line of an interior tree node in that node so that they can be checked on the way down to the leaves.
Constructing the k-d tree is a recursive process. Given a list of triangles and a coordinate to focus on (x or y, alternating with each layer), find a separating line that is vaguely in the middle, by sampling randomly, by taking a median, or by some combination or sampling and taking a median. Gather the triangles whose points are all strictly less than the separation coordinate and use them to construct the left subtree. Gather the triangles whose points are all strictly greater than the separation coordinate and use them to construct the right subtree. Store the remaining triangles (the ones that intersect the coordinate line) in the root.

## Delaunay Walk point outside triangles

By : Novice
Date : March 29 2020, 07:55 AM
hope this fix your issue My guess turned out to be correct. If you have to cross the edge but can't find the triangle, it is on the outside. The points it connects to are l,r and any neighbor that can connect to the point without crossing a line and the neighbor of that point ...

## Finding unique triangles given in n number of triangles in python

By : pbocej
Date : March 29 2020, 07:55 AM
Does that help Given n-number of triangles, we are required to find how many triangles are unique out of given triangles. For each triangle we are given three integers a, b and c (the sides of a triangle).
code :
``````from collections import Counter

arr = [[7, 6, 5],[5, 7, 6],[8, 2, 9],[2, 3, 4],[2, 4, 3]]

def unique_triangles(arr):
counter = Counter([frozenset(a) for a in arr])
return len([res for res in counter if counter[res] == 1])
``````