WorkUnit:Disrupted Cities - road network - Revision history

Frankiezafe: /* related */

2018-07-25T19:52:14Z

‎related

Frankiezafe: /* Resources */

2017-11-13T12:48:42Z

‎Resources

Frankiezafe: /* Simplier version (p5.js) */

2017-09-08T16:40:02Z

‎Simplier version (p5.js)

Frankiezafe: /* related */

2017-09-08T16:16:52Z

‎related

Frankiezafe: /* C++ */

2017-09-08T16:15:48Z

‎C++

Frankiezafe: /* Resources */

2017-09-02T13:29:40Z

‎Resources

Frankiezafe: /* management */

2017-08-26T11:56:18Z

‎management

Frankiezafe: /* management */

2017-08-26T11:54:51Z

‎management

Frankiezafe: /* généralisation (fr) */

2017-08-26T11:51:22Z

‎généralisation (fr)

Frankiezafe: /* management */

2017-08-26T11:47:04Z

‎management

← Older revision		Revision as of 19:52, 25 July 2018
Line 1,109:		Line 1,109:

	<html><iframe width="560" height="315" src="https://www.youtube.com/embed/xhj5er1k6GQ" frameborder="0" allowfullscreen></iframe></html>		<html><iframe width="560" height="315" src="https://www.youtube.com/embed/xhj5er1k6GQ" frameborder="0" allowfullscreen></iframe></html>
		+
		+	Solving via the 3rd dimension:
		+
		+	<html><iframe width="560" height="315" src="https://www.youtube.com/embed/6xxHrWaTAAo" frameborder="0" allow="autoplay; encrypted-media" allowfullscreen></iframe></html>
		+
		+	<html><iframe width="560" height="315" src="https://www.youtube.com/embed/oLM99qYnzm0" frameborder="0" allow="autoplay; encrypted-media" allowfullscreen></iframe></html>

	[[Category:Disrupted Cities]]		[[Category:Disrupted Cities]]

@@ Line 1,104: / Line 1,104: @@
 * '''Doubly connected edge list''', also known as half-edge data structure - [[wikipedia:Doubly_connected_edge_list|wikipedia]]
 *  ''Segments' intersection'' & ''Segments' crossing'' in [[Notes:Math|Notes:Math]]
 === related ===

@@ Line 780: / Line 780: @@
 ==== Simplier version (p5.js) ====
