Différences

Ci-dessous, les différences entre deux révisions de la page.

--- helloworld:algorithms:geometrie [2020/09/29 11:28] – Ajout de "Calculer une moyenne d'angles" root
+++ helloworld:algorithms:geometrie [2020/12/01 09:29] (Version actuelle) – Ajout de "Calculer la distance entre une ligne et un point" root
@@ Ligne 1: / Ligne 1: @@
-  * Vérifier que 4 points forment un rectangle
+===Vérifier que 4 points forment un rectangle===
 On calcule la distance des 4 cotés. On vérifie que les distances sont les mêmes deux à deux.
@@ Ligne 7: / Ligne 7: @@
 [[https://www.onlinemath4all.com/how-to-check-if-given-four-points-form-a-rectangle.html|How to check if given four points form a rectangle]] {{ :helloworld:algorithms:geometrie:how_to_check_if_given_four_points_form_a_rectangle_2020-09-25_01_40_44_.html |Archive le 26/09/2020}}
-  * Vérifier si un point est à l'intérieur d'un polygone
+===Vérifier si un point est à l'intérieur d'un polygone===
 Attention, il ne faut pas que les lignes se coupent.
@@ Ligne 13: / Ligne 13: @@
 [[https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/|How to check if a given point lies inside or outside a polygon?]] {{ :helloworld:algorithms:geometrie:how_to_check_if_a_given_point_lies_inside_or_outside_a_polygon_-_geeksforgeeks_2020-09-28_11_31_55_.html |Archive du 15/11/2019 le 28/09/2020}}
-  * Calculer une moyenne d'angles
+[[http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf|Geometric algorithms]] {{ :helloworld:algorithms:geometrie:geometry1x1.pdf |Archive du 16/03/1998 le 23/10/2020}}
+===Calculer une moyenne d'angles===
 On fait la moyenne des sinus et cosinus puis on calcul l'arctan de l'angle.
@@ Ligne 43: / Ligne 45: @@
 [[https://en.wikipedia.org/wiki/Mean_of_circular_quantities|Mean of circular quantities]] {{ :helloworld:algorithms:geometrie:mean_of_circular_quantities_-_wikipedia_2020-09-29_11_28_50_.html |Archive du 20/09/2020 le 29/09/2020}}
+===Calculer le point d'intersection de deux lignes définies par chacune par deux points===
+<code python>
+def line_intersection(line1, line2):
+  xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
+  ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1])
+  def det(a, b):
+    return a[0] * b[1] - a[1] * b[0]
+  div = det(xdiff, ydiff)
+  if div == 0:
+    raise Exception('lines do not intersect')
+  d = (det(*line1), det(*line2))
+  x = det(d, xdiff) / div
+  y = det(d, ydiff) / div
+  return x, y
+print line_intersection(((x1, y1), (x2, y2)), ((x3, y3), (x4, y4)))
+</code>
+[[https://stackoverflow.com/questions/20677795/how-do-i-compute-the-intersection-point-of-two-lines|How do I compute the intersection point of two lines?]] {{ :helloworld:algorithms:geometrie:python_-_how_do_i_compute_the_intersection_point_of_two_lines_-_stack_overflow_2020-09-29_17_17_11_.html |Archive du 19/12/2013 le 29/09/2020}}
+===Calculer le point d'intersection de deux segments définis par chacune par deux points===
+<code cpp>
+constexpr bool is_segment_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
+  float p2_x, float p2_y, float p3_x, float p3_y)
+{
+  float s1_x = p1_x - p0_x;
+  float s1_y = p1_y - p0_y;
+  float s2_x = p3_x - p2_x;
+  float s2_y = p3_y - p2_y;
+  float div = -s2_x * s1_y + s1_x * s2_y;
+  if (div == 0.)
+    return false;
+  float s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / div;
+  float t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / div;
+  return s >= 0 && s <= 1 && t >= 0 && t <= 1;
+  // Point d'intersection :
+  // i_x = p0_x + (t * s1_x);
+  // i_y = p0_y + (t * s1_y);
+}
+</code>
+[[https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect|How do you detect where two line segments intersect?]] {{ :helloworld:algorithms:geometrie:geometry_-_how_do_you_detect_where_two_line_segments_intersect_-_stack_overflow_2020-10-09_14_14_43_.html |Archive du 18/02/2009 le 09/10/2020}}
+===Calculer la droite perpendiculaire à une droite passant par un point===
+Le concept consiste à calculer le point sur la ligne d'origine.
+Soit (x1, y1) et (x2, y2) la droite et (x3, y3) le point en dehors de la droite.
+La ligne perpendiculaire à (x1, y1) et (x2, y2) passant par (x3, y3) est la droite (x3, y3) et (x4, y4)
+$k = ((y2-y1) * (x3-x1) - (x2-x1) * (y3-y1)) / ((y2-y1)^2 + (x2-x1)^2)$
+$x4 = x3 - k * (y2-y1)$
+$y4 = y3 + k * (x2-x1)$
+[[https://stackoverflow.com/questions/1811549/perpendicular-on-a-line-from-a-given-point|Perpendicular on a line from a given point]] {{ :helloworld:algorithms:geometrie:math_-_perpendicular_on_a_line_from_a_given_point_-_stack_overflow_27_11_2020_10_31_35_.html |Archive du 28/11/2009 le 27/11/2020}}
+===Calculer la distance entre une ligne et un point===
+Soit (x0, y0) et (x1, y1) la droite et (x, y) le point en dehors de la droite.
+$$\frac{|(y_0-y_1)x+(x_1-x_0)y+x_0 y_1-x_1 y_0|}{\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}}$$
+[[https://geomalgorithms.com/a02-_lines.html|Lines and Distance of a Point to a Line]] {{ :helloworld:algorithms:geometrie:lines_and_distance_of_a_point_to_a_line_01_12_2020_09_25_50_.html |Archive du 2012 le 01/12/2020}}