| --- Log opened Fri Aug 13 00:00:33 2010 |
| 00:15 | | You're now known as TheWatcher[T-2] |
| 00:18 | | You're now known as TheWatcher[zZzZ] |
| 00:35 | | AnnoDomini [annodomini@Nightstar-d5315a41.adsl.tpnet.pl] has quit [[NS] Quit: ASDF.] |
| 00:39 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 01:16 | | SmithKurosaki [Smith@Nightstar-cc72cefe.dsl.teksavvy.com] has joined #code |
| 01:23 | | Attilla [Obsolete@Nightstar-4ecdef8c.threembb.co.uk] has quit [[NS] Quit: ] |
| 01:29 | | Derakon[AFK] is now known as Derakon |
| 01:29 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: ] |
| 01:44 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has joined #code |
| 02:55 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 03:25 | | Stalker [Z@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
| 04:00 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 04:52 | | Vornicus [vorn@Nightstar-66efdaa0.ct.comcast.net] has joined #code |
| 04:52 | | mode/#code [+o Vornicus] by Reiver |
| 05:20 | | * Derakon eyes the S-hull triangulation technique. |
| 05:20 | <@Derakon> | "Find the point x_k that creates the smallest circumcircle with x_0 and x_j." |
| 05:21 | <@Derakon> | I'm guessing this is the point such that the maximum distance from the center of the three points to each of the points individually is minimized. |
| 05:21 | <@Derakon> | (I.e. if I have points (a, b, c), then they have a center d as the average of their locations; the smallest circumcircle is when max(|a - d|, |b - d|, |c - d|) is minimal) |
| 05:24 | <@Vornicus> | A trio of points has exactly one circumcircle -- and it's not the average of the points. |
| 05:25 | <@Derakon> | No, no, but its radius is the maximum of the distance from any one point to the average, yes? |
| 05:25 | <@Derakon> | ...no, it wouldn't be. |
| 05:25 | <@Vornicus> | It's the intersection of the perpendicular bisectors of the line segments described by the points. |
| 05:26 | <@Derakon> | Okay, so I need a convenient way to calculate that~ |
| 05:29 | <@Vornicus> | Okay. take two pairs of points. Get their slope (difference, y_diff / x_diff) and midpoint; get the perpendicular (-1/slope is perpendicular to slope). This gives you a point and a slope; use point-slope form as solved for y [ y - y_1 = m(x - x_1) ---> y = m(x - x_1) + y_1 ] to describe the lines, and equate the two lines' y values: m_1 (x - x_1) + y_1 = m_2 (x - x_2) + y_2. Solve /that/ |
| 05:29 | <@Vornicus> | motherfucker and you've got your answer |
| 05:29 | <@Vornicus> | That was kinda long. |
| 05:29 | <@Derakon> | Yeah. |
| 05:30 | <@Derakon> | I've never really liked line intersection tests. |
| 05:30 | <@Vornicus> | This is 2d, fortunately. |
| 05:30 | <@Derakon> | The math is simple, but you have to code for the vertical edge-cases. |
| 05:30 | <@Vornicus> | Right, just thought of that, give me a moment; Standard Form to the rescue. |
| 05:30 | <@Derakon> | Hang on a tick. |
| 05:31 | <@Vornicus> | (I'll give you working code. What language?) |
| 05:31 | <@Derakon> | I have a line module. |
| 05:31 | <@Derakon> | I have done this before~ |
| 05:31 | <@Vornicus> | Okay, what's it give you? |
| 05:31 | <@Derakon> | I haven't remembered how to use it yet~ |
| 05:31 | <@Vornicus> | --oh, written yourself. Okay. |
| 05:31 | <@Derakon> | Looks like it's segment-segment intersection. |
| 05:32 | <@Vornicus> | But still - what language, It feels like fun. |
| 05:32 | <@Derakon> | Python. |
| 05:32 | <@Vornicus> | Ok. |
| 05:35 | <@Derakon> | Okay, looks like I'm generating the lines properly: http://derakon.dyndns.org/~chriswei/temp2/lines.png |
| 05:35 | | * Derakon eyes his line-line intersect code. |
| 05:35 | <@Vornicus> | Looks it. Could you draw the outer lines too? |
| 05:36 | <@Derakon> | Yes, it's lovely that I can know if the lines intersect, but I would also like to know where they intersect. Apparently that wasn't a priority~ |
| 05:36 | <@Derakon> | Vorn: trivially, yes. |
| 05:36 | <@Vornicus> | Good. Wanna make sure it looks right. |
| 05:37 | <@Derakon> | So, maybe I need to extend my lines in both directions. http://derakon.dyndns.org/~chriswei/temp2/lines.png |
| 05:37 | <@Derakon> | This is why my test case is random! |
| 05:38 | <@Vornicus> | Yes! |
| 05:38 | <@Vornicus> | Fair warning, the circumcenter is not necessarily within the triangle. |
| 05:38 | < Rhamphoryncus> | Derakon: what's the purpose of all this? |
| 05:39 | <@Derakon> | Rhamphoryncus: generating the Delaunay triangulation of a set of nodes, for purposes of generating maps in Jetblade. |
| 05:39 | < Rhamphoryncus> | ahhh |
| 05:39 | <@Derakon> | Vorn: yes, I just got a test case like that. |
| 05:45 | <@Derakon> | Okay, that seems to be getting me intersection results. |
| 05:46 | <@Derakon> | Except it's claiming no intersection sometimes. |
| 05:46 | <@Derakon> | Oh, wait, that's because I made the lines too short. |
| 05:49 | <@Vornicus> | There is no technical maximum for intersection distance here. |
| 05:49 | <@Derakon> | Right, but in practice I have a finite line length because my Line class should be called LineSegment~ |
| 05:49 | <@Derakon> | (And it was originally written to detect when two edges of a graph intersect, which requires finite line intersection) |
| 05:50 | <@Vornicus> | Pfah. |
| 05:57 | <@Derakon> | Yeegh, okay, this could be a problem. |
| 05:58 | <@Derakon> | http://derakon.dyndns.org/~chriswei/temp2/longlines.png |
| 05:58 | <@Derakon> | Just extending the lines out indefinitely doesn't really work~ |
| 05:58 | <@Vornicus> | Slightly! |
| 06:05 | | * Derakon mutters as he gets a ZeroDivisionError. |
| 06:05 | <@Derakon> | Frickin' frackin' slopes. |
| 06:05 | <@Vornicus> | I'll have something to you shortly, I'm being careful about 0. |
| 06:05 | <@Derakon> | It's more of a pain than anything else. |
| 06:06 | <@Derakon> | I appear to be successfully generating circumcircles when I don't hit that, though. |
| 06:10 | <@Derakon> | Okay, that seems to be sorted. |
| 06:11 | <@Derakon> | http://derakon.dyndns.org/~chriswei/temp2/circumcircle.png |
| 06:11 | <@Derakon> | I do so love visual debugging. |
| 06:12 | <@Vornicus> | Nice. |
| 06:12 | <@Derakon> | (The labels are radial sort order) |
| 06:15 | <@Vornicus> | By the way, are you doing anything special to generate your points? One of my constant bugbears in VornMoO was generating points so they're acceptably spread out. |
| 06:15 | <@Derakon> | This is the "break screen up into 100x100 chunks; put a node at random in each chunk" approach. |
| 06:15 | <@Derakon> | Which seems to be generating a very regimented look. I'll need to further randomize it. |
| 06:17 | <@Vornicus> | I had a hell of a time making mine "look natural" and not have it either sometimes fail or take an age to generate. |
| 06:20 | <@Derakon> | I'll let you know when I work on that. Bigger fish to fry ATM~ |
| 06:22 | <@Derakon> | Yeegh, I'm only up to step 6 of the algorithm and already I'm at 107 lines of code~ |
| 06:22 | <@Derakon> | 107 lines of uncommented, slapdash code. ¬.¬ |
| 06:23 | <@Vornicus> | Yeah, this stuff isn't very nice. |
| 06:25 | | * Derakon slaps some comments in, will call it a night there. |
| 06:25 | < Orthia> | Vorn: Have you tried the.. what is it |
| 06:26 | < Orthia> | Put a thousand points on a map. Delete every second one a couple times. |
| 06:26 | < Orthia> | (A bit harder if you don't have a convinient grid, but) |
| 06:29 | <@Vornicus> | Orthia: the difficulty here is that, well. What I need is a reasonably 'smooth' distribution. |
| 06:30 | <@Vornicus> | Rejecting points based on selection order doesn't improve the smoothness. |
| 06:31 | <@Vornicus> | Think of how MoO or SotS work: points tend to be reasonable distances apart. |
| 06:31 | | PinkFreud [WhyNot@NetworkAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 06:31 | <@Vornicus> | If I pick 50 random points in the unit square, sure, the average will be reasonable - but the minimum will likely be ridiculously low. |
| 06:32 | | Derakon [Derakon@Nightstar-5213d778.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 06:32 | <@Vornicus> | ...my parents have Plants vs. Zombies. |
| 06:33 | < Orthia> | hahaha, awesome |
| 06:33 | < Orthia> | (Though I admit, my fondness of that game is limited. Not entirely sure why, just...) |
| 06:33 | <@Vornicus> | And it's that minimum I worry about - I want to minimize as much as reasona... shit. |
| 06:33 | <@Vornicus> | I know what to /do/ now. |
| 06:34 | < Orthia> | Do tell! |
| 06:34 | <@Vornicus> | sphere packing ftw |
| 06:37 | <@Vornicus> | What I can do is place stars by starting with a single star, placing another star 3 ly away (in some direction or other) - and then filter out segments of the 3ly circles that are less than 3ly from other stars. |
| 06:38 | < Orthia> | cunning |
| 06:38 | < Orthia> | Then they are all inevitably 3ly away from each other? |
| 06:38 | <@Vornicus> | That way, every star is exactly 3ly from one other star. |
| 06:39 | <@Vornicus> | (i'd actually probably pick something like 2.5 to increase the number of stars in the 3ly radius) |
| 06:40 | < Orthia> | So the first four stars form a tetrahedron? |
| 06:40 | <@Vornicus> | Not necessarily |
| 06:41 | <@Vornicus> | You see, what I'm actually doing here is choosing a random location from /all possible/ locations along the arcs of these circles. |
| 06:42 | < Orthia> | Aah, okay. |
| 06:42 | < Orthia> | Acceptable, though distance-checking after a while will become somewhat onorous. |
| 06:42 | <@Vornicus> | Distance-checking? |
| 06:43 | < Orthia> | Do you plan to keep each new star away from *all* others by a minimum of 3ly? |
| 06:44 | <@Vornicus> | Yes. This is what the filtering is for. |
| 06:44 | < Orthia> | That means that to insert the 100th star, you need to check all 99 others? |
| 06:44 | <@Vornicus> | After I place each star, I filter the existing arcs so that none of the remaining arcs are within 3ly of the new star. |
| 06:45 | < Orthia> | hm |
| 06:45 | < Orthia> | So you first check 99, then by the hundredth you've only got one. |
| 06:45 | <@Vornicus> | I really haven't explained this well. |
| 06:45 | < Orthia> | don't worry about it, I'm in a slightly funny mood myself today, forgive. |
| 06:46 | | * Orthia is trying to decide how best to ad hoc up the frontal fire arc of spaceships. >_> |
| 06:46 | <@Vornicus> | What I'm doing is this: draw a circle; the center of this circle is the first star. |
| 06:46 | < Orthia> | right |
| 06:46 | <@Vornicus> | Choose a random point on the circle. This is the second star. Draw a circle (of the same size) around the second star... and erase any parts of either circle that are inside the other. |
| 06:47 | < Orthia> | right. |
| 06:47 | <@Vornicus> | Then, choose a random point on the arcs you haven't erased. This is the third star. Draw another circle, erase what's inside. Keep going. |
| 06:48 | < Orthia> | right |
| 06:49 | <@Vornicus> | So instead of checking I generate -- but i'm modifying the generation space as I go, in such a way that all the points I choose will be valid. |
| 06:50 | <@Vornicus> | The tricky part is keeping the arcs in check. |
| 06:51 | < Orthia> | And keeping the housecleaning algy clean |
| 06:52 | < Orthia> | Such things are nontrivial, afterall. |
| 06:56 | <@Vornicus> | Quite. I'm pretty sure this is slightly worse than quadratic time. |
| 06:57 | <@Vornicus> | This is considerably better than possibly-infinite time (random placement and rejection) and also quartic+ time (magnetics) |
| 07:06 | <@Vornicus> | (magnetics were pretty bad because I needed to sort locations, filter them, then apply certain of them to the magnet, then do this again for every single one, and it took more steps the more stars I had.) |
| 07:20 | | PinkFreud [WhyNot@NetworkAdministrator.Nightstar.Net] has joined #code |
| 07:33 | | * Vornicus is shockingly close to a closed form with this thing. |
| 07:34 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 07:42 | <@Vornicus> | --actually I think that if I am allowed to reorder the inputs first, I'll have a guaranteed closed form except for situations where the points are colinear. |
| 07:42 | <@Vornicus> | Which is Bad Anyway. |
| 08:11 | <@Vornicus> | Oh. Well, would you look at that. The only situation where I need to switch points is where the first line I chose has no x difference; of the two divisions, one is clearly the cross product of the two slopes (so is only 0 when the triangle is degenerate) and the other is simply the x difference of one line. |
| 08:22 | <@Vornicus> | y = ((ax^2 - bx^2 - ay^2 + by^2) * (ax - cx) - (ax^2 - cx^2 - ay^2 + cy^2) * (ax - bx)) / (2 * ((ay - by) * (ax - cx) - (ay - cy) * (ax - bx))) |
| 08:27 | <@Vornicus> | In short: "shoot me", but that's shockingly good. |
| 08:27 | <@Vornicus> | ...wait. |
| 08:27 | <@Vornicus> | I can just do the solve on x instead of y to get the other answer. |
| 08:28 | <@Vornicus> | Changes ax - cx and ax - bx in the numerator to its counterparts... and that's it. |
| 08:32 | <@Vornicus> | Holy shit. Okay, what's Dad got for spreadsheets. |
| 09:32 | | Stalker [Z@3A600C.A966FF.5BF32D.8E7ABA] has joined #code |
| 09:38 | | You're now known as TheWatcher |
| 09:48 | | AnnoDomini [annodomini@Nightstar-a39828b8.adsl.tpnet.pl] has joined #code |
| 09:48 | | mode/#code [+o AnnoDomini] by Reiver |
| 12:27 | | cpux is now known as shade_of_cpux |
| 12:52 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has quit [Client exited] |
| 13:10 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 13:56 | | You're now known as TheWatcher[afk] |
| 14:05 | | Stalker [Z@3A600C.A966FF.5BF32D.8E7ABA] has quit [Ping timeout: 121 seconds] |
| 14:53 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has joined #code |
| 15:00 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 15:10 | | Vornicus is now known as Vornicus-Latens |
| 15:41 | | You're now known as TheWatcher |
| 16:00 | | Vornicus-Latens [vorn@Nightstar-66efdaa0.ct.comcast.net] has quit [Ping timeout: 121 seconds] |
| 16:58 | | Attilla [Obsolete@Nightstar-6eb0d476.threembb.co.uk] has joined #code |
| 16:58 | | mode/#code [+o Attilla] by Reiver |
| 18:53 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Client closed the connection] |
| 19:01 | | Med-Nador [Medouu@687AAB.B2F6EA.794FDB.87A87C] has joined #code |
| 19:10 | | Attilla [Obsolete@Nightstar-6eb0d476.threembb.co.uk] has quit [Ping timeout: 121 seconds] |
| 19:12 | | Med-Nador [Medouu@687AAB.B2F6EA.794FDB.87A87C] has quit [[NS] Quit: Peace and Protection 4.22] |
| 19:15 | | Attilla [Obsolete@Nightstar-4b1a7c86.threembb.co.uk] has joined #code |
| 19:15 | | mode/#code [+o Attilla] by Reiver |
| 19:56 | | Derakon [Derakon@Nightstar-1ffd02e6.ucsf.edu] has joined #code |
| 19:56 | | mode/#code [+o Derakon] by Reiver |
| 19:56 | <@Derakon> | G'day. |
| 20:34 | | Serah [Z@Nightstar-41ddd748.0.fullrate.dk] has joined #code |
| 20:36 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has quit [Ping timeout: 121 seconds] |
| 20:44 | | Serah [Z@Nightstar-41ddd748.0.fullrate.dk] has quit [Ping timeout: 121 seconds] |
| 20:58 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has joined #code |
| 21:03 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has quit [Ping timeout: 121 seconds] |
| 21:04 | | Vornicus-Latens [vorn@Nightstar-66efdaa0.ct.comcast.net] has joined #code |
| 21:04 | | mode/#code [+o Vornicus-Latens] by Reiver |
| 21:12 | | Vornicus-Latens is now known as Vornicus |
| 21:15 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has joined #code |
| 21:48 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has joined #code |
| 22:47 | | Derakon [Derakon@Nightstar-1ffd02e6.ucsf.edu] has quit [[NS] Quit: Leaving] |
| 23:03 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
| 23:05 | | Stalker [Z@Nightstar-41ddd748.0.fullrate.dk] has quit [Ping timeout: 121 seconds] |
| 23:39 | | You're now known as TheWatcher[T-2] |
| 23:42 | | You're now known as TheWatcher[zZzZ] |
| --- Log closed Sat Aug 14 00:00:34 2010 |