-One of the big problem in split event detection is when the bisector of the point, is not crossing the segment (see [[#selection|selection of segment]] for details).
+One of the big problem in split event detection is when the bisector of the point is not crossing the segment (see [[#selection|selection of segment]] for details).
 The first implemented method was based on detection of bisectors' intersection. The method is unsafe. A better method is to create a temporary polygon representing the surface covered by the segment when shrunk, and verify that the event point is belonging to the surface.

← Older revision		Revision as of 16:16, 8 September 2017
Line 1,121:		Line 1,121:
	[[Category:processing.org]]		[[Category:processing.org]]
	[[Category:openframeworks.cc]]		[[Category:openframeworks.cc]]
		+	[[Category:javascript]]

← Older revision		Revision as of 16:15, 8 September 2017
Line 777:		Line 777:

	[[File:Roadmap 2017052819303639379.png\|400px]]		[[File:Roadmap 2017052819303639379.png\|400px]]
		+
		+	==== Simplier version (p5.js) ====
		+
		+	One of the big problem in split event detection is when the bisector of the point, is not crossing the segment (see [[#selection\|selection of segment]] for details).
		+
		+	The first implemented method was based on detection of bisectors' intersection. The method is unsafe. A better method is to create a temporary polygon representing the surface covered by the segment when shrunk, and verify that the event point is belonging to the surface.
		+
		+	It has been implemented in this sketch ():
		+
		+	<html><iframe src="files/split_event/index.html" width="600" height="600" scrolling="no" frameBorder="0"></iframe></html>
		+
		+	manipulation:
		+
		+	* right-click & drag points to move them
		+	* right-click & drag anywhere else to modify offset

	=== C++ ===		=== C++ ===

← Older revision		Revision as of 13:29, 2 September 2017
Line 1,090:		Line 1,090:
	* ''Segments' intersection'' & ''Segments' crossing'' in [[Notes:Math\|Notes:Math]]		* ''Segments' intersection'' & ''Segments' crossing'' in [[Notes:Math\|Notes:Math]]

		+	=== related ===
		+
		+	<html><iframe width="560" height="315" src="https://www.youtube.com/embed/xhj5er1k6GQ" frameborder="0" allowfullscreen></iframe></html>

	[[Category:Disrupted Cities]]		[[Category:Disrupted Cities]]

@@ Line 905: / Line 905: @@
 <html>
-<iframe src="https://player.vimeo.com/video/229914330" width="640" height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe>
+<iframe src="https://player.vimeo.com/video/229914330?title=0&portrait=0&byline=0" width="640" height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe>
 </html>

← Older revision		Revision as of 11:54, 26 August 2017
Line 903:		Line 903:

	==== management ====		==== management ====
		+
		+	<html>
		+	<iframe src="https://player.vimeo.com/video/229914330" width="640" height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe>
		+	</html>

	[The complete description of the process done during shrink when a shape is flagged as "spiky" will come later.]		[The complete description of the process done during shrink when a shape is flagged as "spiky" will come later.]

← Older revision		Revision as of 11:51, 26 August 2017
Line 924:		Line 924:

	==== généralisation (fr) ====		==== généralisation (fr) ====
		+
		+	===== standardisation des spike events =====
		+
		+	Je n'utilise les spike events que dans un cas bien particulier pour le moment: lorsque les polygones, au moment où le shrink est appliqué, contient des portions dont les segments sont parallèles ET dont l'extrémité est un angle à +/- 2 pi.
		+	Ce cas équivaut à un event dont le facteur de déclenchement (shrink) est 0, c'est-à-dire un event qui doit être effectué immédiatement, avant de faire quoique ce soit d'autre.
		+	Il existe une autre forme de spike event, plus subtile, une sorte de edge event spécial et dont la condition de détection est très simple:
		+	* si la direction du segment suivant le segment courant est parallèle au segment précédent le segment courant, on peut être certain de le segment courant à de fortes chances de se muer en spike event au cours de l'évolution de la forme.
		+	Ça vaut donc le coup de le détecter à l'avance et de le stocker tout comme les autres types.
		+	Bizarrement, quelque soit l'angle entre le segment courant, le précédent et le suivant, ça n'a que très peu d'importance (si ce n'est l'orientation).
		+	En effet, la somme des angles entre les 3 segments sera toujours pi!
		+
		+	petits croquis en ascii
		+
		+	* cas le plus évident: 2 x angles de 90°
		+
		+	x
		+	p0 _____ p1
		+	\| \|
		+	A \| \| B
		+	\| \|
		+	<-\| \|->
		+	\| \|
		+	p-1
		+
		+	À p0, on peut observer que les directions p-1 > p0 et p0 > p1 sont opposées. De là, on stocke un spike event sur p0, et on calcule la distance entre A et B (un peu de math, mais on a déjà les normales, ça devrait aller vite). On divise cette distance par 2 et on obtient le facteur de shrink minimum pour déclencher l'event.
		+	p1 a un statut particulier dans cet event. Il ne s´agit pas d'un point comme les autres (appelés non-cruciaux dans le code). Il ne peut en aucun cas "survivre" au déclenchement de l'event... quoique: dans le cas d'un event ayant la même direction que le spike - convexe dans ce cas, l'intérieur se trouvant entre A et B... non, le spike event de p0 ne déclenchera que vers l'intérieur, p1 est donc condamné à disparaître.
		+
		+	* autre cas
		+
		+
		+	p1 => p0 - p1
		+	/\| => ¦
		+	x / \| B => ¦ B
		+	/ \|-> => ¦
		+	/ \|____________ => ¦____________
		+	p0 / p2 p3 => p2 \| p3
		+	/ => \|
		+	\| => \|
		+	A \| => (A) \|
		+	\| => \|
		+	<-\| => <-\|
		+	___\| => ___\|
		+	p-1 => p-1
		+
		+	dans ce cas, c'est un peu moins rigolo: comme la projection perpendiculaire du point p2 sur la droite p-1,p0 donne un point en dehors du segment \|p-1.p0\|, il va falloir conserver les 2 points, p-1 et p2. Mais ça revient au même avec des angles carrés:
		+
		+	p0 _____ p1
		+	\| \|
		+	A \| \| B
		+	\| \|
		+	<-\| \|->
		+	\| \|______
		+	\| p2
		+	____\|
		+	p-1
		+
		+	===== recherche de la base =====
		+
		+	Comme vu ci-dessus, il est tout-à-fait possible que les deux points "base" d'un spike event ne soit pas identiques et/ou que d'autres points soient alignés des 2 côtés de l'événement. Un autre cas est à traiter:
		+
		+	p0
		+	.
		+	\|\|
		+	\|\|
		+	p-1 .\|
		+	\|\|
		+	p-2 .\|
		+	\|\|
		+	\|. p1
		+	p-3 .\|
		+	\|\|
		+	\|\|
		+	\|\|
		+	\|.________
		+	\| p2
		+	____.
		+	p-4
		+
		+	On identifie de suite les points p-1 et p1, mais il reste à remonter jusqu'à atteindre p-4 et p2.
		+
		+	* cas extrême:
		+
		+	p0
		+	.
		+	\|\|
		+	\|\|
		+	p-1 .\|
		+	\|\|
		+	p-2 .\|
		+	\|\|
		+	\|. p1
		+	p-3 .\|
		+	\|\|
		+	\|\|
		+	\|\|
		+	.
		+	p2
		+
		+
		+	* cas similaire topologiquement:
		+
		+	p0
		+	.
		+	//
		+	//
		+	//
		+	p-1 .. p1
		+	\|\|
		+	\|\|
		+	\|\|
		+	.
		+	p-2 = p2
		+
		+	La différence dans ce cas est la présence de point identiques, et l'obligation de prendre en compte le fait que le polygone contienne un nombre pair ou impair de points. Ce cas limite, où le point le plus éloigné est présent aux 2 extrêmités du spike, permet de flagger le polygone comme étant une ligne, n'ayant plus du coup que la faculté de s'étendre (shrink négatif uniquement, donc).
		+
		+	Ce qui nous amène à une constation intéressante: du point de vue de l'algorithme, une ligne est un polygone sans surface, n'ayant donc pas d'"intérieur".
		+	Cette faculté nous permettra de charger des les chemins ouverts du fichier svg, en doublant tous les points sauf le premier! En prime, ça nous donne la garantie que le premier point sera un split event qui parcourera toute la forme, empêchant du même coup la possibilités et donc le calcul de tous les autres types d'événements.
		+
		+	Les spikes sont des événements cruciaux pour les straight skeletons.
		+
		+	Dernier cas d'utilisation des spikes: détection des collisions de segments parallèles.
		+
		+	___ /
		+	\| \|
		+	\| \|
		+	\|____\|
		+
		+	________
		+	\| \|
		+	\| \|
		+	\| \|
		+	/ \

	=== Weights ===		=== Weights ===

← Older revision		Revision as of 11:47, 26 August 2017
Line 922:		Line 922:

	[[File:Dc openframeworks spikes_003_errors.png\|400px]]		[[File:Dc openframeworks spikes_003_errors.png\|400px]]
		+
		+	==== généralisation (fr) ====

	=== Weights ===		=== Weights ===