Posts by Mike George

Mike George · Coder's Corner

They don't need to be equidistant from each other, just moved the minimum amount to stop them obscuring each other on the map.

I've implemented the simple version described above and I've attached before and after pictures showing the result.

Mike George · Coder's Corner

bobbym wrote:

Hi Mike George;
Do you have a picture of your final best result?

No, I haven't implemented it yet, I was hoping somebody could suggest an elegant nutcracker before I get my sledgehammer out. I've got pictures of the current results but it's not very helpful because you can't see the hidden markers!

I am experimenting with a cruder approach, where I (conceptually) divide the map canvas into 10-pixel squares and set a flag in the appropriate square when I add a marker to the map. Before I add each marker I check to see if there is already one anchored in that square and if there is I try the next adjoining square, and so on until I find an unclaimed one, adjust the lat and long for the marker accordingly and add it. As the markers are added in random order and the average density on the map is fairly low this approach could work but I would be happier with a more robust solution.

Mike George · Puzzles and Games

A camera with a lot of dust on it. I think I'll go outside and

Mike George · Coder's Corner

Hello, it's been a couple of years since the last conundrum you very kindly helped me solve (actually you solved it for me), and now I've got a nice little problem that I can't help feeling should have a fairly simple algorithmic answer if only I knew what I was doing

I'm placing markers at points on a map. The map is redrawn every minute and the number and position of the points can change each time, and I have the x,y coordinates (representing pixel distances) for each point in an array after each refresh of the map. Usually the array is fairly sparse with big gaps between the points, but it is common for clusters of up to 4 or 5 markers to occur at the same point, and I want the markers to be displayed on the map with their anchor points at least 10 pixels apart. The common approach of 'clustering' the markers and springing them apart when the cluster is selected isn't appropriate, they have to be drawn separately (but it doesn't matter if they overlap as long as the 10 pixel rule is applied).

What I think I need to do is find any clashing pairs of x,y coordinates (where x AND y are less than 10 away from its nearest neighbour) and adjust them accordingly. If it helps I can sort the array of coordinates in order of x or y, or the points' distance from the origin.

In my mind's eye I can see all the points as little bar magnets standing on end on the map, free to move in any direction along the surface of the map until their mutual repulsion has pushed them a sufficient distance apart. How to translate that into an algorithm to make it happen I have no idea.

The best I can come up with is to sort them all into distance order (from the origin), start at the beginning of the array and when I find a point that is within 10 pixels of its predecessor's distance from the origin, check the distance between the two points and if that is less than 10 move them apart. Then re-sort the array on distance and repeat, until I make a complete pass without moving any points (ignoring for now the possibility that the map might be so crowded that a solution is impossible).

Can anybody suggest a quicker and simpler way to do this please?

Mike George · Help Me !

Aha!

Many thanks for your help and your patience. My script now does what it is supposed to andyou can see a demo in action at shed5.co.uk/demo.rotatearrow.gif.php?b=35

For anybody else looking for help to rotate a polygon using the PHP GD library of image functions, this is the script I ended up with. It's a bit long-winded to help make it clearer:

<?php
$im = @imagecreatetruecolor(100, 100);			// create the image resource

$white = imagecolorallocate($im, 255, 255, 255); 		// fill the background of
imagefill($im, 0, 0, $white);					// the image with white

$fill = imagecolorallocate($im, 0xFF, 0x33, 0x33);		// allocate the colour to fill the arrow

if (isset($_GET['b'])) {
	$bearing = -1*deg2rad($_GET['b']); 			// the angle to turn the polygon, clockwise
} else {
	$bearing = 0;
}
$offsetX = 50;							// the coordinates of the centre
$offsetY = -50;							// of the polygon

$arrowVerticesBase = array(					// the coordinates for the polygon
			array(50, -10), 				// in its normal state
			array(70, -30), 				// (this one is an arrow pointing north)
			array(55, -30),				// the y coordinates are negative
			array(55, -90),				// because the polygon is in the 
			array(45, -90),				// 'fourth quadrant' with the origin
			array(45, -30),				// of the grid at top left
			array(30, -30),
			array(50, -10)
			);

$arrowVertices = array();					// the array to hold coordinates for the rotated polygon

foreach($arrowVerticesBase as $vertex) {			// for each x,y pair of coordinates

	$x = $vertex[0] - $offsetX;				// take away the offset to put the centre of the polygon
	$y = $vertex[1] - $offsetY;				// at the origin of the grid

	$x1 = $x * cos($bearing) - $y * sin($bearing);	// finally, this is the formula that
	$y1 = $y * cos($bearing) + $x * sin($bearing);	// does the rotation

	$x1 = $x1 + $offsetX;					// add back the offsets to put the centre
	$y1 = $y1 + $offsetY;					// back in its proper position

	$arrowVertices[] = $x1;					// put the new coordinates into
	$arrowVertices[] = -1*$y1;				// the array for the function (make the y values positive for the imagefilledpolygon() function)
}

$arrow = imagefilledpolygon(					// create the rotated polygon
				$im, 					// the image resource
				$arrowVertices, 			// the array of coordinates to use
				sizeof($arrowVertices)/2,		// the number of coordinate pairs in the array
				$fill					// the fill colour for the polygon
				);

header ('Content-Type: image/gif');				// display the image
imagepng($im);
imagedestroy($im);
?>

Mike George · Help Me !

The box it has to fit in is only 100x100, so using 50,100 would put the point of the arrow at the bottom and I want it to point North if no angle is specified.

I've tried implementing the formula without much success so far. Could it be it doesn't take account of this?

Mike George wrote:

The polygon is drawn on an x,y coordinate system with the origin at top left.

Mike George · Help Me !

Thanks bobbym, but I'm afraid you've lost me - can we go back a step?

Taking the first point, where x = 50 and y = 10, I understand I have to compensate for the offset of the centre and make x = 0 and y = -40, then reverse this after the rotation.

I'm really just looking for a formula to apply to x and a formula to apply to y, to give the new coordinates to rotate the point t degrees (preferably clockwise, but that's not important).

