Divide co-ordinates based on priority.

[JChilds]

I have a list of x,y coordinates. (drill positions)

 

I have Three Primary x,y co-ords. (station positions)

 

I want to assign drill positions to stations based on how close they are and the priority of the station(1, 2 or 3).

 

I also want the option of making all stations have a priority or 1 so they divide equally.(for drill positions that are close to two stations)

 

I have absolutely no idea how to tackle this.

Is there a formula anyone is aware of?

Can anyone even attempt to show me how to tackle this. I am 100% lost.

[JKG]

x,y co-ordinates as in grid references?

 

if so, calculate the distance from each drill to all 3 stations, then assign to the station with the smallest number.

[mikesta707]

Which of the two parameters take priority? closeness or the station priority? like say 1 station has a higher priority but a higher distance also. Which station is assigned to the drill in question? This could be as simple as calculating the distance as JKG mentioned, but a little more information would prove useful in helping you solve this problem.

[JChilds]

If you imagine the three stations having rings (radius) around them.

This radius can well and truely overlap a near by station.

 

Only the 'overlap' of the rings is to be split/prioritized.

 

[JChilds]

bump?

[JKG]

should one drill be assigned to more than one station?

[xyph]

If you imagine the three stations having rings (radius) around them.

This radius can well and truely overlap a near by station.

 

Only the 'overlap' of the rings is to be split/prioritized.

 

 

Here's how I would approach this, knowing very little about what's going on.

 

Each station is given a max radius that a given drill must be in to be assigned.

The max radius varies on priority. The greater the priority, the larger the radius.

In the case of overlapping, the 'winning' station will be that with some combination of actual distance from station, and distance from edge of radius.

 

In doing that, a drill that's equidistant to two different stations will be applied to the one with greater priority. In the  hopefully rare case that your algorithm gives equal scores to multiple stations, use a random function.

[JChilds]

Only one drill can go to each station.

 

To specify a little further:

 

Each Station already has a list of drills within its radius.

But a drill cannot be assigned to more than one station.

Where as at the moment the stations are assigned to all drills within their radius, so there are alot of doubles.

 

 

 

[JChilds]

It also has to be a possibility for two stations to have the same priority. (if this happens, I have to assign the current doubled up drill to the station with the least amount of drills assigned to it)

[xyph]

You have yet to comment on my suggestion?

 

I don't see a point in providing code if you aren't happy with the way it works.

 

Also, if only one drill can go to each station, if there are 3 stations there are only 3 drills?

 

And after rereading this, you want variable priority? The more drills a station has, the less priority it has?

[JChilds]

xyph,

 

The lists of drills are already assigned to each station.

But there are alot of double ups (two or more stations being assigned the same drill)

 

There can be 200 or more drills assigned to each station.

 

IF two stations have the same priority, the current drill is assigned to the station with the least amount of drills currently assigned to it.

 

[xyph]

Please provide some sample data.

 

This last post is much different than your original post.

 

So each station has a list of drills assigned to it. Your problem is sometimes there is x drill on more than one station. You want to go through all the duplicates drills, and remove the duplicate from whichever station has lower priority. if they're the same priority, remove it from the station with the most drills

 

How are you storing this information?

[Psycho]

Can you please provide some of the peretinent code? Also, what is the parameters of the grid (i.e the min/max x and y values)? Lastly, you say some of the drills are already assigned - are you getting this info from a database and what is the format of the data?

[JChilds]

xyph, You are correct.

 

I currently use this to get all drills within a certain radius.

 

$query = "
SELECT
*
FROM
$table
WHERE
(SQRT( ($x-x)*($x-x)+($y-y)*($y-y) ) < $radius ) 
";

 

sample data:

 

	x 	y 
	 	 	500	485
	 	 	517	514
	 	 	495	515
	 	 	504	481
	 	 	518	501
	 	 	499	506
	 	 	501	518
	 	 	507	487
	 	 	495	500
	 	 	486	507
	 	 	510	493
	 	 	513	516
	 	 	513	514
	 	 	505	511
	 	 	504	489
	 	 	512	515
	 	 	503	513
	 	 	511	515
	 	 	478	499

 