The polygon described by the list I gave is an arrow on a bearing of 0 degrees, which is the shape I will be using.

Mike George · Help Me !

The origin is at 50,50 but I'm sure I can cope with the translation Bob.

Mike George · Help Me !

Anything between 0 and 359, so take your pick!

Mike George · Help Me !

I could do with more help please.

The array of vertices for an arrow to be rotated is:

$arrowVertices = array(
			50, 10, 
			70, 30, 
			55, 30,
			55, 90,
			45, 90,
			45, 30,
			30, 30,
			50, 10
			);

Mike George · Help Me !

bobbym wrote:

Hi;
Why not do it point by point.

Excuse my ignorance, but is that the same as

and

?

Mike George · Help Me !

Yes, that's it.:)

Mike George · Help Me !

I'm trying to write a function to turn a polygon to a specified bearing.

The polygon is drawn on an x,y coordinate system with the origin at top left.

I know the coordinates for the centre of the polygon, and for the starting position of each point on the polygon, and the value in degrees of the angle the polygon has to be rotated through (clockwise).

Could somebody give me the forumula to apply to each point to do this please (or explain how to work it out)?

Mike George · Introductions

Hello all, I found this forum while searching for a specific formula (which I haven't found yet).

I'm doing a lot of geographic stuff for a web site, which has led to me dusting off some the knowledge I learned over 40 years ago but sadly have mostly forgotten (I blame Mr Richards for not teaching me properly:) )

Anyway, I'll have another search to make sure what I'm looking for isn't already here, but I'll be back...

Math Is Fun Forum

#1 Re: Coder's Corner » How to avoid hidden objects on a map » 2013-12-21 03:40:50

#2 Re: Coder's Corner » How to avoid hidden objects on a map » 2013-12-20 04:58:10

#3 Re: Puzzles and Games » Name the object to the right of this arrow outside your screen --> » 2013-12-20 00:21:24

#4 Coder's Corner » How to avoid hidden objects on a map » 2013-12-19 17:46:36

#5 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-16 06:00:59

#6 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 06:49:49

#7 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 02:04:30

#8 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 01:16:20

#9 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 01:03:16

#10 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 00:59:00

#11 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 00:51:46

#12 Re: Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 00:33:44

#13 Help Me ! » calculating new coordinates for circular rotation to a new bearing » 2011-08-15 00:19:52

#14 Introductions » Hello » 2011-08-14 23:19:30

Board footer