stations:

500,500

480,490

[xyph]

IMO making the decisions in the query is a bad idea, and I don't say that often.

 

I suggest grabbing all the data and allowing PHP to decide what goes where. Modern databases can perform logical functions and make decisions, but that's not what they're meant for.

[Psycho]

 

OK, here is a proof of concept. Since you already have drill positions that are assigned to stations positions I'm not sure how you want to implement this. The code below assumes you have a list of stations and positions and want to iterate over ALL the drill positions to assign them to stations then save those assignments. But, if your drillpositions are dynamic you would have to reprocess ALL of them whenever there is a change.

 

Drill positions will be assigned to Stations according to the following:

 

1. If a drill position is closer to one station than the others it will be assigned to that station.

2. If a drill position is the same distance to two stations, it will be assigned to the station with the higher priority (if different)

3. If a drill position is the same distance to two stations with the same priority, it will be assigned to the station with the least amount of currently assigned drills.

 

Now, this isn't perfect since the order in which the drills are processed will affect the results. If a drill is assigned due to the third condition (number of currently assigned drills) that assignment could be different if they were processed in a different order. I even included a record to see this.The drill position with the comment next to it will be assigned to station '0' based upon where it currently exists in the data order. but, if you move that record to the end of the array it will then get assigned to station 1.

 

Anyway, the following code works pretty much as you requested using two arrays for the station and drill positions. I even included code at the end to display the results in a grid. Stations have a specific background color and the assigned drills are given text color to match the assigned station. Note that the display code was just thrown together. It will not display duplicate items in the same cell. Also, although I hard coded the color coding for a maximum of three positions, the logic for assigning drills to stations will work with any number of records for either.

 

<?php

//Test data
$stationsAry = array(
        array( 'x'=>3, 'y'=>4, 'priority' => 1),
        array( 'x'=>9, 'y'=>8, 'priority' => 1),
        array( 'x'=>5, 'y'=>10, 'priority' => 2)
    );

$drillsAry = array(
        array( 'x'=>3,  'y'=>,
        array( 'x'=>10, 'y'=>6),
        array( 'x'=>5,  'y'=>7),
        array( 'x'=>3,  'y'=>9),
        array( 'x'=>6,  'y'=>6),  //Can Change Assignment
        array( 'x'=>7,  'y'=>2),
        array( 'x'=>9,  'y'=>3),
        array( 'x'=>4,  'y'=>,
        array( 'x'=>1,  'y'=>10),
        array( 'x'=>2,  'y'=>3),
        array( 'x'=>5,  'y'=>5),
        array( 'x'=>3,  'y'=>2)

);

//Function to process all drill positions and
//assign to a station
function get_assigned_drills($drills, $stations)
{
    //Create array to hold results
    $results = array();

    //Process drill locations
    foreach($drills as $drillID => $drill)
    {
        //Tracking vars
        $selected_station  = false;
        $selected_distance = false;
        //Compare drill to stations
        foreach($stations as $stationID => $station)
        {

            //Get station positions
            $distance = sqrt(pow(abs($station['x']-$drill['x']),2) + pow(abs($station['y']-$drill['y']), 2));
            if($selected_distance===false || $distance<$selected_distance)
            {
                //First station or distance is less than prev selected station
                $selected_station  = $stationID;
                $selected_distance = $distance;
            }
            elseif($distance==$selected_distance)
            {
                //Disatnce is equal to previous station distance

                //First check priority
                if($station['priority']!=$stations[$selected_station]['priority'])
                {
                    //Stations have different priorities
                    if($station['priority']>$stations[$selected_station]['priority'])
                    {
                        //This station has a higher priority than the prev selected station
                        $selected_station = $stationID;
                    }
                }
                else
                {
                    //Stations have same priority, check current assigned count
                    if(count($results[$stationID])<count($results[$selected_station]))
                    {
                        //This station has less assigned drills
                        $selected_station = $stationID;
                    }
                }
            }
        }
        $results[$selected_station][] = array('x'=>$drill['x'], 'y'=>$drill['y'], 'distance'=>$selected_distance);
    }
    return $results;
}

//Get an array of all drill positions assigned to appropriate station
$drillAssignments =  get_assigned_drills($drillsAry, $stationsAry);

#########################################################
#  END PROCESSING LOGIC
#  BEGIN SAMPLE CODE TO OUTPUT RESULTS
#########################################################

$colors = array('#FF0000', '#008000', '#0000FF');

$tableData = array();
for($row=1; $row<=10; $row++)
{
    for($col=1; $col<=10; $col++) { $tableData[$row][$col] = ' '; }
}

//Insert drill positions into table data
foreach($drillAssignments as $stationID => $drillPositions)
{
    $color = $colors[$stationID];
    foreach($drillPositions as $drill)
    {
        $tableData[$drill['y']][$drill['x']] = "<span style=\"color:{$color}\">$stationID</span>";
    }
}

//Insert station positions into table data
foreach($stationsAry as $stationID => $station)
{
    $color = $colors[$stationID];
    $tableData[$station['y']][$station['x']] = "<b style=\"background-color:{$color}\">$stationID</b>";
}

$tableHTML = '';
for($row=count($tableData); $row>0; $row--)
{
    $tableHTML .= "<tr>\n";
    $tableHTML .= "<th>{$row}</th>\n";
    foreach($tableData[$row] as $cell)
    {
        $tableHTML .= "<td>{$cell}</td>\n";
    }
    $tableHTML .= "</tr>\n";
}
$tableHTML .= "</tr>\n";
$tableHTML .= "<th></th>\n";
for($col=1; $col<=10; $col++)
{
    $tableHTML .= "<th style=\"width:20px\">{$col}</th>\n";
}
$tableHTML .= "</tr>\n";

?>

<table border="1">
<?php echo $tableHTML; ?>
</table>

[Psycho]

EDIT: Deleted, I accidentally did a quote of my previous post instead of an edit.

[JChilds]

Hi,

 

Thanks for that, but it has got me mighty confused.

I have spent some time going over it and i'm wondering is it possible to have a separate distance for each station(assigned at same time where priorty is assigned)?

Also. If the drills are not within the specified radius of any station, they are not included.

 

Sorry I am being a pain. I only know the basics of php and have really jumped in the deep end i think.

[JChilds]

Seems to be some confusion on the priority also.

 

Here is a graphical example:

 

If priorities are the same, the current drill is to be assigned to the station with the lowest number of drills at present.

 

I was thinking about another way to do it:

- Get list of x,y coords for drills for each station

- Compare the arrays and delete duplicates depending on priority.

- if no priority, rely on size of each array to decide..

 

Is this a good/possible way to do it? Or is it not practical?

[Psycho]

OK, your graphical example changes some of my earlier assumptions. As I stated, the code I provided was only a proof of concept. I stated what the exact logic is, so it would only be a matter of modifying that logic to incorporate the process above.

 

I've already provided a proof of concept with a good deal of logic from scratch. So, I'm not going to rewrite it based on this new information. This forum is for people who want help with code they have written - so I have already dome more than what should be expected. But, I will be happy to provide some guidance on how you can proceed. If you want me to build the logic for you, contact me via PM and we can work something out.

 

So here is how I would modify the previous code:

 

1) The input data will need to include a radius for each station.

2) In the processing of the drill positions you would change the logic to first test if the drill position is within the radius of the station.

3a) If no: skip that station and test the next (start over with next comparison)

3b) If yes, check if the drill position was assigned to a prev station

4a) If no, assign the drill position to that station (start over with next comparison)

4b) If yes, check the priorities of the two stations.

5a) If prev station had a higher priority (start over with next comparison)

5b) If this station has a higher priority, assign the drill position to current station (start over with next comparison)

5c) If both stations have the same priority, assign drill position based upon current count of drill positions for the two